4
$\begingroup$

I'm trying to figure out why Mersenne Twister use exactly Mersenne prime numbers but not regular primes. What makes Mersenne prime numbers more appropriate for this role than regular primes?

$\endgroup$
1
  • 3
    $\begingroup$ From wikipedia ; with the restriction that $2^{nw-r}-1$ is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test that are needed in the parameter search. The question based on this will be more interesting then yours. $\endgroup$
    – kelalaka
    Sep 14, 2023 at 12:14

1 Answer 1

7
$\begingroup$

A Mersenne Twister is a Linear-Feedback Shift Register with other characteristics, including period a Mersenne prime¹. In essence, the question asks why that is desirable.

A LFSR with $n$-bit state generates a Maximum-length sequence (M-sequence) that repeats for the first time after $2^n-1$ steps (starting from any non-zero state) if and only if it's (binary) feedback polynomial is primitive and of degree $n$. Such M-sequence has other nice properties, like a flat spectrum, which makes using such polynomials desirable.

All degree-$n$ binary primitive polynomials are among the set $\mathcal S_n$ of the degree-$n$ binary primitive polynomials with an odd number of terms including $1$. And a small but sizable fraction of polynomials in $\mathcal S_n$ are primitive. Therefore, in order to identify a suitable polynomial, a common practice is screening candidates in $\mathcal S_n$ (or a subset of that) as follows:

  1. Check that the sequence repeats after $2^n-1$ steps. This is feasible for large $n$ because we can fast-forward by $s$ steps at cost growing polynomially with $n$ and $\log_2(s)$ (like $n^2\log_2s$ or something on that tune).
  2. Check that the sequence has no period shorter than $2^n-1$. For arbitrary $n$, we can use that any period $\ell$ must be a divisor of the (now verified) period $2^n-1$: for every prime $p$ dividing $2^n-1$ (and less than that), we check that $\ell=(2^n-1)/p$ is not a period. That's feasible even for large $n$ (like in the hundred thousands) if and only if we know the full factorization of $2^n-1$.

When $n$ gets large, it can be challenging to determine the full factorization of $2^n-1$, as necessary for step 2. For all $n<1207$ and many larger $n$ the factorization of $2^n-1$ is known, thanks to the Cunningham project, but these workable $n$ tend to thin out.

This is where choosing $n$ such that $2^n-1$ is prime (that is choosing $n$ a Mersenne exponent², equivalently $2^n-1$ a Mersenne prime¹) comes handy: for such $n$ we can just skip step 2, since the corresponding Mersenne prime $2^n-1$ has no prime divisor less than $2^n-1$ (because it's prime).

The standard Mersenne Twister does just that, with $n=19937$ (which is prime, since all Mersenne exponents² are prime).


Secondarily, making $n$ a Mersenne exponent² (in addition to using a primitive polynomial) makes sure the LFSR output has prime period $2^n-1$ (the corresponding Mersenne prime¹). It follows that decimating that output by keeping bits at any regular interval smaller than $2^n-1$ generates a sequence of same minimal period, which is a nice-to-have. It's also an M-sequence, see this for a proof.

Note: That does not make such LFSRs of cryptographic quality. In particular, with $n$ consecutive bits of the output and the polynomial, the state can be recovered and the whole output past and future found. It's needed only a little more bits if we replace "consecutive bits" by "bits at known position", or less than twice more bits if we don't know the polynomial.


We see that the question should really ask one of the equivalent:

  • Why does the Mersenne Twister use a Mersenne exponent² $n$ as the number of taps rather than a regular prime $n$, or just an ordinary integer $n$ as most other LFSRs do?
  • Why does the Mersenne Twister use a Mersenne prime¹ $2^n-1$ as the period rather than an ordinary Mersenne number³ $2^n-1$, or just any composite $2^n-1$ as most other LFSRs do?

¹ A Mersenne prime is a prime of the form $2^n-1$. They form the sequence A000668.

² A Mersenne exponent is an $n$ such that $2^n-1$ prime. They form the sequence A000043. All Mersenne exponents are prime, but few Mersenne exponents are Mersenne primes¹. The first four Mersenne primes¹ are Mersenne exponents, but the next few ones are not.

³ A Mersenne number is an integer of the form $2^n-1$ with $n$ prime. They form the sequence A001348. The first four Mersenne numbers are Mersenne primes¹ and Mersenne exponents², but the next one is neither.

$\endgroup$
5
  • $\begingroup$ Note that this still cannot guarantee the quality of the sequence, as 1011011101111... is not periodic, hence m-sequence has not short representation of the sequence. $\endgroup$
    – kelalaka
    Sep 14, 2023 at 15:20
  • 2
    $\begingroup$ It is also important to mention that we have record of at most 829-bit RSA factoring, so most of the time trying to factor the period number of around $2^{19937}-1$ (free paper) is not feasible, though we have good probabilistic primality test and slower deterministic primality test; though all needed once. $\endgroup$
    – kelalaka
    Sep 14, 2023 at 16:43
  • $\begingroup$ @kelalaka: for the question's purpose we are interested only in the factorization of integers of the form $2^n-1$. That's known when $n<1207$, and for many larger $n$. $\endgroup$
    – fgrieu
    Sep 14, 2023 at 17:37
  • $\begingroup$ My point was improving what if we don't use Mersenne Primes as you noted in the answer. Yes, they are worked from early years and still goes on. $\endgroup$
    – kelalaka
    Sep 14, 2023 at 18:03
  • 1
    $\begingroup$ I just remembered one other property of $m$-sequences that makes the cryptographically unattractive. Namely they have a low linear complexity. In other words we only need $n+1$ cyclic shifts of the same sequence to find linear dependencies. This implies that if we know $2n$ consecutive bits of an $m$-sequence of period $2^n-1$, we can identify, which LFSR (of length $n$) is generating it. Other pseudorandom sequences have higher linear complexity. That figure of merit was studied extensively in the 80s-90s (IIRC), may be even earlier. $\endgroup$ Oct 10, 2023 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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