.TH IPINTS-GENPRIME 2.SH NAMEipints: genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime  \- prime number generation.SH SYNOPSIS.EXinclude "ipints.m";ipints := load IPints IPints->PATH;IPint: import ipints; probably_prime: fn(n: ref IPint, nrep: int): int; genprime: fn(nbits: int, nrep: int): ref IPint;gensafeprime: fn(nbits: int, nrep: int): (ref IPint, ref IPint);	# p, alphagenstrongprime: fn(nbits: int, nrep: int): ref IPint;DSAprimes: fn(): (ref IPint, ref IPint, array of byte);	# q, p, seed.EE.SH DESCRIPTIONThis set of functions in.B IPints(see.IR ipints (2))helps Limbo applicationsgenerate and test large prime numbers with relative efficiency.The numbers are all represented by.BR IPint ..PP.I Probably_primeuses the Miller-Rabin test to test.IR n .It returns true (non-zero) if.I Pis probably prime.  The probability of.I nnot being prime is1/4**\fInrep\fR.If.I probably_primereturns false (zero),.I nis certainly not prime..PP.I Genprimereturns a random prime of length.IR nbits .Since it uses the Miller-Rabin test,.I nrepis the repetition count passed to.IR probably_prime ..PP.I Gensafeprimereturns a tuple.BI ( p,\ alpha ),where.I pis a prime of length.I nbitsand.I alphais a generator of the multiplicative group of integers mod \fIp\fR;there is a prime \fIq\fR such that \fIp-1=2*q\fR..PP.I Genstrongprimereturns a prime.I pwith 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 DSAprimesuses the NIST recommended algorithm for generating DSA primes andreturns a tuple.BI ( q,\ p,\ seed ) ,where.I pand.I qare primes, and.I qdivides.IR p -1.The random.I seedused is also returned, so that scepticscan later confirm the computation..SH SOURCE.B /libinterp/ipint.c.br.B /libsec/port/probably_prime.c.br.B /libsec/port/dsaprimes.c.br.B /libsec/port/genprime.c.br.B /libsec/port/gensafeprime.c.br.B /libsec/port/genstrongprime.c.br.SH SEE ALSO.IR crypt-intro (2),.IR crypt-crypt (2),.IR crypt-dsagen (2),.IR crypt-gensk (2),.IR ipints (2)