From: Anonymous <remailer-admin@chaos.bsu.edu>
Date: Tue, 12 Apr 94 12:41:25 PDT
To: cypherpunks@toad.com
Subject: No Subject
Message-ID: <199404122044.OAA20328@chaos.bsu.edu>
MIME-Version: 1.0
Content-Type: text/plain


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

Earlier, somebody indicated that large primes of the form 2^(2^n)+1
exist... actually, it is conjectured that beginning with F5, all are
composite.

This person is probably confusing Fermat numbers with Mersenne numbers
(see my earlier post) - large Mersenne primes exist, but not all
Mersenne numbers are primes.

Also, it was suggested that 2^128+1 is prime; this is false.  You can
almost do the calculation by hand using Fermat's Little Theorem.  But
with Mathematica:

PowerMod[3, 2^128, 2^128+1] = 47511664169441434718291075092691853899

This is not 1 so 2^128+1 is definitely not prime.

> The key property of them is if n is a Carmichael number and n=p*q*r,
> then (p-1), (q-1), and (r-1) divide (n-1).
> I wonder if Carmichael numbers always have some small factors.

Well, many Carmichael numbers do have small factors, but not
necessarily.  If you derive the formuals for creating Carmichael
numbers, you can use them to create Carmichael numbers with prime
factors, arbitrarily large if your patience is willing.

For example (with just a few minutes of Mathematica time)

p = 600035641
q = 1200071281
r = 1800106921
n = 1296230964879005767193383441

p,q,r are prime
n is a Carmichael number

And incidentally, Carmichael numbers can have more than three prime
factors, for instance 7 * 13 * 19 * 37, the smallest Carmichael number
with four.

> I should point out that the standard argument that picking 'k'
> different values for 'a' and then calculating the probability as
> (1/2)^k is fallacious.  This would be true if the probabilities were
> independent, but they aren't.  There was a paper on this about five
> years ago whose awareness has not been yet widespread.  I no longer
> have the reference.

Well, for our purposes, we only care if the probability is lower or
higher than (1/2)^k.  Maybe you can be more certain than (1/2)^k in
which case you are even happier.  So this is "fallacious" because the
probabilities aren't independent... so, what, are we talking larger
than (1/2)^k or smaller?  If smaller, then (1/2)^k is an easy to
calculate upper bound.

Earlier, I said:
>> 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.

Okay, this paper you keep referencing - does it apply to primality
testing based on pseudoprimes (converse of Fermat's Little Theorem),
or other methods, such as Miller-Rabin?  The above passage (the double
quoted one) applies specifically to Miller-Rabin, a test which has no
"bad" inputs - e.g. there exist numbers which will always pass
pseudoprime testing, but there do not exist numbers which always pass
Miller-Rabin.  For M-R, the chance of failure depends on the number of
iterations.

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

iQCVAgUBLar5AYOA7OpLWtYzAQEyLQP/Wb6m+S0pBQrkqPVrbUgkLCgoT5fmLuKC
+0zZ6plve65CuUSalI//L+kZmfaf2WiJnAow1V58i7YJQwMKnds3KomZKbMMpzzb
Y3wbQvuNc+T0kSi7uMeJG0vuzgwjgCYzAI0Xqv2i7hkMN1wejqax8tSK0ZKualrr
SEJKeTKmBvA=
=RwAS
-----END PGP SIGNATURE-----