From: nobody@shell.portal.com

To: cypherpunks@toad.com

Message Hash: 2e6cbfd22b343ea6d83ff341088c02ac61f79653530d8b8d994e11284be7e377

Message ID: <199404120257.TAA26115@jobe.shell.portal.com>

Reply To: *N/A*

UTC Datetime: 1994-04-12 02:56:13 UTC

Raw Date: Mon, 11 Apr 94 19:56:13 PDT

```
From: nobody@shell.portal.com
Date: Mon, 11 Apr 94 19:56:13 PDT
To: cypherpunks@toad.com
Subject: more number theorymore number theory
Message-ID: <199404120257.TAA26115@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain
-----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-----
```

Return to April 1994

- Return to “hughes@ah.com (Eric Hughes)”
Return to “nobody@shell.portal.com”

- 1994-04-12 (Mon, 11 Apr 94 19:56:13 PDT) - more number theorymore number theory -
*nobody@shell.portal.com*- 1994-04-12 (Tue, 12 Apr 94 10:15:07 PDT) - more number theory -
*hughes@ah.com (Eric Hughes)*

- 1994-04-12 (Tue, 12 Apr 94 10:15:07 PDT) - more number theory -