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. 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} , including c = {\displaystyle c=} 3 (sequence A050414 in the OEIS), 5 (sequence A059608 in the OEIS), 7 (sequence A059609 in the OEIS), 9 (sequence A059610 in the OEIS), etc.
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. 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 [ 0 | 0 | . . . | 0 | 1 ] {\displaystyle [0|0|...|0|1]} , shift right one position, injecting 0 {\displaystyle 0} on the left and adding (component-wise) the output value times the vector [ c 0 , . . . , c d − 1 ] {\displaystyle [c_{0},...,c_{d-1}]} at each step (see [1] 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 ) = [ c 0 , . . . , c d − 1 ] {\displaystyle (X_{0,j})=[c_{0},...,c_{d-1}]} . Then if we denote by B = ( B i ) {\displaystyle B=(B_{i})} the integer vector given by:
… excerpt ends here. Continue reading the full article.
