1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
<head>
<title>prime(3) - Plan 9 from User Space</title>
<meta content="text/html; charset=utf-8" http-equiv=Content-Type>
</head>
<body bgcolor=#ffffff>
<table border=0 cellpadding=0 cellspacing=0 width=100%>
<tr height=10><td>
<tr><td width=20><td>
<tr><td width=20><td><b>PRIME(3)</b><td align=right><b>PRIME(3)</b>
<tr><td width=20><td colspan=2>
<br>
<p><font size=+1><b>NAME </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime,
smallprimetest – prime number generation<br>
</table>
<p><font size=+1><b>SYNOPSIS </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<tt><font size=+1>#include <u.h><br>
#include <libc.h><br>
#include <mp.h><br>
#include <libsec.h>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int smallprimetest(mpint *p)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int probably_prime(mpint *p, int nrep)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void genprime(mpint *p, int n, int nrep)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void genstrongprime(mpint *p, int n, int nrep)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])<br>
</font></tt>
</table>
<p><font size=+1><b>DESCRIPTION </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
Public key algorithms abound in prime numbers. The following routines
generate primes or test numbers for primality.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Smallprimetest</i> checks for divisibility by the first 10000 primes.
It returns 0 if <i>p</i> is not divisible by the primes and –1 if it is.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Probably_prime</i> uses the Miller-Rabin test to test <i>p</i>. It returns
non-zero if <i>P</i> is probably prime. The probability of it not being
prime is 1/4**<i>nrep</i>.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Genprime</i> generates a random <i>n</i> bit prime. Since it uses the Miller-Rabin
test, <i>nrep</i> is the repetition count passed to <i>probably_prime</i>. <i>Gensafegprime</i>
generates an <i>n</i>-bit prime <i>p</i> and a generator <i>alpha</i> of the multiplicative
group of integers mod <i>p</i>; there is a prime <i>q</i> such that <i>p-1=2*q</i>.
<i>Genstrongprime</i> generates a
prime, <i>p</i>, with the following properties:<br>
– (<i>p</i>-1)/2 is prime. Therefore <i>p</i>-1 has a large prime factor, <i>p</i>’.<br>
–<i>p</i>’-1 has a large prime factor<br>
–<i>p</i>+1 has a large prime factor
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>DSAprimes</i> generates two primes, <i>q</i> and <i>p,</i> using the NIST recommended
algorithm for DSA primes. <i>q</i> divides <i>p</i>-1. The random seed used
is also returned, so that skeptics can later confirm the computation.
Be patient; this is a slow algorithm.<br>
</table>
<p><font size=+1><b>SOURCE </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<tt><font size=+1>/usr/local/plan9/src/libsec<br>
</font></tt>
</table>
<p><font size=+1><b>SEE ALSO </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<a href="../man3/aes.html"><i>aes</i>(3)</a> <a href="../man3/blowfish.html"><i>blowfish</i>(3)</a>, <a href="../man3/des.html"><i>des</i>(3)</a>, <a href="../man3/elgamal.html"><i>elgamal</i>(3)</a>, <a href="../man3/rsa.html"><i>rsa</i>(3)</a>,<br>
</table>
<td width=20>
<tr height=20><td>
</table>
<!-- TRAILER -->
<table border=0 cellpadding=0 cellspacing=0 width=100%>
<tr height=15><td width=10><td><td width=10>
<tr><td><td>
<center>
<a href="../../"><img src="../../dist/spaceglenda100.png" alt="Space Glenda" border=1></a>
</center>
</table>
<!-- TRAILER -->
</body></html>
|