3 genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest \- prime number generation
11 .B #include <libsec.h>
14 int smallprimetest(mpint *p)
17 int probably_prime(mpint *p, int nrep)
20 void genprime(mpint *p, int n, int nrep)
23 void gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
26 void genstrongprime(mpint *p, int n, int nrep)
29 void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
32 Public key algorithms abound in prime numbers. The following routines
33 generate primes or test numbers for primality.
36 checks for divisibility by the first 10000 primes. It returns 0
39 is not divisible by the primes and \-1 if it is.
42 uses the Miller-Rabin test to test
44 It returns non-zero if
46 is probably prime. The probability of it not being prime is
52 bit prime. Since it uses the Miller-Rabin test,
54 is the repetition count passed to
63 of the multiplicative group of integers mod \fIp\fR;
64 there is a prime \fIq\fR such that \fIp-1=2*q\fR.
68 with the following properties:
70 (\fIp\fR-1)/2 is prime. Therefore
72 has a large prime factor,
76 has a large prime factor
79 has a large prime factor
86 using the NIST recommended algorithm for DSA primes.
90 The random seed used is also returned, so that skeptics
91 can later confirm the computation. Be patient; this is a
94 .B /usr/local/plan9/src/libsec