Solinas prime

In mathematics, a Solinas prime, or generalized Mersenne prime, is a prime number that has the form [math]\displaystyle{ f(2^m) }[/math], where [math]\displaystyle{ f(x) }[/math] 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 [math]\displaystyle{ 2^k-1 }[/math],
• Crandall or pseudo-Mersenne primes, which have the form [math]\displaystyle{ 2^k-c }[/math] for small odd [math]\displaystyle{ c }[/math].

Modular reduction algorithm

Let [math]\displaystyle{ f(t) = t^d - c_{d-1}t^{d-1} - ... - c_0 }[/math] be a monic polynomial of degree [math]\displaystyle{ d }[/math] with coefficients in [math]\displaystyle{ \mathbb{Z} }[/math] and suppose that [math]\displaystyle{ p = f(2^m) }[/math] is a Solinas prime. Given a number [math]\displaystyle{ n \lt p^2 }[/math] with up to [math]\displaystyle{ 2md }[/math] bits, we want to find a number congruent to [math]\displaystyle{ n }[/math] mod [math]\displaystyle{ p }[/math] with only as many bits as [math]\displaystyle{ p }[/math] – that is, with at most [math]\displaystyle{ md }[/math] bits.

First, represent [math]\displaystyle{ n }[/math] in base [math]\displaystyle{ 2^m }[/math]:

[math]\displaystyle{ n = \sum_{j=0}^{2d-1}A_j2^{mj} }[/math]

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

[math]\displaystyle{ (B_0 ... B_{d-1}) = (A_0 ... A_{d-1}) + (A_d ... A_{2d-1})X }[/math],

it can be easily checked that:

[math]\displaystyle{ \sum_{j=0}^{d-1}B_j2^{mj}\equiv\sum_{j=0}^{2d-1}A_j2^{mj} \mod p }[/math].

Thus [math]\displaystyle{ B }[/math] represents an [math]\displaystyle{ md }[/math]-bit integer congruent to [math]\displaystyle{ n }[/math].

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

Examples

Four of the recommended primes in NIST's document "Recommended Elliptic Curves for Federal Government Use" are Solinas primes:

• p-192 [math]\displaystyle{ 2^{192} - 2^{64} - 1 }[/math]
• p-224 [math]\displaystyle{ 2^{224} - 2^{96} + 1 }[/math]
• p-256 [math]\displaystyle{ 2^{256} - 2^{224} + 2^{192} + 2^{96} -1 }[/math]
• p-384 [math]\displaystyle{ 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1 }[/math]

Curve448 uses the Solinas prime [math]\displaystyle{ 2^{448} - 2^{224} - 1. }[/math]

See also

• Mersenne prime

References

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