Post Reply 
[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
02-16-2019, 02:29 PM (This post was last modified: 02-16-2019 03:02 PM by Albert Chan.)
Post: #29
RE: [HP35s] Program for prime number (brut force)
(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.
Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019 02:29 PM

User(s) browsing this thread: 1 Guest(s)