Aurora modexp implementation

What this crate is

This crate is an efficient implementation of the EVM modexp precompile. This crate exposes a single public function

pub fn modexp(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8>

This function takes the base, exponent and modulus as big-endian encoded bytes and returns the result in big-endian as well.

This crate is meant to be an efficient implementation, using as little memory as possible (for example, it does not copy the exponent slice). The exponentiation is done using the "binary method". The multiplication steps within the exponentiation use "Montgomery multiplication". In the case of even modulus, Montgomery multiplication does not apply directly. However we can reduce the problem to one involving an odd modulus and one where the modulus is a power of two. These two sub-problems can be solved efficiently (the former using Montgomery multiplication, the latter the modular arithmetic is trivial on a binary computer), then the results are combined using the Chinese remainder theorem.

The primary academic references for this implementation are:

1. Analyzing and Comparing Montgomery Multiplication Algorithms
2. Montgomery Reduction with Even Modulus
3. A Cryptographic Library for the Motorola DSP56000
4. The Art of Computer Programming Volume 2

What this crate is NOT

This crate is not a general purpose big integer library. If you need anything other than modexp, then you should use something like num-bigint or ibig.