NAME

ipints: genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime - prime number generation

SYNOPSIS

include "ipints.m";
ipints := load IPints IPints->PATH;
IPint: import ipints;

probably_prime: fn(n: ref IPint, nrep: int): int;

genprime: fn(nbits: int, nrep: int): ref IPint;
gensafeprime: fn(nbits: int, nrep: int): (ref IPint, ref IPint);	# p, alpha
genstrongprime: fn(nbits: int, nrep: int): ref IPint;
DSAprimes: fn(): (ref IPint, ref IPint, array of byte);	# q, p, seed

DESCRIPTION

This set of functions in IPints (see ipints(2)) helps Limbo applications generate and test large prime numbers with relative efficiency. The numbers are all represented by IPint.

Probably_prime uses the Miller-Rabin test to test n. It returns true (non-zero) if P is probably prime. The probability of n not being prime is 1/4**nrep. If probably_prime returns false (zero), n is certainly not prime.

Genprime returns a random prime of length nbits. Since it uses the Miller-Rabin test, nrep is the repetition count passed to probably_prime.

Gensafeprime returns a tuple (p, alpha), where p is a prime of length nbits and alpha is a generator of the multiplicative group of integers mod p; there is a prime q such that p-1=2*q.

Genstrongprime returns 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 uses the NIST recommended algorithm for generating DSA primes and returns a tuple (q, p, seed), where p and q are primes, and q divides p-1. The random seed used is also returned, so that sceptics can later confirm the computation.

SOURCE

/libinterp/ipint.c
/libsec/port/probably_prime.c
/libsec/port/dsaprimes.c
/libsec/port/genprime.c
/libsec/port/gensafeprime.c
/libsec/port/genstrongprime.c

SEE ALSO

crypt-intro(2), crypt-crypt(2), crypt-dsagen(2), crypt-gensk(2), ipints(2)

IPINTS-GENPRIME(2 )

Rev:  Tue Mar 31 02:42:39 GMT 2015