math/big: Comment for Int.ProbablyPrime() is inaccurate

[akalin]

It says:

// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.
// If it returns true, x is prime with probability 1 - 1/4^n.
// If it returns false, x is not prime.

But this is backwards. It should be more like:

// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.
// If x is prime, it returns true.
// If x is not prime, it returns false with probability at least 1 - 1/4^n.

See https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Accuracy_of_the_test for a detailed explanation.

Also, the comment for nat.probablyPrime() needs to be changed similarly.

[ALTree]

The original comment says to the reader that true means "probably prime" and false means "composite". Which is the spirit of the Miller-Rabin test, and follows the good practice of clearly stating what the return value of the function means.

Your comment says that the function is always right on prime numbers, but it could be fooled (with small probability) by composite numbers. This is correct, but why is it "more accurate"?

Your proposed comment does not say what a true or false return value means. I see a true and wonder whether we are on the // if x is prime line or on the // if x is not prime line.

[akalin]

The statement "if x is not prime, it returns false with probability at least 1 - 1/4^n" is true, but it does not imply the different statement "if it returns true, x is prime with probability 1 - 1/4^n"; it's the figure of "1 - 1/4^n" that is inaccurate.

If you wanted to keep the original wording, you could say something like:

// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.
// If it returns true, x is probably prime, with confidence increasing as n does.
// If it returns false, x is not prime.

[akalin]

@ALTree (For some reason, GitHub isn't showing your latest comment so I'm quoting it here.)

Edit: Just realized you probably just deleted it. Leaving this up in case anyone else reading is unsure.

Now I don't understand why did you remove the 4^(-n) figure (which is a provably correct bound on the probability of an error) and replaced it with a vague statement on the increasing of the confidence..

Sorry, I wasn't clear. The original statement states the bound incorrectly. My first suggestion replaced it with the correct statement of the bound.

The Wikipedia link explains this also, but it's easier to see with symbols. Let X be the event "x is prime", and Y be the event "ProbablyPrime returns true". The correct statement of the bound is this:

P(not Y | not X) >= 1 - 4^{-n}

The original comment is saying

P(X | Y) = 1 - 4^{-n}

which does not follow, even if you replace = with >=. You need to use Bayes rule to compute that probability, which in general depends on the number x and the density of primes around it. So the best you can say in general is that P(X | Y) increases as n does.

[akalin]

Thinking about it a bit more, I have a third suggestion:

// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.
// If it returns true, the likelihood ratio is at least 4^n : 1 in favor of x being prime.
// If it returns false, x is not prime.

(see https://en.wikipedia.org/wiki/Bayes%27_rule#Frequentist_example for where this comes from.)

It preserves the form of the original comment and is less vague than my second suggestion. Not sure how many people are familiar with likelihood ratios, though.

[ALTree]

@akalin Yeah I deleted it because after re-reading your comment I understood the point you were making. I have a comment. You wrote that "So the best you can say in general is that P(X | Y) increases as n does.". Is this true? I mean: maybe 4^-n is not precise, but is it a valid bound? I'm reading the last part of the link you provided:

In such cases, only the error bound of 4^−k can be relied upon.

I'm not a bayesian, but is there a way to express the statement at least 4^n : 1 in favor of in term of a [0..1] probability? Like in

// If it returns true, x is prime with probability at least 1 - 1/4^n.

[akalin]

@ALTree You can say more, if you're willing to talk about the prior probability of x being prime. Maybe something like:

If it returns true, and p is the prior probability that x is prime, then x is prime with (posterior) probability at least 4^n p / ((4^n - 1)p + 1).

Not as simple an expression, I'm afraid.

[agl]

Thanks all. I'm suggesting https://go-review.googlesource.com/#/c/14052 as the fix for this.

[gopherbot]

CL https://golang.org/cl/14052 mentions this issue.