Solinas prime

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form $f(2^{m})$ , where $f(x)$ 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 $2^{k}-1$ ,
Crandall or pseudo-Mersenne primes, which have the form $2^{k}-c$ for small odd $c$ .^[3]

^ 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.

[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.

[1]

[2]

[3]