Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2013

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

Search the Archive

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