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

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 or odd ${\displaystyle c}$[3]

## Modular Reduction Algorithm

Suppose there is a Solinas prime ${\displaystyle p=f(2^{m})}$, where ${\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}}$ and a number ${\displaystyle n}$ such that ${\displaystyle n. In this case, ${\displaystyle n}$ has 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, up to ${\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}$ by stepping a ${\displaystyle d}$-bit linear feedback shift register, starting with the values ${\displaystyle 0,0,...,0,1}$, for ${\displaystyle d}$ steps, so ${\displaystyle X_{i,j}}$ is the value of the ${\displaystyle j}$th register on the ${\displaystyle i}$th step. Then compute the matrix ${\displaystyle B}$ with the following equation:

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

It turns out that

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

so we have found a smaller number congruent to ${\displaystyle n}$. Since this algorithm does not have divisions, it is very efficient compared to the naive modular reduction algorithm (${\displaystyle n-p\cdot (n/p)}$).

## Examples of Solinas primes

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