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