Solinas 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_{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 < 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_{j=0}^{2d-1}A_j2^{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 [1] 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_j2^{mj}\equiv\sum_{j=0}^{2d-1}A_j2^{mj} \mod p$.

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

For judicious choices of $f$ (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 ($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.$

See also

• Mersenne prime