Plantard Arithmetic for NTT, STARKS & Lattices

[mratsim]

Plantard arithmetic, introduced in https://thomas-plantard.github.io/pdf/Plantard21.pdf significantly improve modular arithmetic for single word fields. Those fields are popular for lattices and Starks based on small fields.

In particular, quoting section 4.2.4

4.2.4 Comparison with Pseudo-Mersenne
Pseudo-Mersenne numbers offer enough moduli for them
to be used in each application we are proposing. However,
table 6 clearly shows that even without correction, pseudo-
Mersenne based arithmetic is slower than our by at lease
17% and up to 38% depending of applications, and up to
52% when redundancy is not available.

This should allow the BabyBear and KoalaBear field to be very competitive with M31.

Further research

• Efficient Word Size Modular Multiplication over Signed Integers
  Aoki, Minematsu Okamura, Takagi
  ARITH 2022 (IEEE)
  http://crypto.mist.i.u-tokyo.ac.jp/publications/782700a094.pdf
• Improved Plantard AArithmetic for Lattice-based Cryptography
  Huang, Zhang, Zhao, Liu, Cheung, Koç, Chen,
  TCHES 2022
  https://eprint.iacr.org/2022/956