Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
.TH PRIME 2
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 /sys/src/libsec
95 
.SH SEE ALSO
96 
.IR aes (2)
97 
.IR blowfish (2),
98 
.IR des (2),
99 
.IR elgamal (2),
100 
.IR rsa (2)