NAME

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

SYNOPSIS

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

intsmallprimetest(mpint ∗p)

intprobably_prime(mpint ∗p, int nrep)

voidgenprime(mpint ∗p, int n, int nrep)

voidgensafeprime(mpint ∗p, mpint ∗alpha, int n, int accuracy)

voidgenstrongprime(mpint ∗p, int n, int nrep)

voidDSAprimes(mpint ∗q, mpint ∗p, uchar seed[SHA1dlen])

DESCRIPTION

Public key algorithms abound in prime numbers.  The following 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 factor, 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 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 algorithm.

SOURCE

­/sys/src/libsec

SEE ALSO

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

Plan 9  —  September 17, 2003