Solinas prime explained

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form

f( 2 ^{m)} , where f(x) is a low-degree polynomial with small integer coefficients.^{[1] [2]} These primes allow fast modular reduction algorithms and are widely used in cryptography. They are named after Jerome Solinas.

This class of numbers encompasses a few other categories of prime numbers:

• Mersenne primes, which have the form

2 ^{k-1} ,

• Crandall or pseudo-Mersenne primes, which have the form

2 ^{k-c} for small odd c .^[3]

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 Z and suppose that p = f( 2 ^{m)} is a Solinas prime. Given a number n < p ^{2} with up to 2 md 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 ^{2 d -1} _{j =0} A ^{mj} _{j 2}

Next, generate a

d -by-d matrix X = (X _{i,j} ) by stepping d times the linear-feedback shift register defined over 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 j th register on the i th 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 ^{d -1} _{j =0} B ^{mj} _{j 2} \equiv\sum ^{2 d -1} _{j =0} A ^{mj} _{j 2} \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 ⋅ (n / p) ).

Examples

Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:

• p-192

2 ^{192} - 2 ^{64} - 1

• p-224

2 ^{224} - 2 ^{96} + 1

• p-256

2 ^{256} - 2 ^{224} + 2 ^{192} + 2 ^{96} -1

• p-384

2 ^{384} - 2 ^{128} - 2 ^{96} + 2 ^{32} - 1

Curve448 uses the Solinas prime

2 ^{448} - 2 ^{224} - 1 .

See also

• Mersenne prime

Notes and References

1. Jerome A. . Solinas . Generalized Mersenne Numbers . CORR-99-39 . Center for Applied Cryptographic Research, University of Waterloo . 1999 .
2. Book: Solinas, Jerome A.. Encyclopedia of Cryptography and Security. limited. Henk C. A. van. Tilborg. Sushil. Jajodia. 2011. Springer US. 509–510. 10.1007/978-1-4419-5906-5_32. Generalized Mersenne Prime. 978-1-4419-5905-8.
3. US . 5159632 . patent . Method and apparatus for public key exchange in a cryptographic system . 1992-10-27 . 1991-09-17 . Richard E. Crandall . NeXT Computer, Inc. .