ref: 3c6be4750088503e4387a3b3b4910354c89913ed
dir: /libsec/gensafeprime.c/
#include "os.h"
#include <mp.h>
#include <libsec.h>
// find a prime p of length n and a generator alpha of Z^*_p
// Alg 4.86 Menezes et al () Handbook, p.164
void
gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
{
mpint *q, *b;
q = mpnew(n-1);
while(1){
genprime(q, n-1, accuracy);
mpleft(q, 1, p);
mpadd(p, mpone, p); // p = 2*q+1
if(probably_prime(p, accuracy))
break;
}
// now find a generator alpha of the multiplicative
// group Z*_p of order p-1=2q
b = mpnew(0);
while(1){
mprand(n, genrandom, alpha);
mpmod(alpha, p, alpha);
mpmul(alpha, alpha, b);
mpmod(b, p, b);
if(mpcmp(b, mpone) == 0)
continue;
mpexp(alpha, q, p, b);
if(mpcmp(b, mpone) != 0)
break;
}
mpfree(b);
mpfree(q);
}