tgensafeprime.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
       ---
       tgensafeprime.c (756B)
       ---
            1 #include "os.h"
            2 #include <mp.h>
            3 #include <libsec.h>
            4 
            5 /* find a prime p of length n and a generator alpha of Z^*_p */
            6 /* Alg 4.86 Menezes et al () Handbook, p.164 */
            7 void
            8 gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
            9 {
           10         mpint *q, *b;
           11 
           12         q = mpnew(n-1);
           13         while(1){
           14                 genprime(q, n-1, accuracy);
           15                 mpleft(q, 1, p);
           16                 mpadd(p, mpone, p); /* p = 2*q+1 */
           17                 if(probably_prime(p, accuracy))
           18                         break;
           19         }
           20         /* now find a generator alpha of the multiplicative */
           21         /* group Z*_p of order p-1=2q */
           22         b = mpnew(0);
           23         while(1){
           24                 mprand(n, genrandom, alpha);
           25                 mpmod(alpha, p, alpha);
           26                 mpmul(alpha, alpha, b);
           27                 mpmod(b, p, b);
           28                 if(mpcmp(b, mpone) == 0)
           29                         continue;
           30                 mpexp(alpha, q, p, b);
           31                 if(mpcmp(b, mpone) != 0)
           32                         break;
           33         }
           34         mpfree(b);
           35         mpfree(q);
           36 }