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_{d-1}t^{d-1}-...-c_{0)$ be a monic polynomial of degree $d$ with coefficients in $\mathbb {Z}$ and suppose that $p=f(2^{m})$ is a Solinas prime. Given a number $n 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 _{j=0}^{2d-1}A_{j}2^{mj)$ Next, generate a $d$ -by-$d$ matrix $X=(X_{i,j})$ by stepping $d$ times the linear-feedback shift register defined over $\mathbb {Z}$ by the polynomial $f$ : starting with the $d$ -integer register $[0|0|...|0|1]$ , shift right one position, injecting $0$ on the left and adding (component-wise) the output value times the vector $[c_{0},...,c_{d-1}]$ at each step (see  for details). Let $X_{i,j)$ 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,j})=[c_{0},...,c_{d-1}]$ . Then if we denote by $B=(B_{i})$ the integer vector given by:

$(B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X$ ,

it can be easily checked that:

$\sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\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

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

• p-192 $2^{192}-2^{64}-1$ • p-224 $2^{224}-2^{96}+1$ • p-256 $2^{256}-2^{224}+2^{192}+2^{96}-1$ • p-384 $2^{384}-2^{128}-2^{96}+2^{32}-1$ Curve448 uses the Solinas prime $2^{448}-2^{224}-1.$ 