Comment 1:

->agl for a closer look, if you have time.
Looks like this could be the root cause:
big.ProbablyPrime(18699199384836356663) = false, should be true.
---
package main
import "big"
func main() {
    z := big.NewInt(0)
    z.SetString("18699199384836356663", 10)
    println(z.String())
    println(big.ProbablyPrime(z, 20))  // prints false, both 8g and 6g
}
---
http://www.wolframalpha.com/input/?i=18699199384836356663
says that it is prime.

Labels changed: added packagebug.

Owner changed to a...@golang.org.

Status changed to Accepted.

Comment 2:

Noted that it's slow. On TODO list.

Comment 3:

I believe the slowness could be due to the incorrectness of the algorithm. I have a 
couple of examples in the 648-bit space where it takes 108k tries before a random 
is reached (all-in-all covering 216000 different numbers); another, in the 66-bit 
space and using the incremental algorithm, fails to find a prime in at least the 
12,630,912 numbers between 18699199384836273063 and 
18699199384848903975. 
p9p's probable_prime finds 4225 primes within that slice, and wolfram alpha 
confirms at least a dozen of (somewhat) random sampled finds from there.
let me know if you want the file with the odd numbers (stepping of 4) of that slice for 
testing.

Comment 4:

Right, the issue is that ProbablyPrime is returning false negatives.
Details in comment #1.

Comment 5:

sorry, i was originally responding to comment #2 above mine, which came a little bit 
later than your #1 so i thought i'd make sure the ProbablePrime issue was emphasized.

Comment 6:

(removing the RSA speed from consideration)
There were a couple of issues with probablyPrime. I've written a couple of test
programs that use GMP to verify ProbablyPrime and they've now run for several million
iterations of 512 bit numbers with no problems.
CL coming in a sec.

Attachments:

1. driver.c (1735 bytes)
2. t.go (324 bytes)

Comment 7:

This issue was closed by revision 308064f.

Status changed to Fixed.