[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.
Prev by Date:
**Re: Solid State Disk to boost Mathematica performance**
Next by Date:
**Re: problem with append**
Previous by thread:
**Re: Prime numbers and primality tests**
Next by thread:
**Re: Prime numbers and primality tests**
| |