From: Nathan Zook <nzook@bga.com>
Date: Wed, 9 Aug 95 22:01:42 PDT
To: Ray Cromwell <rjc@clark.net>
Subject: Re: Prime Number Gen's.
In-Reply-To: <199508091413.KAA00112@clark.net>
Message-ID: <Pine.3.89.9508092321.C21852-0100000@maria.bga.com>
MIME-Version: 1.0
Content-Type: text/plain




On Wed, 9 Aug 1995, Ray Cromwell wrote:

> 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

Common, Ray!  floor(sqrt(p))! would work fine....  ;-)  Seriously, at 
least 1/4 of the numbers between can p and 0 prove that p is prime.  So you 
try for a while.  If you don't get it, you can flip back.

I apologize for being so vague.  I don't have the paper I read a couple 
years ago in front of me.  You might contact your local math department & 
ask...

Nathan