glenda.party
term% ls -F
term% cat index.txt
PRIME(2)                      System Calls Manual                     PRIME(2)



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 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
       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
       /sys/src/libsec

SEE ALSO
       aes(2) blowfish(2), des(2), elgamal(2), rsa(2)



                                                                      PRIME(2)