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.. 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 
Modular Reduction Algorithm
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
Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:
Curve448 uses the Solinas prime
- Solinas, Jerome (1999). Generalized Mersenne Numbers (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39.
- 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.
- 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.
- Jerome A. Solinas, "Generalized Mersenne Numbers" (pdf)