ipints: genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime - prime number generation .EX 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 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.

/libinterp/ipint.c

/libsec/port/probably_prime.c

/libsec/port/dsaprimes.c

/libsec/port/genprime.c

/libsec/port/gensafeprime.c

/libsec/port/genstrongprime.c

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