4 ms·

Can you explain finding Mersenne primes so CPU intensive? Mₙ = 2ⁿ − 1 gives an easy to generate candidate set and testing primality of a single number isn't th

Can you explain finding Mersenne primes so CPU intensive? Mₙ = 2ⁿ − 1 gives an easy to generate candidate set and testing primality of a single number isn't that expensive. 57885161th candidate being the 48th hit is getting pretty sparse I guess, but it isn't that crazy. What am I missing? Seems the compute would be rather small compared to much of the "big data" / NN training done every day

Someone 5y ago
Because they are so big. 10³ > 1,000, so in decimal, 2^57,885,161 - 1 has over 3 × 5,788,516 digits, so over 17 million. You do not check whether that is a prime by trial division (https://en.wikipedia.org/wiki/Trial_division https://en.wikipedia.org/wiki/Trial_division). If you could do a division every nanosecond and had a billion devices, that would still take way, way more time than till the heat death of the universe to do. We have better tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...), but the best generic one still is Õ((log n)⁶). Here, log(n) is about 58 million, so that log(n)⁶ has over 46 digits. We can do better, as we don’t need a generic test. for Mersenne numbers, there’s https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test.
jacquesm 5y ago
Because of the numers 'in between', once you start testing that many numbers in such an enormous range it eats up CPU power. There is some very beautiful math trickery which uses an FFT to help determine if a number is prime or not, and even though that's a massive optimization the number of remaining cycles required is still enormous. See here for more background: https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php
- np_tedious 5y ago
  Are Mersennes any more or less likely to be excluded by a probabilistic primality test than other numbers might be?
  - jacquesm 5y ago
    I do not know. Maybe Colin Wright would be able to comment on this.
  - pvg 5y ago
    https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php If you scroll to the very bottom there's some stuff on recent use of probable prime proofs, as well as a fairly detailed explanation of how the whole thing operates.
  - cperciva 5y ago
    The algorithm for testing a Mersenne number for primality has the same running time as performing a pseudoprime test, so there's no point using such probabilistic tests. It is however useful to perform "trial division" to exclude small factors.

Someone 5y ago

Because they are so big. 10³ > 1,000, so in decimal, 2^57,885,161 - 1 has over 3 × 5,788,516 digits, so over 17 million. You do not check whether that is a prime by trial division (https://en.wikipedia.org/wiki/Trial_division https://en.wikipedia.org/wiki/Trial_division). If you could do a division every nanosecond and had a billion devices, that would still take way, way more time than till the heat death of the universe to do. We have better tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...), but the best generic one still is Õ((log n)⁶). Here, log(n) is about 58 million, so that log(n)⁶ has over 46 digits. We can do better, as we don’t need a generic test. for Mersenne numbers, there’s https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test.

jacquesm 5y ago

Because of the numers 'in between', once you start testing that many numbers in such an enormous range it eats up CPU power. There is some very beautiful math trickery which uses an FFT to help determine if a number is prime or not, and even though that's a massive optimization the number of remaining cycles required is still enormous. See here for more background: https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php

np_tedious 5y ago
Are Mersennes any more or less likely to be excluded by a probabilistic primality test than other numbers might be?
- jacquesm 5y ago
  I do not know. Maybe Colin Wright would be able to comment on this.
- pvg 5y ago
  https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php If you scroll to the very bottom there's some stuff on recent use of probable prime proofs, as well as a fairly detailed explanation of how the whole thing operates.
- cperciva 5y ago
  The algorithm for testing a Mersenne number for primality has the same running time as performing a pseudoprime test, so there's no point using such probabilistic tests. It is however useful to perform "trial division" to exclude small factors.