Solinas prime
In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form formula_1, where formula_2 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: Modular Reduction Algorithm. Let formula_6 be a monic polynomial of degree formula_7 with coefficients in formula_8 and suppose that formula_9 is a Solinas prime. Given a number formula_10 with up to formula_11 bits, we want to find a  number congruent to formula_12 mod formula_13 with only as many bits as formula_13 – that is, with at most formula_15 bits. First, represent formula_12 in base formula_17: Next, generate a formula_7-by-formula_7 matrix formula_21 by stepping formula_7 times the linear-feedback shift register defined over formula_8 by the polynomial formula_24: starting with the formula_7-integer register formula_26, shift right one position, injecting formula_27 on the left and adding (component-wise) the output value times the vector formula_28 at each step (see  for details). Let formula_29 be the integer in the formula_30th register on the formula_31th step and note that  the first row of formula_32 is given by formula_33. Then if we denote by formula_34 the integer vector given by: it can be easily checked that: Thus formula_37 represents an formula_15-bit integer congruent to formula_12. For judicious choices of formula_24 (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 (formula_41). 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 formula_46