0

A Mersenne prime has $17 425 170$ digits. How many digits needs to be checked to know that this is a prime?

I know that the square rot of a number digit needs to be checked to know if it is a prime, but I have no idea what to do here.

Apple Pie
  • 35
  • 3
    You do not check the digits to test for primality. Do you mean how many operations it takes in terms of the number of digits? – Tobias Kildetoft Apr 12 '16 at 11:44
  • 5
    It is not necessary to check any digits - a Mersenne prime is, by definition, prime. – Carl Mummert Apr 12 '16 at 11:44
  • In practice there are much better tests than checking every prime up to $\sqrt N$. But if that is the strategy you need to check roughly $\sqrt N/\ln N$ primes. You know that $N$ is approx $10^{17425170}$. If you don't have a list of these primes, then you need to check every number up to $\sqrt N$ or maybe those that are not even or multiples of 2,3,5. – almagest Apr 12 '16 at 11:54

1 Answers1

1

$2^{57885161}-1$ is indeed prime (see here), and has $17425170$ digits. It is very difficult to check that this Mersenne number is prime (see the above link).

Dietrich Burde
  • 130,978
  • and checking it is prime "only asks $57885161$ multiplications modulo $2^{57885161}-1$", with the discrete Fourier transform a multiplication in $\mathbb{Z}_p$ can be done in $\mathcal{O}(p \ln p)$, hence it asks $\mathcal{O}(p^2 \ln p)$ operations to check if $2^p-1$ is prime ? – reuns Apr 12 '16 at 12:23