tprime.3 - plan9port - [fork] Plan 9 from user space
 (HTM) git clone git://src.adamsgaard.dk/plan9port
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) LICENSE
       ---
       tprime.3 (1965B)
       ---
            1 .TH PRIME 3
            2 .SH NAME
            3 genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest  \- prime number generation
            4 .SH SYNOPSIS
            5 .B #include <u.h>
            6 .br
            7 .B #include <libc.h>
            8 .br
            9 .B #include <mp.h>
           10 .br
           11 .B #include <libsec.h>
           12 .PP
           13 .B
           14 int        smallprimetest(mpint *p)
           15 .PP
           16 .B
           17 int        probably_prime(mpint *p, int nrep)
           18 .PP
           19 .B
           20 void        genprime(mpint *p, int n, int nrep)
           21 .PP
           22 .B
           23 void        gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
           24 .PP
           25 .B
           26 void        genstrongprime(mpint *p, int n, int nrep)
           27 .PP
           28 .B
           29 void        DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
           30 .SH DESCRIPTION
           31 .PP
           32 Public key algorithms abound in prime numbers.  The following routines
           33 generate primes or test numbers for primality.
           34 .PP
           35 .I Smallprimetest
           36 checks for divisibility by the first 10000 primes.  It returns 0
           37 if
           38 .I p
           39 is not divisible by the primes and \-1 if it is.
           40 .PP
           41 .I Probably_prime
           42 uses the Miller-Rabin test to test
           43 .IR p .
           44 It returns non-zero if
           45 .I P
           46 is probably prime.  The probability of it not being prime is
           47 1/4**\fInrep\fR.
           48 .PP
           49 .I Genprime
           50 generates a random
           51 .I n
           52 bit prime.  Since it uses the Miller-Rabin test,
           53 .I nrep
           54 is the repetition count passed to
           55 .IR probably_prime .
           56 .I Gensafegprime
           57 generates an
           58 .IR n -bit
           59 prime
           60 .I p
           61 and a generator
           62 .I alpha
           63 of the multiplicative group of integers mod \fIp\fR;
           64 there is a prime \fIq\fR such that \fIp-1=2*q\fR.
           65 .I Genstrongprime
           66 generates a prime,
           67 .IR p ,
           68 with the following properties:
           69 .IP \-
           70 (\fIp\fR-1)/2 is prime.  Therefore
           71 .IR p -1
           72 has a large prime factor,
           73 .IR p '.
           74 .IP \-
           75 .IR p '-1
           76 has a large prime factor
           77 .IP \-
           78 .IR p +1
           79 has a large prime factor
           80 .PP
           81 .I DSAprimes
           82 generates two primes,
           83 .I q
           84 and
           85 .IR p,
           86 using the NIST recommended algorithm for DSA primes.
           87 .I q
           88 divides
           89 .IR p -1.
           90 The random seed used is also returned, so that skeptics
           91 can later confirm the computation.  Be patient; this is a
           92 slow algorithm.
           93 .SH SOURCE
           94 .B \*9/src/libsec
           95 .SH SEE ALSO
           96 .MR aes (3)
           97 .MR blowfish (3) ,
           98 .MR des (3) ,
           99 .MR elgamal (3) ,
          100 .MR rsa (3) ,