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
|
#include "os.h"
#include <mp.h>
#include <libsec.h>
// Gordon's algorithm for generating a strong prime
// Menezes et al () Handbook, p.150
void
genstrongprime(mpint *p, int n, int accuracy)
{
mpint *s, *t, *r, *i;
if(n < 64)
n = 64;
s = mpnew(n/2);
genprime(s, (n/2)-16, accuracy);
t = mpnew(n/2);
genprime(t, n-mpsignif(s)-32, accuracy);
// first r = 2it + 1 that's prime
i = mpnew(16);
r = mpnew(0);
itomp(0x8000, i);
mpleft(t, 1, t); // 2t
mpmul(i, t, r); // 2it
mpadd(r, mpone, r); // 2it + 1
for(;;){
if(probably_prime(r, 18))
break;
mpadd(r, t, r); // r += 2t
}
// p0 = 2(s**(r-2) mod r)s - 1
itomp(2, p);
mpsub(r, p, p);
mpexp(s, p, r, p);
mpmul(s, p, p);
mpleft(p, 1, p);
mpsub(p, mpone, p);
// first p = p0 + 2irs that's prime
itomp(0x8000, i);
mpleft(r, 1, r); // 2r
mpmul(r, s, r); // 2rs
mpmul(r, i, i); // 2irs
mpadd(p, i, p); // p0 + 2irs
for(;;){
if(probably_prime(p, accuracy))
break;
mpadd(p, r, p); // p += 2rs
}
mpfree(i);
mpfree(s);
mpfree(r);
mpfree(t);
}
|