[Date Index] [Thread Index] [Author Index]

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.