Solinas prime
Introduction 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. They are named after Jerome Solinas.This class of numbers encompasses a few other categories of prime numbers:* Mersenne primes, which have the form ,* Crandall or pseudo-Mersenne primes, which have the form  for small odd .
Modular reduction algorithm 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 ().
Examples Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:* p-192 * p-224 * p-256 * p-384 Curve448 uses the Solinas prime
See also * Mersenne prime
References