Solinas prime

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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.

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]

Suppose there is a Solinas prime , where and a number such that . In this case, has up to bits; we want to find a number congruent to mod with only as many bits as --that is, up to bits.

First, represent in base :

Next, generate a -by- matrix by stepping a -bit linear feedback shift register, starting with the values , for steps, so is the value of the th register on the th step. Then compute the matrix with the following equation:

It turns out that

so we have found a smaller number congruent to . Since this algorithm does not have divisions, it is very efficient compared to the naive modular reduction algorithm ().

Examples of Solinas primes[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 (1999). Generalized Mersenne Numbers (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39. 
  2. ^ Solinas, Jerome A. (1 January 2011). 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. 
  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. 

External links[edit]