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 accuracy) 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 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:
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) |