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
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 }