tgenstrongprime.c - plan9port - [fork] Plan 9 from user space
  HTML git clone git://src.adamsgaard.dk/plan9port
   DIR Log
   DIR Files
   DIR Refs
   DIR README
   DIR LICENSE
       ---
       tgenstrongprime.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 }