Primality hangs below 2^63 and leaves 2^89 - 1 open: trial division where Miller-Rabin and Lucas-Lehmer decide #2230

Primes.IsPrime decides primality by trial division, only for a number that fits a long. It has three defects, measured on master 1c9dbce:

The hang is an overflow. The loop is for (long divisor = 3; divisor * divisor <= value; divisor += 2). Past divisor = 3037000499, divisor * divisor exceeds long.MaxValue and wraps negative, so the condition stays true. For a prime between 3037000499² = 9223372030926249001 and 2^63, the loop runs until the divisor reaches the number itself. The same loop is in 2.6.0.

The time. For a prime near 2^63 the loop takes about 1.5 · 10^9 divisions.

The open cases. Two tests decide them, and both are proofs:

• Miller–Rabin with the first 12 primes as bases is exact below ψ12 = 318665857834031151167461, which is past 2^64. With the first 13 primes it is exact below ψ13 = 3317044064679887385961981. Both bounds are from Sorenson and Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017). It takes microseconds, and would replace the trial division.
• Lucas–Lehmer decides a Mersenne number 2^p − 1 in p − 2 squarings modulo it, for any p: 2^89 − 1 is prime, and 2^67 − 1 is composite.

Past ψ13, a single failed Miller–Rabin round still proves a number composite, so False can be answered at any size. True there needs a proof. BPSW has no known counterexample, but it is not a proof.

Raised by @Happypig375 on #2221.

🤖 Generated with Claude Code