Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #13240

Re: Prime numbers and primality tests

From RBaillie <bobbaillie@frii.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: Prime numbers and primality tests
Date 2013-01-21 05:06 +0000
Message-ID <kdiicf$nbq$1@smc.vnet.net> (permalink)
References <kd2lt4$co5$1@smc.vnet.net> <kdg2kq$hf6$1@smc.vnet.net>
Organization Time-Warner Telecom

Show all headers | View raw


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.

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Prime numbers and primality tests johnfeth@gmail.com - 2013-01-15 04:28 +0000
  Re: Prime numbers and primality tests amzoti <amzoti@gmail.com> - 2013-01-19 06:14 +0000
  Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-20 06:25 +0000
    Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-21 05:06 +0000
  Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-23 04:18 +0000

csiph-web