.TH PRIME 2.SH NAMEgenprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest  \- prime number generation.SH SYNOPSIS.B #include <u.h>.br.B #include <libc.h>.br.B #include <mp.h>.br.B #include <libsec.h>.PP.Bint	smallprimetest(mpint *p).PP.Bint	probably_prime(mpint *p, int nrep).PP.Bvoid	genprime(mpint *p, int n, int nrep).PP.Bvoid	gensafeprime(mpint *p, mpint *alpha, int n, int accuracy).PP.Bvoid	genstrongprime(mpint *p, int n, int nrep).PP.Bvoid	DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen]).SH DESCRIPTION.PPPublic key algorithms abound in prime numbers.  The following routinesgenerate primes or test numbers for primality..PP.I Smallprimetestchecks for divisibility by the first 10000 primes.  It returns 0if.I pis not divisible by the primes and \-1 if it is..PP.I Probably_primeuses the Miller-Rabin test to test.IR p .It returns non-zero if.I Pis probably prime.  The probability of it not being prime is1/4**\fInrep\fR..PP.I Genprimegenerates a random.I nbit prime.  Since it uses the Miller-Rabin test,.I nrepis the repetition count passed to.IR probably_prime ..I Gensafegprimegenerates an.IR n -bitprime.I pand a generator.I alphaof the multiplicative group of integers mod \fIp\fR;there is a prime \fIq\fR such that \fIp-1=2*q\fR..I Genstrongprimegenerates a prime,.IR p ,with the following properties:.IP \-(\fIp\fR-1)/2 is prime.  Therefore.IR p -1has a large prime factor,.IR p '..IP \-.IR p '-1has a large prime factor.IP \-.IR p +1has a large prime factor.PP.I DSAprimesgenerates two primes,.I qand.IR p,using the NIST recommended algorithm for DSA primes..I qdivides.IR p -1.The random seed used is also returned, so that skepticscan later confirm the computation.  Be patient; this is aslow algorithm..SH SOURCE.B /sys/src/libsec.SH SEE ALSO.IR aes (2).IR blowfish (2),.IR des (2),.IR elgamal (2),.IR rsa (2)