Generalized Mersenne Prime

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form $f(2^m)$, where $f(x)$ 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 $2^k-1$,
* Crandall or pseudo-Mersenne primes, which have the form $2^k-c$ for small odd $c$.

Modular reduction algorithm

Let $f(t) = t^d - c_t^ - ... - c_0$ be a monic polynomial of degree $d$ with coefficients in $\mathbb$ and suppose that $p = f(2^m)$ is a Solinas prime. Given a number $n < p^2$ with up to $2md$ bits, we want to find a number congruent to $n$ mod $p$ with only as many bits as $p$ – that is, with at most $md$ bits.

First, represent $n$ in base $2^m$:

:$n = \sum_^A_j2^$

Next, generate a $d$-by-$d$ matrix $X = (X_)$ by stepping $d$ times the linear-feedback shift register defined over $\mathbb$ by the polynomial $f$: starting with the $d$-integer register 0 , ..., 0 , 1/math>, shift right one position, injecting $0$ on the left and adding (component-wise) the output value times the vector _0,...,c_/math> at each step (see for details). Let $X_$ be the integer in the $j$th register on the $i$th step and note that the first row of $X$ is given by (X_) = _0,...,c_/math>. Then if we denote by $B = (B_i)$ the integer vector given by:

:$(B_0 ... B_) = (A_0 ... A_) + (A_d ... A_)X$,

it can be easily checked that:

:$\sum_^B_j2^\equiv\sum_^A_j2^ \mod p$.

Thus $B$ represents an $md$-bit integer congruent to $n$.

For judicious choices of $f$ (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 ($n - p \cdot (n / p)$).

Examples

In 1999, NIST recommended four Solinas primes as moduli for elliptic curve cryptography:
* curve p-192 uses modulus $2^ - 2^ - 1$
* curve p-224 uses modulus $2^ - 2^ + 1$
* curve p-256 uses modulus $2^ - 2^ + 2^ + 2^ -1$
* curve p-384 uses modulus $2^ - 2^ - 2^ + 2^ - 1$.

A newer Curve448 uses modulus $2^ - 2^ - 1$.

See also

* Mersenne prime

References

{{Prime number classes, state=collapsed

Classes of prime numbers
Eponymous numbers in mathematics

fr:Nombre de Mersenne premier#Généralisations