Solinas prime

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form ${\displaystyle f(2^{m})}$, where ${\displaystyle f(x)}$ 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:

• Mersenne primes, which have the form ${\displaystyle 2^{k}-1}$,
• Crandall or pseudo-Mersenne primes, which have the form ${\displaystyle 2^{k}-c}$ for small odd ${\displaystyle c}$, ^[3] including ${\displaystyle 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 ${\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}}$ be a monic polynomial of degree ${\displaystyle d}$ with coefficients in ${\displaystyle \mathbb {Z} }$ and suppose that ${\displaystyle p=f(2^{m})}$ is a Solinas prime. Given a number ${\displaystyle n<p^{2}}$ with up to ${\displaystyle 2md}$ bits, we want to find a number congruent to ${\displaystyle n}$ mod ${\displaystyle p}$ with only as many bits as ${\displaystyle p}$ – that is, with at most ${\displaystyle md}$ bits.

First, represent ${\displaystyle n}$ in base ${\displaystyle 2^{m}}$:

${\displaystyle n=\sum _{j=0}^{2d-1}A_{j}2^{mj}}$

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

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

it can be easily checked that:

${\displaystyle \sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p}$.

Thus ${\displaystyle B}$ represents an ${\displaystyle md}$-bit integer congruent to ${\displaystyle n}$.

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

Examples

In 1999, NIST recommended four Solinas primes as moduli for elliptic curve cryptography: ^[4]

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

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

A Solinas prime that fits into a typical 64-bit unsigned integer is ${\displaystyle 2^{64}-2^{32}+1}$, it is ${\displaystyle \Phi _{192}(2)}$ where ${\displaystyle \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. ^[5]

A complete list of ${\displaystyle f(2^{k})=2^{m}-2^{n}\pm 1}$ with ${\displaystyle m\leq 2000}$, a small modular reduction weight ${\displaystyle wt<15}$, and ${\displaystyle 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. ^[6]

See also

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

References

1. Solinas, Jerome A. (1999). Generalized Mersenne Numbers (PDF) (Technical report). Center for Applied Cryptographic Research, University of Waterloo. CORR-99-39.
2. Solinas, Jerome A. (2011). "Generalized Mersenne Prime". In Tilborg, Henk C. A. van; Jajodia, Sushil (eds.). Encyclopedia of Cryptography and Security . Springer US. pp.  509–510. doi:10.1007/978-1-4419-5906-5_32. ISBN   978-1-4419-5905-8.
3. USpatent 5159632,Richard E. Crandall,"Method and apparatus for public key exchange in a cryptographic system",issued 1992-10-27, assigned to NeXT Computer, Inc. 
4. Recommended Elliptic Curves for Federal Government Use (PDF) (Technical report). NIST. 1999.
5. Craig-Wood, Nick. "Integer DWTs mod 2^64-2^32+1". www.craig-wood.com.
6. de Jesús Angel Angel, José; Morales-Luna, Guillermo (2010). "Solinas primes of small weight for fixed sizes". Cryptology ePrint Archive, Paper 2010/058.