Prime Number Gen's.

"Rev. Ben" <samman@cs.yale.edu> writes on cpunks:
> Does anyone know of where I could get source, royalty free, in the US for 
> a good Prime Number Generator?

GNU code sounds like it would fit the royalty free bill.

Try the GNU multi-precision library: gmp-1.3.2.tar.gz from all good
GNU sources.  I get my stuff from ftp://src.doc.ic.ac.uk/gnu/ if you
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

I've got some code Aggelos Keromitis <kermit@forthnet.gr> wrote using
the GNU mp library for generating RSA keys, it uses the probab_prime
function, like this:

        while (!mpz_probab_prime_p(&p, 25))     /* Find a prime */
          mpz_add_ui(&p, &p, 1);

Where p is a random starting point.  Ie just add one and repeat.  It
would be faster to check for some more obvious things like even nos,
etc.  But it seems to work well enough, and generates working RSA
keys.

Adam
--
HAVE *YOU* EXPORTED RSA TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/
--rsa--------------------------8<-------------------------------
#!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL
$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa
2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print
pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length($n)&~1)/2)
-------------------------------8<-------------------------------
TRY: rsa -k=3 -n=7537d365 < msg | rsa -d -k=4e243e33 -n=7537d365

On Tue, 8 Aug 1995 aba@atlas.ex.ac.uk wrote:

> 
> "Rev. Ben" <samman@cs.yale.edu> writes on cpunks:
> > Does anyone know of where I could get source, royalty free, in the US for 
> > a good Prime Number Generator?
> 
> GNU code sounds like it would fit the royalty free bill.
> 
> Try the GNU multi-precision library: gmp-1.3.2.tar.gz from all good
> GNU sources.  I get my stuff from ftp://src.doc.ic.ac.uk/gnu/ if you
> 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....

Nathan

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

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