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
You do not check whether that is a prime by 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_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.
See here for more background:
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.