Jump to content

Solinas prime

From Wikipedia, the free encyclopedia
(Redirected from Generalized Mersenne prime)

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form , where 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 ,
  • Crandall or pseudo-Mersenne primes, which have the form for small odd .[3]

Modular reduction algorithm

[edit]

Let be a monic polynomial of degree with coefficients in and suppose that is a Solinas prime. Given a number with up to bits, we want to find a number congruent to mod with only as many bits as – that is, with at most bits.

First, represent in base :

Next, generate a -by- matrix by stepping times the linear-feedback shift register defined over by the polynomial : starting with the -integer register , shift right one position, injecting on the left and adding (component-wise) the output value times the vector at each step (see [1] for details). Let be the integer in the th register on the th step and note that the first row of is given by . Then if we denote by the integer vector given by:

,

it can be easily checked that:

.

Thus represents an -bit integer congruent to .

For judicious choices of (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 ().

Examples

[edit]

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

  • p-192
  • p-224
  • p-256
  • p-384

Curve448 uses the Solinas prime

See also

[edit]

References

[edit]
  1. ^ Solinas, Jerome A. (1999). Generalized Mersenne Numbers (PDF) (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39.
  2. ^ Solinas, Jerome A. (2011). "Generalized Mersenne Prime". In Tilborg, Henk C. A. van; Jajodia, Sushil (eds.). Encyclopedia of Cryptography and Security. Springer US. pp. 509–510. doi:10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8.
  3. ^ US patent 5159632, Richard E. Crandall, "Method and apparatus for public key exchange in a cryptographic system", issued 1992-10-27, assigned to NeXT Computer, Inc.