首页
社区
课程
招聘
[求助]关于求大素数原根
发表于: 2010-12-10 09:49 9265

[求助]关于求大素数原根

2010-12-10 09:49
9265
本人是初学者 ,最近在做题目,算法中要用到大素数的 原根
哪位知道 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期)

上传的附件:
收藏
免费 0
支持
分享
最新回复 (1)
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
2
其实速度慢在1-3步, 那里要先算出一个素数P, 4-5才是算这个素数的原根. 如果你已经知道P, 只需要做第4/5两步就可以了.
另外, 1-3步生成的是一个2q+1(q是素数)型的素数(可以避免小因子攻击), 所以相对少些, 如果只需要一个任意素数, 单做第一步就足够了.
嗯, 还要补充一点, 要验证g是否为素数p的原根, 其实只要满足 g^(p-1) mod p != 1就可以了.
计算g^2和g^q是因为 p = 2q+1, 所以 g^(p-1) = g^(2q)  = (g^2)^q = (g^q)^2 mod p, 即g^2 mod p或g^q mod p为1的话, g^(p-1) mod p = 1.
2010-12-13 16:27
0
游客
登录 | 注册 方可回帖
返回
//