本人是初学者 ，最近在做题目，算法中要用到大素数的 原根
哪位知道 miracl库中是否有什么函数可以快速求大素数原根 ？？？？
如果采用下列算法来求原根 效率不高 计算128位的p要花很长时间 有没有什么方法可以优化？？
step 1 随机生成一个大素数q
step 2 令p=2*q+1
step 3 检测P是否是素数 ，若非素数 则转 step 1
step 4 随机产生一个随机数g,1<g<p-1
step 5 计算g^2mod p 与 g^q mod p ，若g^2mod p 与 g^q mod p 计算值均不为 1 ，即 g 为素数p的原根，否则转 step 4 。
以下是代码 C 语言 基于miracl库
#include "stdio.h"
#include "miracl.h"
#include "time.h"
void main()
{
int k=2,m=0;
unsigned long seed;
big p,q,g,k2,kq,k1;
clock_t t_begin,t_end;
miracl *mip=mirsys(5000,16);
mip->IOBASE=16;
p=mirvar(0);
q=mirvar(0);
g=mirvar(0);
k2=mirvar(0);
kq=mirvar(0);
k1=mirvar(0);
seed=time(0);
convert(1,k1);
printf("开始计算大素数p的本原根");
t_begin=clock();
gprime(15000);
do{
do{
seed=seed++;
irand(seed);
bigdig(128,16,q); //产生128位16进制的随机数q
}while(!isprime(q));
//p=2*q+1
premult(q,2,p);
incr(p,1,p);
}while(!isprime(p));
printf("\n p=");
cotnum(p,stdout);
do{ //产生随机数 g , 1<= g < p
do{
seed++;
irand(seed);
bigrand(p,g);
}while(compare(g,k1)==0);
power(g,k,p,k2); //g^k mod p =k2
powmod(g,q,p,kq); //g^q mod p =kq
if((compare(k2,k1)==0)||(compare(kq,k1)==0))
m=1;
}while(m);
printf("\n原根g=");
cotnum(g,stdout);
t_end=clock();
printf("花费时间 %d ms \n",t_end-t_begin);
}
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
