blob: 6ac4fa3324da2573feafbaac1af55354fa05d909 [file] [log] [blame]
 #include "os.h" #include #include /* Gordon's algorithm for generating a strong prime */ /* Menezes et al () Handbook, p.150 */ void genstrongprime(mpint *p, int n, int accuracy) { mpint *s, *t, *r, *i; if(n < 64) n = 64; s = mpnew(n/2); genprime(s, (n/2)-16, accuracy); t = mpnew(n/2); genprime(t, n-mpsignif(s)-32, accuracy); /* first r = 2it + 1 that's prime */ i = mpnew(16); r = mpnew(0); itomp(0x8000, i); mpleft(t, 1, t); /* 2t */ mpmul(i, t, r); /* 2it */ mpadd(r, mpone, r); /* 2it + 1 */ for(;;){ if(probably_prime(r, 18)) break; mpadd(r, t, r); /* r += 2t */ } /* p0 = 2(s**(r-2) mod r)s - 1 */ itomp(2, p); mpsub(r, p, p); mpexp(s, p, r, p); mpmul(s, p, p); mpleft(p, 1, p); mpsub(p, mpone, p); /* first p = p0 + 2irs that's prime */ itomp(0x8000, i); mpleft(r, 1, r); /* 2r */ mpmul(r, s, r); /* 2rs */ mpmul(r, i, i); /* 2irs */ mpadd(p, i, p); /* p0 + 2irs */ for(;;){ if(probably_prime(p, accuracy)) break; mpadd(p, r, p); /* p += 2rs */ } mpfree(i); mpfree(s); mpfree(r); mpfree(t); }