# FreeBSD Manual Pages

```PRIME(3)		   Library Functions Manual		      PRIME(3)

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-Ra-
bin  test, nrep is the repetition count passed to probably_prime.  Gen-
safegprime generates an n-bit prime p and a generator alpha of the mul-
tiplicative  group  of  integers	 mod  p;  there	is a prime q such that
p-1=2*q.	 Genstrongprime	generates a prime, p, with the following prop-
erties:

-      (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 al-
gorithm for DSA primes.	q divides p-1.	The random seed	used  is  also
returned,  so  that skeptics can	later confirm the computation.	Be pa-
tient; this is a	slow algorithm.

SOURCE
/usr/local/plan9/src/libsec