# 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. 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 }$.

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

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

For judicious choices of $\displaystyle{ 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 ($\displaystyle{ 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 $\displaystyle{ 2^{192} - 2^{64} - 1 }$
• p-224 $\displaystyle{ 2^{224} - 2^{96} + 1 }$
• p-256 $\displaystyle{ 2^{256} - 2^{224} + 2^{192} + 2^{96} -1 }$
• p-384 $\displaystyle{ 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1 }$

Curve448 uses the Solinas prime $\displaystyle{ 2^{448} - 2^{224} - 1. }$