PRIME(2)                                                 PRIME(2)

          genprime, gensafeprime, genstrongprime, DSAprimes,
          probably_prime, smallprimetest  - prime number generation

          #include <u.h>
          #include <libc.h>
          #include <mp.h>
          #include <libsec.h>

          int  smallprimetest(mpint *p)

          int  probably_prime(mpint *p, int nrep)

          void genprime(mpint *p, int n, int nrep)

          void gensafeprime(mpint *p, mpint *alpha, int n, int accu-

          void genstrongprime(mpint *p, int n, int nrep)

          void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])

          Public key algorithms abound in prime numbers.  The follow-
          ing routines generate primes or test numbers for primality.

          Smallprimetest checks for divisibility by the first 10000
          primes.  It returns 0 if p is not divisible by the primes
          and -1 if it is.

          Probably_prime uses the Miller-Rabin test to test p. It
          returns non-zero if P is probably prime.  The probability of
          it not being prime is 1/4**nrep.

          Genprime generates a random n bit prime.  Since it uses the
          Miller-Rabin test, nrep is the repetition count passed to
          probably_prime. Gensafegprime generates an n-bit prime p and
          a generator alpha of the multiplicative group of integers
          mod p; there is a prime q such that p-1=2*q.  Genstrongprime
          generates a prime, p, with the following properties:

          -    (p-1)/2 is prime.  Therefore p-1 has a large prime fac-
               tor, p'.

          -    p'-1 has a large prime factor

          -    p+1 has a large prime factor

          DSAprimes generates two primes, q and p, using the NIST

     Page 1                       Plan 9             (printed 7/22/24)

     PRIME(2)                                                 PRIME(2)

          recommended algorithm for DSA primes.  q divides p-1. The
          random seed used is also returned, so that skeptics can
          later confirm the computation.  Be patient; this is a slow


          aes(2) blowfish(2), des(2), elgamal(2), rsa(2)

     Page 2                       Plan 9             (printed 7/22/24)