sys/src/libsec/port/genstrongprime.c

   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 }