gridiron icon indicating copy to clipboard operation
gridiron copied to clipboard

62 bit montgomery multiply.

Open coltfred opened this issue 7 years ago • 0 comments

The implementation of montgomery multiplication is currently using our 31 bit representation. This is because of our desire to support WASM. We should detect if the machine has a 64 bit native multiply and if it does, use a 62 bit representation instead. I've hacked this up in a branch to only support 62 bit and the gains are around 40% on a 256 bit prime. These gains would be even larger on larger primes as the montgomery multiplication is n^2 in the length of the limbs array.

This gain is realized for multiplication as well as the exponentiation and is probably the lowest hanging fruit we have left.

See https://github.com/IronCoreLabs/gridiron/tree/62-bit-hack for my work on this.

coltfred avatar Dec 19 '18 17:12 coltfred