
Re: Prime numbers and primality tests
Posted:
Jan 21, 2013 12:06 AM


I forgot to say: if a composite N passes the usual probable prime test b^(N1) = 1 (mod N) for one base b, then it is more likely than the average number that size to pass another test, c^(N1) = 1 (mod N).
For example, N = 341 is a pseudoprime base 2, which means that 2^3401 (mod 341). There are 100 bases b between 1 and 340 such that b^340 = 1 (mod 341).
On the other hand, if b^(N1) = 1 (mod N), then this N seems (empirically and heuristically) to be LESS likely than average to pass a Lucas probable prime test.
That's why I like to do one or more of EACH type of test, which I think is what PrimeQ does.

