[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)

[Gerald H]

(02-17-2019 10:58 PM)Albert Chan Wrote:  Trivia: searching backwards, found a particular bad composite, with many SPRP non-witnesses.

N = 999999 512881 = 881917 * 1133893 = A*B

For PRP test:
Total PRP non-witnesses = gcd(A-1,N-1) gcd(B-1,N-1) = 125988 * 125988 = 15872 976144
Percent of hitting PRP non-witness = (125988² - 2) / (N-3) ≈ 1.59%

For SPRP test:
Tried first 10 million bases, SPRP non-witnesses = 59708
Percent of hitting SPRP non-witness ≈ 59708/1e7 ≈ 0.60%

Note: 0.60% assumed statstical trend continued all the way to N-2

A very nice example of a difficult case - But the chance of testing this number, or any other constructed to be difficult cases, when feeding the programme a random number is very small.

Similarly the likelihood of finding a number as in posting #43 is very small.