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]- ^ Solinas, Jerome A. (1999). Generalized Mersenne Numbers (PDF) (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39.
- ^ 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.
- ^ 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.