[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Yet more number theory



-----BEGIN PGP SIGNED MESSAGE-----

Well, I'm the person posting all the number theory stuff anonymously.
Well, not too anonymously since I am signing each post... ;)

I thought I'd try out Matt Ghio's service.  I'm not sure exactly what
will happen, but hopefully you will able to reply to this message and
reach me!

Anyway, I got my copy of "Elementary Number Theory and its
Applications" by Kenneth Rosen just now, and checked Miller-Rabin
primality testing, and pseudoprime primality testing.  Eric pointed
out some recent work (by Pomerance I presume) and it does indeed junk
the notion that for pseudoprime testing, the failure rate is 2^-n, n
being the number of trials.

However, Miller-Rabin isn't susceptible (it uses strong pseudoprime
testing) - and what it even better is the latest bound is 4^-k!  That
is, if you pick k integers and perform M-R on n for each, the chance a
composite will pass is less than (1/4)^k.

And, there is no analogy of a Carmichael number for strong
pseudoprimes.

So I guess the bottom line is M-R is the way to go.


-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLas39YOA7OpLWtYzAQETVQP/YzHMudKp/ehgcG0MkBeoyhQsItAlAvXL
VVj2VN2ac7KjlqtyP/Frjq+6s/T0ai4MhojboaWKBJfuUvZT1hBj0c0PvkaHVeiQ
H1eJpEXEqbFoouRX/M7ZYLmwfeJenKn0th408gJBf6yDHwdv9dyo7//Hhd/GreWJ
K+9nHl4k3kU=
=9zRl
-----END PGP SIGNATURE-----