RNS modular multiplication through reduced base extensions
Karim Bigou, Arnaud Tisserand · 2014
The paper describes a new RNS (residue number system) modular multiplication algorithm, for finite field arithmetic over FP, based on a reduced number of moduli in base extensions with only 3n=2 moduli instead of 2n for standard ones. Our algorithm reduces both the number of elementary modular multiplications (EMMs) and the number of stored precomputations for large asymmetric cryptographic applications such as elliptic curve cryptography or Diffie-Hellman (DH) cryptosystem. It leads to faster operations and smaller circuits.