|
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
SEE ALSO
|
|
