In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form
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
is a Solinas prime.
bits, we want to find a number congruent to
{\displaystyle md}
bits.
in base
: Next, generate a
matrix
by stepping
times the linear-feedback shift register defined over
-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).
be the integer in the
th register on the
th step and note that the first row of
Then if we denote by
the integer vector given by: it can be easily checked that: Thus
-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