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

[Albert Chan]

(02-16-2019 05:57 PM)Thomas Klemm Wrote:  

Code:

   r    n    k
   4.21 1891 448
   5.00 8911 1780
   5.57 2701 484
   6.18 6533 1056
   6.20 5461 880
   6.41 1541 240
   8.22 8321 1012
   8.33 4033 484
   8.52 2047 240
   8.65 1387 160

Before n is strong pseduoprime, it must be a Fermat pseduoprime.
Let p1, ... pk be distinct prime factors of N:

Number of bases (mod N) = gcd(p1-1, N-1) ... gcd(pk-1, N-1)

So, picking top 2 numbers from the list:
1891 = 31 * 61, gcd(30, 1890) * gcd(60, 1890) = 30 * 30 = 900
8911 = 7*19*67, gcd(6, 8910) * gcd(18, 8910) * gcd(66, 8910) = 6 * 18 * 66 = 7128

No wonder so many strong pseudoprimes.

Gerald H's example, N = 803189 * 485909
gcd(N-1, 803188) * gcd(N-1, 485908) = 4*4 = 16
Removing 2 trivial bases of ±1, you are down to 14
Some Fermat pseudoprimes might not survive the strong test, so possibly few strong pseudoprimes.