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

[Albert Chan]

(02-16-2019 10:45 AM)Gerald H Wrote:  Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A.

Just checking, when you say random base, you meant 2 to A-2 ?

Technically, this is a composite test. Any number that failed is *guaranteed* composite.

The reverse is not always true: strong pseudoprimes

Thus, we use pre-selected set of bases, to cover each other's "holes", to prove primality.

Baillie-PSW primality test (SPRP + Lucas test) covered the "holes" even better.
There is an award of $30 to show an example of pseudoprime.