prime.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) ,