Looking for some information on how long it has taken to generate large primes I stumbled across https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf which makes interesting reading. It concentrates on giving no false negatives (never saying n is not a prime when it is) but giving an increasing probability that n is a prime as testing goes on.
I did find an article from 2016 that mentioned M77232917 (a 23,249,425 digit Mersenne prime) and M74207281 (22,338,618 digit Mersenne prime) with the latter taking a month to check with the Lucas-Lehmer test. On 14/07/2018 05:54, Steven D'Aprano wrote: > On Fri, Jul 13, 2018 at 10:52:38AM -0500, Tim Peters wrote: > >> Steven's numbers are pretty baffling to me, since these are all composite >> and so iterating Miller-Rabin "should get out" pretty fast: > > That's because you haven't seen my code :-) > > It's over-engineered, class-based, and written as a learning exercise. > There's a compatibility layer so it will work back to Python 2.4 and an > instrumentation layer which I inserted in a fit of enthusiasm to gather > staticistics, which I have never once looked at since. > > And *even so* it is still fast enough for casual use at the interactive > interpreter, compared to more naive algorithms with worse Big O > performance characteristics. > > You might think 5 seconds is slow, but I'm serious when I say some of > the other algorithms I played with would take *days* to generate, > or check, largish primes. > > -- Steve (Gadget) Barnes Any opinions in this message are my personal opinions and do not reflect those of my employer. --- This email has been checked for viruses by AVG. https://www.avg.com _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/