Steven D'Aprano <steve+pyt...@pearwood.info> added the comment:
> [Steven] > > ... Try it on numbers like this: > > ... > > Q = P*(313*(P-1)+1)*(353*(P-1)+1) > > > > Q is a 397 digit Carmichael Number. Its smallest factor is P, > > which has 131 digits. [Tim] > The pure-Python Miller-Rabin code i posted in the aforementioned > thread is typically at least 100 times faster than that. This is exactly the sort of argument about quality of implementation which isn't, or shouldn't be, part of the argument about the API, IMO. Just as the choice of Timsort over Quicksort or Bubblesort *wink* isn't part of the list.sort() API, let alone the implementation choices in Timsort such as MIN_GALLOP. I'm happy to have a discussion about implementation, here or off-list, I'm sure I will learn a lot. But briefly, the Q I quoted above was carefully designed (not by me, I hasten to add!) to be a preudoprime to the first 307 prime bases, so it's something of a worst-case scenario for my version. > BTW, it doesn't much matter that this is "pure Python" - for ints of > this size the bulk of the time regardless is spent in CPython's > C-coded bigint arithmetic. A fair point, thank you. > About the API, I can't agree to the one you propose. Different > applications have different appropriate tradeoffs between degree of > certainty and time consumed - "one size fits all" doesn't fly here. > > def probably_prime(n, maxsteps=20) > > supplies a _default_ instead. I don't want an API that's useful > _only_ to people who don't know what they're doing ;-) It's not just for people who don't know what they're doing. It is for people who don't want to sweat the small details, they just want an answer True or False and are prepared to trust that the function author knows what they are doing. If someone cares about the small details like how many bases to try, they might also care about details like: - which specific bases are used; - whether to use Miller-Rabin at all; - how many trial divisions to do first; - which specific primality test to use; etc. What if the implementation shifts away from Miller-Rabin to (say) Baillie-PSW? Then your maxsteps parameter becomes meaningless. Do we deprecate it or leave it there in case the implementation changes again to something that has a concept of number of steps? I think that if someone cares sufficiently about the details, then they probably won't be satisfied with a single isprime function, but may want is_fermat_prime, is_miller_rabin_prime, is_lucas_prime etc. > > (By the way: for smallish numbers, under 2**64, no more than > > twelve rounds of Miller-Rabin are sufficient to > > deterministically decide whether a number is prime or not. > > But only if you use a fixed set of 12 specific bases for which the > claim has been proved. Correct. The first twelve primes make up such a minimal set. http://oeis.org/A014233 ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue39479> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
