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

[Albert Chan]

Just to show what is involved doing Primality SPRP Test.
Example, Prove X = 56789 is composite

X-1 = 56788 = 2^2 * 14197 = 2^s * d
→ s = 2
→ d = 14197 = 0b11,011,101,110,101

Check if X is an a-SPRP, for a=2:
Bits Mod X
1     2^1 ≡ 2
1     2^3 ≡ 2² * 2 ≡ 8
0     2^6 ≡ 8² ≡ 64
1     2^13 ≡ 64² * 2 ≡ 8192
1     2^27 ≡ 8192² * 2 ≡ 25321
1     2^55 ≡ 25321² * 2 ≡ 10462
0     2^110 ≡ 10462² ≡ 21041
1     2^221 ≡ 21041² * 2 ≡ 50063
1     2^443 ≡ 50063² * 2 ≡ 13275
1     2^887 ≡ 13275² * 2 ≡ 18716
0     2^1774 ≡ 18716² ≡ 14104
1     2^3549 ≡ 14104² * 2 ≡ 38687
0     2^7098 ≡ 38687² ≡ 9874
1     2^14197 ≡ 9874² * 2 ≡ 35115 → a^d ≠ ±1
0     2^28394 ≡ 35115² ≡ 3668 → a^(2^r*d) ≠ -1, r < s

-> 56789 is *not* 2-SPRP
-> 56789 is *guaranteed* composite

2-SPRP may still be composite, but much less likely. Furthur testing may required.

An issue is how to do the squaring and multiply without overflow.
It may require splitting the numbers, and do in steps.