genstrongprime.c (1081B)
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 }