On Fri, Jul 13, 2018 at 2:58 PM, Tim Peters tim.peters@gmail.com wrote:

[Chris Angelico, on "probable prime" testers]

You can say that about algorithms easily enough. My point is that this ought to be a constraint on the function - implementations may choose other algorithms, but they MUST follow one pattern or the other, meaning that a Python script can depend on it without knowing the implementation. Like guaranteeing that list.sort() is stable without stipulating the actual sort algo used.

I agree! Don't worry about it - if this module gets added, I'll make sure of it. My own "probable prime" function starts like so:

def pp(n, k=10): """ Return True iff n is a probable prime, using k Miller-Rabin tests.

`When False, n is definitely composite. """`

In the context of algorithmic number theory, "no false negatives" is implied by that context, but it should be spelled out anyway. A "probable prime", by definition, is an integer that satisfies some property that _all_ primes satisfy, but that some composites may satisfy too. The variation among probable prime algorithms is in which specific property(ies) they test for.

For example:

def pp1(n): return True

meets the promise, but is useless ;-)

def pp2(n): return n % 3 != 0 or n == 3

is slightly less useless.

But

def pp3(n): return n % 3 != 0

would be incorrect, because pp3(3) returns False - `n % 3 != 0` is not a property that all primes satisfy.

Thank you. Great explanation. Much appreciated!

ChrisA