Solinas prime

Summary

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.