Re: Prime numbers and primality tests
- To: mathgroup at smc.vnet.net
- Subject: [mg129533] Re: Prime numbers and primality tests
- From: RBaillie <bobbaillie at frii.com>
- Date: Mon, 21 Jan 2013 00:08:02 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Delivered-to: l-mathgroup@wolfram.com
- Delivered-to: mathgroup-newout@smc.vnet.net
- Delivered-to: mathgroup-newsend@smc.vnet.net
- References: <kd2lt4$co5$1@smc.vnet.net> <kdg2kq$hf6$1@smc.vnet.net>
I forgot to say: if a composite N passes the usual probable prime test b^(N-1) = 1 (mod N) for one base b, then it is more likely than the average number that size to pass another test, c^(N-1) = 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^(N-1) = 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.