There is a VERY slow certain test for primality: divide by every candidate factor (up to sqrt(N)). This is certainly not what we want for very large numbers.
But the uncertainty of the probabilistic tests is very small. Steven likened the odds of the test being wrong to "less than the chance of a cosmic ray hitting a memory cell and altering the result." In any case, an amateur programmer could write a tight loop testing random large numbers and leave it running for the rest of their life without ever encountering a false positive. Number theorists have constructed these false positives... But if you know enough to do that construction, this isn't going to confuse you. On Fri, Jul 13, 2018, 4:44 AM Jacco van Dorp <j.van.d...@deonet.nl> wrote: > If there's going to be failure possible primality tests, there should > also exist certain ones. No matter how slow it can be to do it. > > Python if often a language for beginners. I think it'd be confusing to > a lot of people that there's going to be tests that show "This one is > probably prime", instead of sure tests. > > I'd call the functions is_prime() and is_likely_prime() (or > is_likely_not_prime(), depending on where it fails), to make it really > clear which you're picking and avoid confusion. > > 2018-07-13 10:21 GMT+02:00 Jeroen Demeyer <j.deme...@ugent.be>: > > On 2018-07-13 04:02, Chris Angelico wrote: > >> > >> Haha. Okay. I'm not familiar with every possible primality test, so I > >> had no idea that they ALL have the same failure mode :) > > > > > > There exist guaranteed primality tests, but those are much slower and > more > > complicated. The state of the art is ECPP: > > > > https://en.wikipedia.org/wiki/Elliptic_curve_primality > > > > _______________________________________________ > > Python-ideas mailing list > > Python-ideas@python.org > > https://mail.python.org/mailman/listinfo/python-ideas > > Code of Conduct: http://python.org/psf/codeofconduct/ > _______________________________________________ > Python-ideas mailing list > Python-ideas@python.org > https://mail.python.org/mailman/listinfo/python-ideas > Code of Conduct: http://python.org/psf/codeofconduct/ >
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
