PRIME(3) PRIME(3)
NAME
genprime, gensafeprime, genstrongprime, DSAprimes,
probably_prime, smallprimetest - prime number generation
SYNOPSIS
#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-
racy)
void genstrongprime(mpint *p, int n, int nrep)
void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
DESCRIPTION
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 11/18/24)
PRIME(3) PRIME(3)
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
/usr/local/plan9/src/libsec
SEE ALSO
aes(3) blowfish(3), des(3), elgamal(3), rsa(3),
Page 2 Plan 9 (printed 11/18/24)