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:
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:
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:
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
participants (3)
-
aba＠dcs.exeter.ac.uk -
Nathan Zook -
Ray Cromwell