Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The field prime numbers $p$ proposed by the NIST standards are referred to as Generalized Mersenne prime numbers [1] and as Pseudo Mersenne prime numbers [2].

Is there a difference between Pseudo Mersenne and Generalized Mersenne prime numbers? A lot of papers I recently read do claim that the primes proposed by the NIST standards are Pseudo Mersenne primes. However, other papers define them as Generalized Mersenne primes. Since those two prime families have different properties, applied in an ECC system, I am confused.


Section 7.1. NIST Discussion

Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs

share|improve this question
up vote 6 down vote accepted

In the context of the papers you reference, Generalized Mersenne prime numbers and Pseudo-Mersenne prime numbers are indeed two different things.

A Pseudo-Mersenne prime number has the form $2^{\alpha}-\gamma$ for a small integer $\gamma \gt 0$.

The term Generalized Mersenne prime number is defined by example in the referenced paper, and the examples given are the primes used for the NIST prime curves for elliptic curve cryptography. For instance, the P-256 prime can be expressed as $2^{256}–2^{224}+2^{192}+2^{96}–1$. Consequently, a Generalized Mersenne prime number could be defined as a sum $2^{c_n}+(\sum_{i=1}^{n-1}{{-1}^{b_i}2^{c_i}})-1$ for two integer sequences $(b_i)_{i=1}^n$ and $(c_i)_{i=1}^n$ such that $b_i\in \{0,1\}$ and $c_1 \gt 0$ and $c_{i-1} < c_i$ and $c_n \gt n$.

The two definitions, as given here, overlap for (proper) Mersenne numbers $2^{\alpha}-1$, but any Pseudo-Mersenne number might also be expressed as a Generalized Mersenne number. The reverse is not true, unless you apply a very liberal definition of "small" as in small integer $\gamma \gt 0$. Typically, though, the $c_i$ exponents in a Generalized Mersenne number would be chosen as multiples of the word bit size, and $\gamma \gt 0$ would be selected as small possible.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.