genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest - prime number generation #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])

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.

/sys/src/libsec aes (2) blowfish (2), des (2), elgamal (2), rsa (2)