[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-----