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]

Modular reduction algorithm[edit]

Let $f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}$ be a monic polynomial of degree $d$ with coefficients in $\mathbb {Z}$ and suppose that $p=f(2^{m})$ is a Solinas prime. Given a number $n<p^{2}$ with up to $2md$ bits, we want to find a number congruent to $n$ mod $p$ with only as many bits as $p$ – that is, with at most $md$ bits.

First, represent $n$ in base $2^{m}$ :

n=\sum _{j=0}^{2d-1}A_{j}2^{mj}

Next, generate a $d$ -by- $d$ matrix $X=(X_{i,j})$ by stepping $d$ times the linear-feedback shift register defined over $\mathbb {Z}$ by the polynomial $f$ : starting with the $d$ -integer register $[0|0|...|0|1]$ , shift right one position, injecting $0$ on the left and adding (component-wise) the output value times the vector $[c_{0},...,c_{d-1}]$ at each step (see [1] for details). Let $X_{i,j}$ be the integer in the $j$ th register on the $i$ th step and note that the first row of $X$ is given by $(X_{0,j})=[c_{0},...,c_{d-1}]$ . Then if we denote by $B=(B_{i})$ the integer vector given by:

(B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X

,

it can be easily checked that:

\sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p

.

Thus $B$ represents an $md$ -bit integer congruent to $n$ .

For judicious choices of $f$ (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 ( $n-p\cdot (n/p)$ ).

Examples[edit]

Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:

p-192 $2^{192}-2^{64}-1$
p-224 $2^{224}-2^{96}+1$
p-256 $2^{256}-2^{224}+2^{192}+2^{96}-1$
p-384 $2^{384}-2^{128}-2^{96}+2^{32}-1$

Curve448 uses the Solinas prime $2^{448}-2^{224}-1.$

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.

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

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers

Modular reduction algorithm[edit]

Examples[edit]

See also[edit]

References[edit]