From: mpd@netcom.com (Mike Duvos)
Date: Thu, 16 Jun 94 17:53:33 PDT
To: cypherpunks@toad.com
Subject: Re: Did anyone see...
In-Reply-To: <Pine.3.89.9406161705.C27205-0100000@Joyce-Perkins.tenet.edu>
Message-ID: <199406170053.RAA21246@netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Dan Harmon <harmon@tenet.edu> writes:

 > If you find out anything would you please post it to the
 > list?  This is very curious.

D.C. Williams remembered the thread and Emailed me a copy.
(Thanks D.C.) It was in alt.security.pgp which is why I couldn't
find it.  I was looking in sci.math for something with the word
"prime" in the title. :)

I quote the interesting sections below.

Nick Gilling begins by asking:

 > Is there a formula for calculating primes?

Gareth McCaughan responds:

 > Well... yes, actually, but not a useful one.

 > For instance: "Wilson's theorem" says that if p is prime
 > then (p-1)! is congruent to -1, modulo p. And you can check
 > that if p isn't prime then (p-1)! is congruent to 0 modulo p
 > (i.e., is a multiple of p).

 > So, writing [x] for "integer part of x", ((p-1)! -
 > [(p-1)!/p].p)/(p-1) is 1 if p is prime and 0 if p is
 > composite. So summing this thing will give you a formula for
 > the number of primes <= any given number; and I'm sure
 > there's a "formulaic" way to invert this to give you the
 > n'th prime for any n.

 > Alternatively, there is a polynomial of degree
 > something-very-large in about 26 variables with the
 > property that when you plug integers into it you get either
 > a negative number or a prime; and every prime arises as some
 > value of it. (In fact, for any computable property of
 > positive integers, there is a polynomial in lots of
 > variables such that the values it takes are {some load of
 > negative numbers} together with {positive integers with the
 > required property}. This is a Deep Theorem.)

 > Alternatively, I suspect there is some sort of thing
 > involving contour integrals and the Riemann zeta function.

James Kilfiger then expands:

 > Actually it a little more interesting than this. First a
 > disclaimer, I'm writing from memory and may be wrong on
 > details If you want to see more a truly wonderful book is
 > "The Little book of BIG primes" By Riemboiem (I've spelt
 > this wrong) published by Springer-Verlag.

 > This book as a section on prime number formulae, There is a
 > famous class of polynomials {P(x)}, tend to be large (the
 > classic one has 26 variables and has degree 25) With the
 > exellent property of {all positive values taken by
 > P(x)}={all positive primes}. The existance of such
 > polynomials is gaurrenteed by results stemming from
 > Hilbert's 10th. Also There is a number \theta with
 > 3^\theta^n (or some similar formula, remeber I'm quoting
 > from memory) being prime for all values of n, unfortuantly
 > we can't calculate \theta, but its quite small. (if somebody
 > can correct me on the formula I'd be grateful)

Gareth McCaughan then cites the following reference:

 > By an amusing coincidence, when I went into our
 > departmental library to look for a reference, there on the
 > "new accessions" shelf was a book all about Hilbert's tenth
 > problem. So, here's a reference.

 > Matiyasevich, Yuri V. "Hilbert's 10th Problem" (MIT Press,
 > 1993; in their "Foundations of Computing" series) section
 > 3.4, at end.

 > For those who are wondering how on earth it's done, here's
 > a *very* brief sketch. In everything that follows
 > polynomials have integer coefficients, and variables range
 > over non-negative integers, which I shall call "natural
 > numbers".

 > Observation number 1: Suppose we have a set A of natural
 > numbers, and a polynomial P such that: there exist
 > x1,x2,..,xm with P(a,x1,..,xm)=0 iff a is in A. Then there
 > is a polynomial Q such that the natural number values of
 > Q(x0,..,xm) are just the elements of A. PROOF: put
 > Q(x0,..,xm) = (x0+1)(1-P(x0,..,xm)^2)-1 and notice that if P
 > isn't zero there, we get something negative, and if P is
 > zero we get x0.

 > Difficult Theorem number 1: There is a polynomial E such
 > that there exist x1,x2,..,xm with E(a,b,c,x1,..,xm)=0 if and
 > only if a^b=c.

 > Observation number 2: So it's enough to find an
 > "exponential polynomial" (i.e., we allow variables as
 > exponents) such that there exist x1,..,xm with
 > P(a,x1,..,xm)=0 if and only if a is prime.

 > Difficult Theorem number 2: We can "do" the operations
 > "factorial" and "greatest common divisor" with exponential
 > polynomials.

 > Easier Theorem: p is prime iff the greatest common divisor
 > of p and (p-1)! is 1. (See a posting I made earlier in this
 > thread.)

 > Conclusion: We can "do" primality with an exponential
 > polynomial, and hence with a normal polynomial.

 > Annoying Fact: The numbers do get *very* large. I do not
 > recommend trying to generate primes with this method. I
 > haven't done the calculations, but I suspect that getting
 > the prime 5 might require more computing resources than you
 > have available.

 > More details are in Matiyasevich's book. (Matiyasevich did
 > a large fraction of the work required to prove all this and
 > much more. He knows what he is talking about.)

Victor S. Miller, [who I suspect is the same Victor S. Miller I
knew at UMass Boston many years ago], published a nifty little
paper in the mid 1980's on the computation of the function Pi(n)
which gives the Nth prime as a function of N.  He had a table
giving the (10^N)th prime for n={3,6,9,12,15,18,...} which was
quite impressive.  Calculating the correct value for the
zillionth prime directly is a cute bit of mathematics.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $