14
$\begingroup$

I am a software engineer but try to keep up with maths as I really enjoyed the subject at school. I just saw a great TED talk: Why I fell in love with monster prime numbers

The talk states that the current largest known prime is $2^{57885161}-1$

This got me thinking - how does one actually prove whether a number this large is prime or not?

Is it just done by brute force via a computer algorithm or are there any well known mathematical techniques for doing so?

I would be really grateful for any pointers as I am eager to learn about these techniques (if they exist).

$\endgroup$
  • 11
    $\begingroup$ This particular number is a Mersenne prime, primality of which can be proved using the Lucas-Lehmer Test. $\endgroup$ – Rebecca J. Stones Sep 3 '13 at 20:26
  • $\begingroup$ @Rebecca -- Thanks for the link. The method has a step in it where it says $M_p$ is prime iff $s_{p-2}=0 mod M_p$ where $M_p$ is the potential prime of form $2^p-1$. How would you calculate the mod against such a large number? $\endgroup$ – Mufasa Sep 3 '13 at 20:32
  • 1
    $\begingroup$ Using arbitrary precision arithmetic. I know also that this process is sped up using something called a discrete weighted transform, but I don't know much about this. $\endgroup$ – Rebecca J. Stones Sep 3 '13 at 20:34
  • 1
    $\begingroup$ Repeated squaring and mod reduction, or similar optimized methods, using an infinite precision math library. $\endgroup$ – Amzoti Sep 3 '13 at 20:34
  • 1
    $\begingroup$ @Mufasa Yes, you do need to perform some 57 million bit calculations - but at least you don't have to do trial division with $\approx \sqrt {M_p}$ potential divisors ... $\endgroup$ – Hagen von Eitzen Sep 3 '13 at 20:36
12
$\begingroup$

This particular number is a Mersenne prime, primality of which can be proved using the Lucas-Lehmer Test. Proving these numbers prime must be performed on a computer, and it can take months to perform the relevant computations. GIMPS hosts a distributed computing project to search for Mersenne primes.

Multiplication modulo $M_p:=2^p-1$ can be performed using arbitrary precision arithmetic. Highly optimized libraries by George Woltman (and others) are used to perform the actual computation; they make use of discrete weighted transforms to speed up the computation.

R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994) 305-324. (pdf)


In fact, there are several tests similar to the Lucas Lehmer Test. The Lucas Lehmer Test is favoured because it's necessary and sufficient (i.e., a pass implies primality, and a fail implies compositeness).

Lucas Lehmer Test: $M_n:=2^n-1$ is prime if and only if $S_{n-2} \equiv 0 \pmod {M_n}$, where $S_0=4$ and $S_i=S_{i-1}^2-2$ for $i \geq 1$.

To verify that $2^{19}$ is prime, we compute $S_i \pmod {M_{19}}$ for $0 \leq i \leq 17$, which is $$4, 14, 194, 37634, 218767, 510066, 386344, 323156, 218526, 504140, 103469, 417706, 307417, 382989, 275842, 85226, 523263, 0.$$

Theorem: If $n \equiv -1 \pmod 4$, then $M_n$ is prime if $T_{n-2} \equiv 0 \pmod {M_n}$, where $T_0=3$ and $T_i=T_{i-1}^2-2$ for $i \geq 1$.

To verify that $2^{19}$ is prime, we compute $T_i \pmod {M_{19}}$ for $0 \leq i \leq 17$, which is $$3, 7, 47, 2207, 152264, 354554, 244924, 420095, 86240, 326503, 409010, 208425, 132664, 470878, 399999, 439061, 523263, 0.$$

Theorem: Let $U_0=4$, $U_1=52$ and $U_i=14U_i-U_{i-2}$ for $i \geq 2$. If $U_{n-2} \equiv \pm 2^{(n+1)/2} \pmod n$ then $M_n$ is prime.

To verify that $2^{19}$ is prime, we compute $T_i \pmod {19}$ for $0 \leq i \leq 17$, which is $$4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2.$$ We now check that $2^{(n+1)/2} \equiv -2 \pmod {19}$.

There are several other such theorems in the following paper (not all for Mersenne primes):

D. H. Lehmer, An Extended Theory of Lucas' Functions, Ann. Math. (2), 31 (1930), 419-448. (link)


Similar efficient algorithms exist for other numbers, such as $$k \times 2^n+1$$ with $2^n<k$, which are called Proth numbers (the Brillhart-Lehmer-Selfridge test; see also Proth's Theorem), and $$k \times 2^n-1$$ with $2^n<k$ (the Lucas–Lehmer–Riesel test).

$\endgroup$
  • $\begingroup$ Thanks for all this - this should keep me busy for the next few weeks. :) $\endgroup$ – Mufasa Sep 3 '13 at 21:54
  • 1
    $\begingroup$ $2^{19}$ should be $2^{19}-1$ or $M_{19}$ (twice). And the RHS in the recursion for $U_i$ should contain $U_{i-1}$ instead of $U_i$, I suppose. $\endgroup$ – ccorn Aug 12 '18 at 13:24
  • $\begingroup$ ... and the $\pmod{n}$ in the theorem with the $U_i$ should likely be a $\pmod{M_n}$. $\endgroup$ – ccorn Aug 12 '18 at 15:07
  • $\begingroup$ Reading Lehmer's paper (p. 445), your proposition around the $U_i$ seems to be based on a misunderstanding. The $U_i$ are possible starting terms for the recursion $S_i=S_{i-1}^2-2$. $\endgroup$ – ccorn Aug 12 '18 at 15:53

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.