Tricks for arithmetic modulo NIST primes

The US National Institute of Standards and Technology (NIST) originally recommended 15 elliptic curves for use in elliptic curve cryptography [1]. Ten of these are over a field of size 2ⁿ. The other five are over prime fields. The sizes of these fields are known as the NIST primes.

The NIST curves over prime fields are named after the number of bits in the prime: the name is "P-" followed by the number of bits. The primes themselves are named p with a subscript for the number of bits.

The five NIST primes are

p₁₉₂ = 2¹⁹² - 2⁶⁴ - 1
p₂₂₄ = 2²²⁴ - 2⁹⁶ + 1
p₂₅₆ = 2²⁵⁶ - 2²⁴⁴ + 2¹⁹² + 2⁹⁶ - 1
p₃₈₄ = 2³⁸⁴ - 2¹²⁸ - 2⁹⁶ + 2³² - 1
p₅₂₁ = 2⁵²¹ - 1

The largest of these, p₅₂₁, is a Mersenne prime, and the rest are generalized Mersenne primes.

Except for p₅₂₁, the exponents of 2 in the definitions of the NIST primes are all multiples of 32 or 64. This leads to efficient tricks for arithmetic modulo these primes carried out with 32-bit or 64-bit integers. You can find pseudocode implementations for these tricks in Mathematical routines for the NIST prime elliptic curves.

The elliptic curve Ed448 "Goldilocks" was not part of the original set of recommended curves from NIST but has been added. It employs a multiplication trick in the same spirit as the routines referenced above, but simpler. Ed448 uses

p = 2⁴⁴⁸ - 2²²⁴ - 1

which has the special form I^2 - I - 1 where I = 2²²⁴. This enables a trick known as Karatsuba multiplication. More on that here.

• NIST P-384
• Naming conventions for elliptic curve cryptography

[1] FIPS PUB 186-4. This publication is dated 2013, but the curve definitions are older. I haven't found for certain when the curves were defined. I've seen one source that says 1997 and another that says 1999.