Optimize EVMMAX montgomery multiplication

[chfast]

Now that we have benchmarks for EVMMAX precompiles we can experiment with different Montgomery multiplication algorithms. Currently we use CIOS.

The reference paper we used have a summary of the complexity of each algorithm. However, these may not be directly applicable to small numbers like 256-bit. Check also what other projects are doing.

Also study https://www.amazon.science/blog/better-performing-25519-elliptic-curve-cryptography.

[triggeredcode]

@chfast Could I help here? I am good with algorithms, also it will help if I can get a bit more context. Thanks

[chfast]

Hi @triggeredcode,

The two important references are already in the description. You should check out our existing code implementing Montgomery multiplication using CIOS algorithm. https://github.com/ethereum/evmone/blob/v0.11.0/lib/evmmax/evmmax.cpp#L55-L83.

We want to know if swapping this algorithm with any other would bring performance improvements. The good overview of the algorithms is https://www.microsoft.com/en-us/research/wp-content/uploads/1998/06/97Acar.pdf. But you can also do your research.

This code is well tested and we have benchmarks so it should be relatively easy to get feedback.

[chfast]

Possibly generate the algorithms with https://github.com/mit-plv/fiat-crypto.