From: mpd@netcom.com (Mike Duvos)
Date: Thu, 16 Jun 94 22:40:27 PDT
To: cypherpunks@toad.com
Subject: Re: Did anyone see...
In-Reply-To: <199406170136.SAA28382@mail.netcom.com>
Message-ID: <199406170540.WAA13491@netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Eli Brandt writes:

 >> 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)

 > Do you have a pointer to this paper?  I'd been under the
 > impression that this function had no analytic closed form
 > (unless you cheat).

I'll also post this to the list since I need to correct a dumb
error in my previous post.

I previously stated that Pi(n) was the Nth prime.  It is of
course in reality the Prime Number Counting Function which is
equal to the number of primes <= n.  Computing the Nth prime is
trivial given a program which computes Pi(n) since Pi(n) is
asymptotic to a known smooth function and one need only evaluate
it a small number of times to refine an initial estimate of the
Nth prime into the correct value.

Miller's definitive paper on the subject is...

    Computing Pi(x): The Meissel-Lehmer method
    Mathematics of Computation, 1985, 44, no. 170, 537-560

There is another paper by this gentleman which may be of interest
to Cypherpunks.  It is on the use of elliptic curves as a basis
for cryptosystems.  He demonstrates how an analogue to the
Diffie-Hellman secure key exchange may be constructed using
groups of points on elliptic curves and conjectures that such a
system may be stronger than one based on the discrete log
problem.  Here is the citation.

    Use of elliptic curves in cryptography
    Advances in cryptology---CRYPTO 85
    1986, 417-426 ISBN: 0-387-16463-4

Happy reading.

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