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

[Thomas Klemm]

(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