more number theorymore number theory

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

> What estimates exist for the density of large Carmichael numbers,
> say 1000 bits long?

I'm not sure off hand - maybe Ray can try to check the source of his
formula.

Carmichael numbers must be square free and the product of at least
three primes... I seem to remember a formula for the distribution of
square free integers, but can't quite remember it...

> test? Are other probability tests like Miller-Rabin any more
> provably likely to detect these?

Well Phil, you are in luck!  Miller-Rabin isn't fooled by Carmichael
numbers.  There still is a chance for failure, but it doesn't depend
on the input (i.e. there are no bad inputs for Miller-Rabin like there
are for pseudoprime testing).  Failure depends on how many iterations
you perform (n iterations = 2^-n chance of failure) and the values of
the base you choose.

For example, in Miller-Rabin, the Carmichael number 561 is exposed to
be composite by choosing a base of 7.

I'm familiar with two other primality testing algorithms (I'm no
number theory wiz so there are probably more): Lucas' and Lehmer's.
Well, Lehmer's method is a modification of Lucas' method.  They both
are slow, but have the advantage of being true.


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

iQCVAgUBLaoM/IOA7OpLWtYzAQEXPQQAy1110rgCUzLtKoaTsWvGCujq3fWD7Ppz
A+/2b4NmR9+YmqHl63kb9zKU1/KOfDVXsmE7o0beyRQzSNGzj2I5yEUrnz0IzBLt
cy4ooiE3ED/jBBc01MBYhm5v3s9dIMJNXbsw7mBSBasqzEvHHpjH8dnGZA8QXhYT
fKTlU7rKa0o=
=XgrZ
-----END PGP SIGNATURE-----

>Failure depends on how many iterations
>you perform (n iterations = 2^-n chance of failure) and the values of
>the base you choose.

As I pointed out before, this probability is not correct.  The trials
are not independent, so you cannot just multiply them together.

>I'm familiar with two other primality testing algorithms [...]:
>Lucas' and Lehmer's.

For some good information on primality testing, see

	A Course in Computational Algebraic Number Theory
	by Henri Cohen

Chapter 9 is titled "Modern Primality Tests".  I give you fair warning
that you will not be able to understand this without significant
effort.  The Pocklington-Lehmer primality test is in Chapter 8
"Factoring in the Dark Ages".

There's a very interesting result stated here, "There exists a
probabilistic polynomial time algorithm which can prove or disprove
that a given number N is prime".  The result is by Adleman and Huang.
(Yes, _that_ Adleman.)

And for purposes of cultural literacy, the names are the Jacobi sum
test, the elliptic curve tests, Goldwasser-Kilian, and Atkin (a
development on G-K).

Eric