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.[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:
Let be a monic polynomial of degree with coefficients in and suppose that is a Solinas prime. Given a number with up to bits, we want to find a number congruent to mod with only as many bits as – that is, with at most bits.
First, represent in base :
Next, generate a -by- matrix by stepping times the linear-feedback shift register defined over by the polynomial : starting with the -integer register , shift right one position, injecting on the left and adding (component-wise) the output value times the vector at each step (see [1] for details). Let be the integer in the th register on the th step and note that the first row of is given by . Then if we denote by the integer vector given by:
it can be easily checked that:
Thus represents an -bit integer congruent to .
For judicious choices of (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 ( ).
Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:
Curve448 uses the Solinas prime