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

[Albert Chan]

(04-10-2019 03:56 PM)fred_76 Wrote:  I use the Miller Rabin algorithm already detailed in some page before. I test only a small set of bases as it was proven that such small set is enough :

* if n < 2,047, it is enough to test a = 2;
* if n < 9,080,191, it is enough to test a = 31 and 73;
* if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
* if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;

Or, you can pick the bases from the records: http://miller-rabin.appspot.com

Assuming 12 digits range:

if n < 132,239, test a = 814494960528
if n < 360,018,361, test a = 1143370 and 2350307676
if n < 154,639,673,381, test a = 15 and 176006322 and 4221622697
if n < 47,636,622,961,201, test a = 2 and 2570940 and 211991001 and 3749873356

Do a = a (mod n). If a = 0 or 1 or n-1, skip the test and return as probable prime.

Edit: with little effort, you can use the bigger base for bigger range.

Example if n < 341,531, test a = 9,345,883,071,009,581,737 → reduced a = ((9345883e12 % n) + 71009581737) % n