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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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