5 // Gordon's algorithm for generating a strong prime
6 // Menezes et al () Handbook, p.150
8 genstrongprime(mpint *p, int n, int accuracy)
16 genprime(s, (n/2)-16, accuracy);
18 genprime(t, n-mpsignif(s)-32, accuracy);
20 // first r = 2it + 1 that's prime
24 mpleft(t, 1, t); // 2t
25 mpmul(i, t, r); // 2it
26 mpadd(r, mpone, r); // 2it + 1
28 if(probably_prime(r, 18))
30 mpadd(r, t, r); // r += 2t
33 // p0 = 2(s**(r-2) mod r)s - 1
41 // first p = p0 + 2irs that's prime
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
48 if(probably_prime(p, accuracy))
50 mpadd(p, r, p); // p += 2rs