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),
