Solinas prime

Modular reduction algorithm

Let f(t) = t^d - c_{d-1}t^{d-1} - ... - c_0 be a monic polynomial of degree d with coefficients in \mathbb{Z} and suppose that p = f(2^m) is a Solinas prime. Given a number n with up to 2md bits, we want to find a number congruent to n mod p with only as many bits as p – that is, with at most md bits.

First, represent n in base 2^m:

:n = \sum_{j=0}^{2d-1}A_j2^{mj}

Next, generate a d-by-d matrix X = (X_{i,j}) by stepping d times the linear-feedback shift register defined over \mathbb{Z} by the polynomial f: starting with the d-integer register [0 | 0 |...| 0 | 1], shift right one position, injecting 0 on the left and adding (component-wise) the output value times the vector [c_0,...,c_{d-1}] at each step (see [1] for details). Let X_{i,j} be the integer in the jth register on the ith step and note that the first row of X is given by (X_{0,j}) = [c_0,...,c_{d-1}]. Then if we denote by B = (B_i) the integer vector given by:

:(B_0 ... B_{d-1}) = (A_0 ... A_{d-1}) + (A_d ... A_{2d-1})X,

it can be easily checked that:

:\sum_{j=0}^{d-1}B_j2^{mj}\equiv\sum_{j=0}^{2d-1}A_j2^{mj} \mod p.

Thus B represents an md-bit integer congruent to n.

For judicious choices of f (again, see [1]), this algorithm involves only a relatively small number of additions and subtractions (and no divisions!), so it can be much more efficient than the naive modular reduction algorithm (n - p \cdot (n / p)).

Examples

In 1999, NIST recommended four Solinas primes as moduli for elliptic curve cryptography:

• curve p-192 uses modulus 2^{192} - 2^{64} - 1
• curve p-224 uses modulus 2^{224} - 2^{96} + 1
• curve p-256 uses modulus 2^{256} - 2^{224} + 2^{192} + 2^{96} -1
• curve p-384 uses modulus 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1.

A newer Curve448 uses modulus 2^{448} - 2^{224} - 1.

A Solinas prime that fits into a typical 64-bit unsigned integer is 2^{64}-2^{32}+1, it is \Phi_{192}(2) where \Phi is the cyclotomic polynomial, thus it is a unique prime in base 2 (with period length 192). This size is too small for cryptography, but finds use in implementing a number-theoretic transform for efficient multiplication of large numbers.

A complete list of f(2^k)=2^m - 2^n \pm 1 with m \leq 2000, a small modular reduction weight wt , and k=8,16,32,64 (i.e. multiples of a computer word size) was produced by José de Jesús Angel Angel and Guillermo Morales-Luna in 2010.

The Curve25519 uses 2^{255} - 19, which has also been called pseudo-Mersenne.

References

fr:Nombre de Mersenne premier#Généralisations

References

1. Solinas, Jerome A.. (1999). "Generalized Mersenne Numbers".
2. Solinas, Jerome A.. (2011). "Encyclopedia of Cryptography and Security". Springer US.
3. "Method and apparatus for public key exchange in a cryptographic system".
4. (1999). "Recommended Elliptic Curves for Federal Government Use".
5. "Integer DWTs mod 2^64-2^32+1".
6. (2010). "Solinas primes of small weight for fixed sizes".
7. (2018). "Efficient Arithmetic In (Pseudo-)Mersenne Prime Order Fields".