- Modular Reduction Algorithm
- Examples of Solinas primes
- See also
- References
- External links
In mathematics, a Solinas prime, or generalized mersenne prime, is a prime number that has the form 
, where 
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
- Crandall or pseudo-mersenne primes, which have the form
for small odd 
[3]
Modular Reduction Algorithm
Suppose there is a Solinas prime 
, where 
and a number 
such that 
. In this case, has up to 
bits; we want to find a number congruent to mod 
with only as many bits as --that is, up to 
bits.
First, represent in base 
:
Next, generate a 
-by- matrix 
by stepping a -bit linear feedback shift register, starting with the values 
, for steps, so 
is the value of the 
th register on the 
th step. Then compute the matrix 
with the following equation:
It turns out that
so we have found a smaller number congruent to . Since this algorithm does not have divisions, it is very efficient compared to the naive modular reduction algorithm (
).
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
- p-224
- p-256
- p-384
See also
- Mersenne prime
References
2. ^{{cite book|title=Encyclopedia of Cryptography and Security|first=Jerome A.|last=Solinas|editor-first1=Henk C. A. van|editor-last1=Tilborg|editor-first2=Sushil|editor-last2=Jajodia|date=1 January 2011|publisher=Springer US|pages=509–510|doi=10.1007/978-1-4419-5906-5_32|chapter = Generalized Mersenne Prime|isbn = 978-1-4419-5905-8}}
3. ^{{cite patent |country=US |number=5159632 |status=patent |title=Method and apparatus for public key exchange in a cryptographic system |gdate=1992-10-27 |fdate=1991-09-17 |pridate= |invent1= Richard E. Crandall |assign1=NeXT Computer, Inc. |url=http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5159632.PN.&OS=PN/5159632&RS=PN/5159632}}
External links
- Jerome A. Solinas, "Generalized Mersenne Numbers" (pdf)
- Voo nocturno
- Voopsu village
- Voorbereidend middelbaar beroepsonderwijs
- Voorbeschikten
- Voorburg group
- Voorburg 't Loo railway station
- Voorburg 't Loo RandstadRail station
- Voorde
- Voordelta
- Voorderweert
- Voor een Verloren Soldaat
- Voorekula
- Vooreküla
- Voore, Laane-Viru County
- Voore, Lääne-Viru County
- Vooremaa (ajaleht)
- Vooremaa (newspaper)
- Voorepalu
- Voorepera
- Voorgoed Voorbij
- Voorhees College Historic District
- Voorhees (disambiguation)
- Voorhees, Gmelin, and Walker
- Voorhees, Gmelin and Walker
- Voorhees high school