Solinas prime


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. These primes allow fast modular reduction algorithms and are widely used in cryptography.
This class of numbers encompasses a few other categories of prime numbers:
Let be a monic polynomial of degree over 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 the output value times the vector at each step. 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 , this algorithm involves only a relatively small number of additions and subtractions, so it can be much more efficient than the naive modular reduction algorithm.

Examples of Solinas primes

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