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

[Gerald H]

(02-16-2019 02:12 PM)Thomas Klemm Wrote:  

(02-16-2019 12:54 PM)Gerald H Wrote:  Please report a number falsely returned as prime.

Example:

Quote:Suppose we wish to determine if n = 221 is prime.
We randomly select a number a such that 1 < a < n - 1, say a = 174.
…
Since 220 ≡ −1 mod n, either 221 is prime, or 174 is a strong liar for 221.

But 221 = 13×17, so it's not a prime.

Quote:It can be shown that for any odd composite n, at least 3/4 of the bases a are witnesses for the compositeness of n.

Thus chances are that a composite number is falsely considered a prime if we run the test only once.
I would expect this to happen if you run the program multiple times with the same composite number.

Cheers
Thomas

"Chances are..." - No.

"At least 3/4 of bases are witnesses..." - Yes, but how many are in fact witnesses? The "at least" allows the likelihood that many more than 3/4 are witnesses, & that is in fact generally the case.

Set at random

N := 803189 * 485909

the product of two primes, how many bases are actually witnesses? Try running PRIME?, I will be very surprised if the 35s is fast enough for you to repeat the test until a 1 appears.

I use one test as it's reliable enough - Certainty is expensive, if you're really not sure try running the programme again.

For larger numbers, say 2^555 range, one test gives certainty.