harvey/sys/man/2/prime

.TH PRIME 2
.SH NAME
genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest  \- prime number generation
.SH SYNOPSIS
.B #include <u.h>
.br
.B #include <libc.h>
.br
.B #include <mp.h>
.br
.B #include <libsec.h>
.PP
.B
int	smallprimetest(mpint *p)
.PP
.B
int	probably_prime(mpint *p, int nrep)
.PP
.B
void	genprime(mpint *p, int n, int nrep)
.PP
.B
void	gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
.PP
.B
void	genstrongprime(mpint *p, int n, int nrep)
.PP
.B
void	DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
.SH DESCRIPTION
.PP
Public key algorithms abound in prime numbers.  The following routines
generate primes or test numbers for primality.
.PP
.I Smallprimetest
checks for divisibility by the first 10000 primes.  It returns 0
if
.I p
is not divisible by the primes and \-1 if it is.
.PP
.I Probably_prime
uses the Miller-Rabin test to test
.IR p .
It returns non-zero if
.I P
is probably prime.  The probability of it not being prime is
1/4**\fInrep\fR.
.PP
.I Genprime
generates a random
.I n
bit prime.  Since it uses the Miller-Rabin test,
.I nrep
is the repetition count passed to
.IR probably_prime .
.I Gensafegprime
generates an
.IR n -bit
prime
.I p
and a generator
.I alpha
of the multiplicative group of integers mod \fIp\fR;
there is a prime \fIq\fR such that \fIp-1=2*q\fR.
.I Genstrongprime
generates a prime,
.IR p ,
with the following properties:
.IP \-
.IR p -1
has a large prime factor,
.IR p '.
A large factor is one close to 1/2
the bit length of
.IR p .
.IP \-
.IR p '-1
has a large prime factor
.IP \-
.IR p +1
has a large prime factor
.IP \-
(\fIp\fR-1)/2 is prime
.PP
.I DSAprimes
generates two primes,
.I q
and
.IR p,
using the NIST recommended algorithm for DSA primes.
.I q
divides
.IR p -1.
The random seed used is also returned, so that skeptics
can later confirm the computation.  Be patient; this is a
slow algorithm.
.SH SOURCE
.B /sys/src/libsec
.SH SEE ALSO
.IR aes (2)
.IR blowfish (2),
.IR des (2),
.IR elgamal (2),
.IR rsa (2),