Solinas prime
In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form f ( 2 m ) {\displaystyle f(2^{m})} , where f ( x ) {\displaystyle f(x)} is a low-degree polynomial with small integer coefficients. These primes allow fast modular reduction algorithms and are widely used in cryptography. They are named after Jerome Solinas.
, where
f
(
x
)
{\displaystyle f(x)}
is a low-This class of numbers encompasses a few other categories of prime numbers:
- Mersenne primes, which have the form 2 k − 1 {\displaystyle 2^{k}-1} ,
- Crandall or pseudo-Mersenne primes, which have the form 2 k − c {\displaystyle 2^{k}-c} for small odd c {\displaystyle c} .
,
for small 
.Modular reduction algorithm
Let f ( t ) = t d − c d − 1 t d − 1 − . . . − c 0 {\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}} be a monic polynomial of degree d {\displaystyle d} with coefficients in Z {\displaystyle \mathbb {Z} } and suppose that p = f ( 2 m ) {\displaystyle p=f(2^{m})} is a Solinas prime. Given a number n < p 2 {\displaystyle n<p^{2}} with up to 2 m d {\displaystyle 2md} bits, we want to find a number congruent to n {\displaystyle n} mod p {\displaystyle p} with only as many bits as p {\displaystyle p} – that is, with at most m d {\displaystyle md} bits.
be a 
with coefficients in
Z
{\displaystyle \mathbb {Z} }
and suppose that
p
=
f
(
2
m
)
{\displaystyle p=f(2^{m})}
is a Solinas prime. Given a number
n
<
p
2
{\displaystyle n<p^{2}}
with up to
2
m
d
{\displaystyle 2md}
bits, we want to find a number 
mod
p
{\displaystyle p}
with only as many bits as
p
{\displaystyle p}
bits.
First, represent n {\displaystyle n} in base 2 m {\displaystyle 2^{m}} :
n = ∑ j = 0 2 d − 1 A j 2 m j {\displaystyle n=\sum _{j=0}^{2d-1}A_{j}2^{mj}}
:
Next, generate a d {\displaystyle d} -by- d {\displaystyle d} matrix X = ( X i , j ) {\displaystyle X=(X_{i,j})} by stepping d {\displaystyle d} times the linear-feedback shift register defined over Z {\displaystyle \mathbb {Z} } by the polynomial f {\displaystyle f} : starting with the d {\displaystyle d} -integer register {\displaystyle } , shift right one position, injecting 0 {\displaystyle 0} on the left and adding (component-wise) the output value times the vector {\displaystyle } at each step (see for details). Let X i , j {\displaystyle X_{i,j}} be the integer in the j {\displaystyle j} th register on the i {\displaystyle i} th step and note that the first row of X {\displaystyle X} is given by ( X 0 , j ) = {\displaystyle (X_{0,j})=} . Then if we denote by B = ( B i ) {\displaystyle B=(B_{i})} the integer vector given by:
( B 0 . . . B d − 1 ) = ( A 0 . . . A d − 1 ) + ( A d . . . A 2 d − 1 ) X {\displaystyle (B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X} ,
by stepping
d
{\displaystyle d}
: starting with the
d
{\displaystyle d}
, shift right one position, injecting
0
{\displaystyle 0}
on the left and adding (component-wise) the output value times the vector
{\displaystyle }
at each step (see for details). Let
X
i
,
j
{\displaystyle X_{i,j}}
be the integer in the
j
{\displaystyle j}
th register on the
i
{\displaystyle i}
th step and note that the first row of
X
{\displaystyle X}
is given by
(
X
0
,
j
)
=
{\displaystyle (X_{0,j})=}
. Then if we denote by
B
=
(
B
i
)
{\displaystyle B=(B_{i})}
the integer vector given by:
,
it can be easily checked that:
∑ j = 0 d − 1 B j 2 m j ≡ ∑ j = 0 2 d − 1 A j 2 m j mod p {\displaystyle \sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p} .
.
Thus B {\displaystyle B} represents an m d {\displaystyle md} -bit integer congruent to n {\displaystyle n} .
represents an
m
d
{\displaystyle md}
For judicious choices of f {\displaystyle f} (again, see ), 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 ⋅ ( n / p ) {\displaystyle n-p\cdot (n/p)} ).
).
Examples
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 {\displaystyle 2^{192}-2^{64}-1}
- p-224 2 224 − 2 96 + 1 {\displaystyle 2^{224}-2^{96}+1}
- p-256 2 256 − 2 224 + 2 192 + 2 96 − 1 {\displaystyle 2^{256}-2^{224}+2^{192}+2^{96}-1}
- p-384 2 384 − 2 128 − 2 96 + 2 32 − 1 {\displaystyle 2^{384}-2^{128}-2^{96}+2^{32}-1}
Curve448 uses the Solinas prime 2 448 − 2 224 − 1. {\displaystyle 2^{448}-2^{224}-1.}
See also
References
- ^ 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.