Solinas prime

Short description: Prime number of the form that allows fast modular reduction

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$, including $c=$ 3 (sequence A050414 in the OEIS), 5 (sequence A059608 in the OEIS), 7 (sequence A059609 in the OEIS), 9 (sequence A059610 in the OEIS), etc.

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{\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}_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{\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}_j{2}^{mj}\equiv \sum _{j=0}^{2d-1}{A}_j{2}^{mj}modp$.

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

In 1999, NIST recommended four Solinas primes as moduli for elliptic curve cryptography:

• curve p-192 uses modulus $2^{192}-2^{64}-1$
• curve p-224 uses modulus $2^{224}-2^{96}+1$
• curve p-256 uses modulus $2^{256}-2^{224}+2^{192}+2^{96}-1$
• curve p-384 uses modulus $2^{384}-2^{128}-2^{96}+2^{32}-1$.

A newer Curve448 uses modulus $2^{448}-2^{224}-1$.

A Solinas prime that fits into a typical 64-bit unsigned integer is $2^{64}-2^{32}+1$, it is ${\mathrm{\Phi }}_{192}(2)$ where $\mathrm{\Phi }$ is the cyclotomic polynomial, thus it is a unique prime in base 2 (with period length 192). This size is too small for cryptography, but finds use in implementing a number-theoretic transform for efficient multiplication of large numbers.

A complete list of $f(2^k)=2^m-2^n\pm 1$ with $m\le 2000$, a small modular reduction weight $wt<15$, and $k=8,16,32,64$ (i.e. multiples of a computer word size) was produced by José de Jesús Angel Angel and Guillermo Morales-Luna in 2010.

See also

• Proth prime: several examples on this page are also Proth primes

References

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