From: Ray Cromwell <rjc@clark.net>
Date: Wed, 9 Aug 95 07:14:32 PDT
To: nzook@bga.com (Nathan Zook)
Subject: Re: Prime Number Gen's.
In-Reply-To: <Pine.3.89.9508082313.C4312-0100000@lia.bga.com>
Message-ID: <199508091413.KAA00112@clark.net>
MIME-Version: 1.0
Content-Type: text/plain


Nathan Zook wrote:
> > don't have a GNU ftp site to hand.
> > 
> > There's a function
> > 
> > 	int mpz_probab_prime_p(mpnum, SURETY)
> > 
> > which returns true if the prime passes SURETY probablistic prime tests.
> > 
> > I think if it passes say 25 tests, then there will be less than a
> > 1/2^25 chance that it is not prime.
> > 
> > Also, on:
> > 
> > 	http://dcs.ex.ac.uk/~aba/rsa-keygen.html
> > 
> 
> The proper thing to do is to then search for a number which demonstrates 
> p is prime....

  And how do you do this? I'm not aware of any deterministic primality
test which isn't atleast as hard as factoring. P-1 factorial is such
a number which could demonstrate P is prime (compute the gcd, check if
they are relatively prime). Good luck computing it.
 
-Ray