GOAT_0x02
2021-08-29 12:02
采纳率: 0%
浏览 36

利用gmp库实现大数计算的一道题目

img

我的想法是,首先遍历大数n得到小于n的所有m值,然后对每个m值与n利用gmp库自带的gcd函数计算出最大公约数,如果是1,那么他们就是互素的,euler值就+1,可是遍历n是不现实的,n是个最高长达512比特的大数,加载一天都不知道能不能加载出来,这让我不知所措,请问到底如何实现这个题呢?

对于这道题,我的代码如下:

#include<gmp.h>
#include<iostream>
using namespace std;
int main()
{
    mpz_t p, q;
    mpz_init(p); //初始化q和p大素数
    mpz_init(q);

    //生成大素数算法
    gmp_randstate_t grt;
    gmp_randinit_default(grt); //设置随机数生成算法为默认
    gmp_randseed_ui(grt, time(NULL)); //设置随机化种子为当前时间

    mpz_urandomb(p, grt, 512);//随机生成一个0 ———(2^512)- 1(即512个bit上都是1)的一个大数
    mpz_urandomb(q, grt, 512);

    //利用mpz_t p, q生成素数mpz_t p, q
    mpz_nextprime(p, p);  //使用GMP自带的素数生成函数
    mpz_nextprime(q, q);
    gmp_printf("%ZX\n\n", p);
    gmp_printf("%ZX\n\n", q);

    //计算p*q的值,并存放在n中
    mpz_t n;
    mpz_init(n);
    mpz_mul(n, p, q); //计算p*q
    gmp_printf("%ZX\n\n", n);

    //计算euler值
    mpz_t euler,rop,m;
    mpz_init(euler);
    mpz_init(rop);
    mpz_init(m);

    //这里需要先遍历n,得到m值 (×) =》太理想化,遍历n同样是不现实的 
    while (1)
    {
        mpz_add_ui(m,m,1);//m=m+1
        if (mpz_cmp(m, n) > 0)
        {
            break;
        }

        //计算m与n之间的最大公约数,可以用gmp库自带的gcd函数
        mpz_gcd(rop, m, n);
        if (mpz_cmp_ui(rop, 1) == 0)//最大公约数为1,则为互素
        {
            //mpz_set(euler, euler + 1); 这个会直接报错
            mpz_add_ui(euler, euler, 1);//euler=euler+1
            gmp_printf("%ZX\n\n", euler);
        }

    }
    gmp_printf("%ZX\n\n", euler);

    //必须释放内存,不然就会报错
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(m);
    mpz_clear(n);
    mpz_clear(rop);
    mpz_clear(euler);

}

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题