1 #include "os.h"
2 #include <mp.h>
3 #include <libsec.h>
4
5 // Gordon's algorithm for generating a strong prime
6 // Menezes et al () Handbook, p.150
7 void
genstrongprime(mpint * p,int n,int accuracy)8 genstrongprime(mpint *p, int n, int accuracy)
9 {
10 mpint *s, *t, *r, *i;
11
12 if(n < 64)
13 n = 64;
14
15 s = mpnew(n/2);
16 genprime(s, (n/2)-16, accuracy);
17 t = mpnew(n/2);
18 genprime(t, n-mpsignif(s)-32, accuracy);
19
20 // first r = 2it + 1 that's prime
21 i = mpnew(16);
22 r = mpnew(0);
23 itomp(0x8000, i);
24 mpleft(t, 1, t); // 2t
25 mpmul(i, t, r); // 2it
26 mpadd(r, mpone, r); // 2it + 1
27 for(;;){
28 if(probably_prime(r, 18))
29 break;
30 mpadd(r, t, r); // r += 2t
31 }
32
33 // p0 = 2(s**(r-2) mod r)s - 1
34 itomp(2, p);
35 mpsub(r, p, p);
36 mpexp(s, p, r, p);
37 mpmul(s, p, p);
38 mpleft(p, 1, p);
39 mpsub(p, mpone, p);
40
41 // first p = p0 + 2irs that's prime
42 itomp(0x8000, i);
43 mpleft(r, 1, r); // 2r
44 mpmul(r, s, r); // 2rs
45 mpmul(r, i, i); // 2irs
46 mpadd(p, i, p); // p0 + 2irs
47 for(;;){
48 if(probably_prime(p, accuracy))
49 break;
50 mpadd(p, r, p); // p += 2rs
51 }
52
53 mpfree(i);
54 mpfree(s);
55 mpfree(r);
56 mpfree(t);
57 }
58