number theorynumber theory

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

All right, a number theory discussion!

>The integer N is prime if:
>   2^N - 2
>  ---------
>      N              is an integer.

Well, this is false.

The above formula is derived from Fermat's Little Theorem, or Euler's
Generalization of Fermat's Little Theorem.

a^(n-1) = 1 mod n, n prime, gcd(a,n) = 1
==> a^n = n mod n
    a^n - n = kn, for k some integer
    (a^n - n)/n = k, for k some integer

now sub in a = 2.

However, the converse of this is not true (n isn't necessarily prime
if it satifies the formula).  Composities that satisfy this are called
pseudoprimes.  For example, for a = 2, n = 341 satisfies the relation,
so 341 is a pseudoprime base 2.

Now it works "most" of the time, and in fact one method of testing
large integers for primality is to choose a whole bunch of a's and
plug in n.  If a^(n-1) mod n != 1, the number is composite and can be
rejected.  But, if a^(n-1) mod n == 1, you can only be 50% sure n is
prime.  (Roughly speaking; Phil Karn notes that the PGP docs indicate
a 50%, I've seen proofs that this pseudoprime test fails 50% of the
time, etc.  But these are upper bounds; the real percentage seems much
lower and I haven't seen a tighter bound on it).

There is a "strong psuedoprime" test, in which failure occurs for at
least 25% of integers in the range, thus the probability that a
composite will pass is at most 25%.

Even better is Lucas' test, but it runs a bit slow.

However, you can be unlucky and pick a Carmichael number, which will
pass the pseudoprime test for all bases relatively prime to n (for all
a such that gcd(a,n) = 1).  Ray Cromwell advises to choose n = 561,
the smallest Carmichael number (an excellent choice!)  Carmichael
numbers exist, they are relatively rare, formulas exists for
generating some of them...

Eric Hughes mentions that 1729 is the next Carmichael number... not
quite true.  1105 is the next Carmichael number.  (But congrats Eric
for even remembering the third one!) ;)

Now, some other topics:

> For any number n which is prime, (2^n)-1 is also prime (Mersenne's
> theorem).

Hm... some confusion here.  A Mersenne prime is of this form (2^n) - 1
where n is prime, but not all number this formula generates are
primes.  Mersenne primes are related to perfect numbers.

An example of a composite of this form:

for n = 11, 2^11 - 1 = 2047 = 23 * 89

> For any number n (2^(2^n))+1 is prime. (I might have that wrong, I
> don't remember exactly)

Well, no.  These number are Fermat numbers, and while the first 5 (n=0
to n=4) but Euler showed that the Fermat number for n=5 is composite.

As an aside, Fermat numbers satisfy the pseudoprime test.

> For any number n, if the square root of (n!)+1 is an integer, it is
> also prime.  (This is interesting, but rather useless in practice)

A couple of issues here:

I think you may be remembering a different theorem, a consequence of
Wilson's theorem.

Wilson's theorem says: 

  for any prime p, (p-1)! = -1 mod p

The theorem I think you are referring to is:
  if P is the product of the remainders relatively prime to m, then
  P = +/- 1 mod m; +/- = plus or minus

The congruence is +1 except in three cases:
  1) m = 4
  2) m = p^b (m is a power of an odd prime)
  3) m = 2p^b (m is twice the power of an odd prime)

I'm still trying to either prove or disprove your claim!

Two followups relating the the original formula posted:

> For any number a, 1<a<=n, n! mod a == 0; therefore, n!+1 mod a == 1.
> n!+1 is prime.  Prime numbers don't have integral square roots.

Good analysis, except for the "n! + 1 is prime" part.  The only thing
you can say is n!+1 has no factors <= n.

For example, n = 4, n!+1 = 25 = 5 * 5.

> Well, it was quoted from memory, so it's possible that I made an
> error, but it seems to work as stated...
> For example :
> (4!+1)^(1/2)=5
> (5!+1)^(1/2)=11
> (7!+1)^(1/2)=71
> I can't find a value which produces a result that is a non-prime
> integer.  (Of course that doesn't prove that there isn't one.)

Still working on this... ;)


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

iQCVAgUBLanNNYOA7OpLWtYzAQF10wP9GExbaoloiXqFe7AtXb/UzUHXhW3VDC1b
mfD0RhgK2i0Dr05RW5FCvj/9i7Jxhrd3E26hTe5g4WckvIcvp+GWhE/5fkdtVMA9
THutX1ukGO/5qCxSRT4hVCeXStAz7tunkF3fcEQjPe8pSSvKxN8tw/wIZzclRDRx
JDE4HYRhAz0=
=OW8h
-----END PGP SIGNATURE-----

What estimates exist for the density of large Carmichael numbers, say
1000 bits long? I.e., what's the probability of running into one by
accident when generating primes by the usual technique of picking a
random starting point and searching up until you find a number that
passes seive or small factor tests and a few iterations of Fermat's
test? Are other probability tests like Miller-Rabin any more provably
likely to detect these?

I'm currently playing with the Miller-Rabin test. Boy, is modular
exponentiation a pig (at least the routine in RSAREF).

Phil

The figure I have for the Carmichael numbers is x^(.1), where .1 is
approximate.  Ray has the exponent at 2/7.  The exact one doesn't
matter so much, because compared to the density of primes (x/ln x),
these are both extremely small.  The chance of picking a Carmichael
number is very small.  But that's not the relevant density.

The problem with RSAREF's prime testing is that it will find
pseudoprimes base 2.  Carmichael numbers are pseudoprimes to any base,
but that's unneeded for the RSAREF test.  What is needed is the
density of pseudoprimes base 2.  I don't know that figure.  I don't
know that anybody does.

I would really suggest that someone with access to Mathematica or
Maple do an experiment to find out how many non-primes the RSAREF
algorithm passes.

Carmichael numbers do not, generally, pass the Miller-Rabin test.
Some might; I'll bet it's an open question.

Eric

Some anonymous agent wrote:

> Eric Hughes mentions that 1729 is the next Carmichael number... not
> quite true.  1105 is the next Carmichael number.  (But congrats Eric
> for even remembering the third one!) ;)
> 

I suspect Eric's memory was influenced by his memories of last
Saturday night, after the Cyperpunks meeting and after the Dave Emory
lecture a half dozen of us saw that evening.

We all decided to attend the midnight showing at the Stanford Theater
of a new Indian film, "Rendezvous with Ramanujan," based of course on
the famous Arthur C. Clarke novel, and directed by noted British
director, G. H. Hardy (no relation to Norm Hardy).

Our taxi had the license plate number "RSA-1729," which we took to be
a pun about the next big factoring project. After all, 1729 is a
rather unremarkable number.

The taxi driver, an unemployed mathematician named Ted Streleski, was
heard muttering, "Some squares, some cubes." 


--Klaus! von Future Prime

(channeled by Tim May)

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

>If a^(n-1) mod n != 1, the number is composite and can be
>rejected.  But, if a^(n-1) mod n == 1, you can only be 50% sure n is
>prime.  

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.

For everybody that wants to really know about this, find out about the
Miller-Rabin test.

>(Roughly speaking; Phil Karn notes that the PGP docs indicate
>a 50%, I've seen proofs that this pseudoprime test fails 50% of the
>time, etc.  But these are upper bounds; the real percentage seems much
>lower and I haven't seen a tighter bound on it).

The 50% figure is easy to show with some considerations about
quadratic residues.  Tightening the bound is much more difficult.

Eric