PRIME(2)PRIME(2)
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:
–
(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
aes(2)
blowfish(2),
des(2),
elgamal(2),
rsa(2)