GMP库使用以及java中的BigInteger和BigDecimal

￡神魔★判官ぃ 2024-03-16 14:04 46阅读 0赞

#### 一、GMP介绍和安装 ####

GMP library全称是GNU Multiple Precision Arithmetic Library，即GNU高精度算术运算库。在网络安全技术领域中各种加密算法的软件实现始终有一个共同话题是如何在普通的PC机上实现大数运算。普通的PC机内部字长最多时32位或64位，但各种加密算法中为了达到一定安全强度，都要求在128位、512位或1024位字长下进行加减乘除等数学运算，这叫做“**大数运算**”。

在此前提下，如何在普通的PC机上高效快速的实现大数运算成为加密算法在普通PC机上软件实现的重要问题。如python等语言都内建大数计算机制，但C/C++语言既没有内建大数运算机制，也没有对应的标准库实现。

GMP大数库是GUN项目的一部分，诞生于1991年，作为一个任意精度的大整数运算库，它包含了任意精度的整数、浮点数的各种基础运算操作。它是一个C语言库，并提供了C++的包装类，主要应用于密码学应用和研究、互联网安全应用、代数系统、计算代数研究等。

GMP库运行速度非常快，官网上称自己是地球上最快的大数库，但GMP只提供了基础数学运算，并没有提供密码学的相关运算。

**1、在Mac上安装**

到[官网下载][Link 1]相应的包。

# Mac下方便解压，直接下载 gmp-6.2.0.tar.xz 版本
    # 解压 
    $ tar -xvf gmp-6.2.0.tar
    
    # 编译
    $ cd gmp-6.2.0
    $ ./configure --enable-cxx
    $ make -j4  # 4 核心编译速度更快 也可以直接 make
    
    # 对编译进行自测
    $ make check
    
    # 安装 默认路径为/usr/local
    $ sudo make install

注：由于GMP是C语言库，但也提供了C++的包装类，在编译时，如果要增加C++支持，**./configure**时加上**--enable-cxx**参数，这样才能使用c++库**gmpxx.h**。

**2、使用库**

链接到 libgmp 库，使用选项 -lgmp：

gcc myprogram.c -lgmp

c++函数在 libgmpxx 库中，因此需要额外的编译选项：

g++ mycxxprog.cc -lgmpxx -lgmp

**3、示例**

**1）整型运算：**

testgmp.cpp：

#include <iostream>
    #include <gmpxx.h>
    using namespace std;
    
    int main()
    {
        mpz_t a,b,c,d;  // define
        mpz_init(a);  // initialize
        mpz_init(b);
        mpz_init(c);
        mpz_init(d);
        gmp_scanf("%Zd%Zd",a,b);  // input
        mpz_add(c,a,b);  // compute c = a + b
        gmp_printf("%Zd\n",c);  // output
        mpz_mul(d,a,b);  // compute d = a * b
        gmp_printf("%Zd\n",d);  // output
        mpz_clear(a);  // clear memory
        mpz_clear(b);
        mpz_clear(c);
        mpz_clear(d);
        return 0;
    }

编译、运行

# 编译
    $ g++ -o testgmp.out testgmp.cpp -lgmpxx -lgmp
    
    # 运行
    $ ./testgmp.out
    324327543564685049860389045809768327483265873264578346593489
    100000000000000000000000000000000000000000000000000000000001

输出：

424327543564685049860389045809768327483265873264578346593490
    3243275435646850498603890458097683274832658732645783465934922432754356468504986038904580976832748326587326457

**2）浮点型运算：**

testgmp2.cpp

#include <iostream>
    #include <gmpxx.h>
    using namespace std;
    
    int main()
    {
        mpf_set_default_prec(64); // 默认精度，即小数点后精确多少位
        mpf_t a,b,c,d;  // define
    
        mpf_init(a);  // initialize
        mpf_init(b);
        mpf_init(c);
        mpf_init(d);
    
        gmp_scanf("%Ff%Ff",a,b);  // input
        mpf_add(c,a,b);  // compute c = a + b
        gmp_printf("%Ff\n",c);  // output
        mpf_mul(d,a,b);  // compute d = a * b
        gmp_printf("%Ff\n",d);  // output
        mpf_clear(a);  // clear memory
        mpf_clear(b);
        mpf_clear(c);
        mpf_clear(d);
        return 0;
    }

编译、运行

$ g++ -o testgmp2.out testgmp2.cpp -lgmpxx -lgmp
    $ ./testgmp2.out
    9876543.123456
    123456.987654

输出

10000000.111110
    1219328262456.705990

**4、GMP库介绍**

*  在线文档：[Top (GNU MP 6.2.1)][Top _GNU MP 6.2.1]
 *  官方手册：[https://gmplib.org/gmp-man-6.2.1.pdf][https_gmplib.org_gmp-man-6.2.1.pdf]

**4.1）数据类型：**

*  mpz\_t（整数） mpz\_开头
 *  mpq\_t（有理数） mpq\_开头
 *  mpf\_t（浮点数） mpf\_开头

**4.2）使用步骤：（以浮点型为例）**

1）声明变量：

mpf_t fnum;

2）初始化变量：

mpf_init(fnum); //或mpf_init(fnum,20)，此函数指针对类型mpf_t有效

3）变量赋值：

mpf_set_str(fnum,"1.23",10);    //以10为进制数，表示浮点数的字符串来赋值fnum
    
    //mpf_set_str的原型
    int mpf_init_set_str (mpf_ptr, const char *, int);
    其中三个参数表示为多精度浮点数变量、字符串、进制。

4）变量计算：

mpf_mul(fnum,fnum,tmp);    //fnum和tmp都是mpf_t类型的变量

5）释放变量：

mpf_clear(fnum);

**4.3）常用方法：**

*  加法：void mpz\_add(mpz\_t rop, mpz\_t op1, mpz\_t op2); //rop = op1 + op2
 *  减法：void mpz\_sub(mpz\_t rop, mpz\_t op1, mpz\_t op2); //rop = op1 - op2
 *  乘法：void mpz\_mul(mpz\_t rop, mpz\_t op1, mpz\_t op2); //rop = op1 \* op2
 *  除法：void mpz\_cdiv\_q (mpz\_t q, mpz\_t n, mpz\_t d); //q = n/d,这个有很多种类型，具体的看使用手册
 *  幂运算：void mpz\_pow\_ui (mpz\_t rop, mpz\_t base, unsigned long int exp); //rop = base^exp
 *  开方：void mpz\_sqrt (mpz\_t rop, mpz\_t op); //rop = op开方的向下取整

**5、应用：（RSA加密）**

#include <iostream>
    #include <gmpxx.h>
    #include <cstdlib>
    
    using namespace std;
    
    mpz_class randbits(int bits) // base = 2
    {
        gmp_randclass a(gmp_randinit_default);
        a.seed(rand());
        mpz_class l(bits);
        return a.get_z_bits(l);
    }
    
    inline mpz_class randprime(int bits)
    {
        mpz_class a = randbits(bits);
        mpz_class ret;
        mpz_nextprime(ret.get_mpz_t(), a.get_mpz_t());
        return ret;
    }
    
    void setKey(mpz_class &n, mpz_class &e, mpz_class &d, const int nbits, int ebits = 16)
    {
        if (nbits / 2 <= ebits)
        {
            ebits = nbits / 2;
        }
        mpz_class p = randprime(nbits / 2); //随机取p
        mpz_class q = randprime(nbits / 2); //随机取q
        n = q * p;                          //计算n=p*q
        mpz_class fn = (p - 1) * (q - 1);   //计算欧拉数
        mpz_class gcd;
        do
        {
            e = randprime(ebits);           //随机取e
            mpz_gcd(gcd.get_mpz_t(), e.get_mpz_t(), fn.get_mpz_t());       //判断gcd(e,fn)=1是否成立
        } while (gcd != 1);
        //mpz_gcdext(g, s, t, a, b)： g = as + bt
        mpz_gcdext(p.get_mpz_t(), d.get_mpz_t(), q.get_mpz_t(), e.get_mpz_t(), fn.get_mpz_t()); //计算d=e^{-1} mod fn
    }
    
    inline mpz_class encrypt(const mpz_class &m, const mpz_class &e, const mpz_class &n)
    {
        mpz_class ret;
        mpz_powm(ret.get_mpz_t(), m.get_mpz_t(), e.get_mpz_t(), n.get_mpz_t()); //ret=m^e mod n
        return ret;
    }
    
    inline mpz_class decrypt(const mpz_class &c, const mpz_class &d, const mpz_class &n)
    {
        return encrypt(c, d, n);    //m=c^d mod n
    }
    
    int main()
    {
        int nbits;
        cout << "输入大数比特数:";
        cin >> nbits;
        mpz_class n, e, d;
        setKey(n, e, d, nbits);         //密钥生成
        cout << "公钥:(e=" << e.get_str() << ", n=" << n.get_str() << ")" << endl;
        cout << "私钥:(d=" << d.get_str() << ", n=" << n.get_str() << ")" << endl;
    
        cout << "输入加密数据:";
        string s;
        cin >> s;
    
        mpz_class m(s);
        mpz_class c;
        c = encrypt(m, e, n);       //加密
        cout << "加密后:" << c.get_str() << endl;
        c = decrypt(c, d, n);       //解密
        cout << "解密后:" << c.get_str() << endl;
        if (c == m)
            cout << "加/解密成功!" << endl
                 << endl;
        else
            cout << "加/解密失败!" << endl
                 << endl;
    
        string q;
        cout << "是否继续(Y/N):";
        cin >> q;
        if (q == "y" || q == "Y")
            main();
        return 0;
    }

#### 二、java中的BigInteger和BigDecimal ####

**1、BigInteger：**

在Java中，由CPU原生提供的整型最大范围是64位long型整数。使用long型整数可以直接通过CPU指令进行计算，速度非常快。

如果我们使用的整数范围超过了long型怎么办？这个时候，就只能用软件来模拟一个大整数。java.math.BigInteger就是用来表示任意大小的整数。BigInteger内部用一个int\[\]数组来模拟一个非常大的整数。和long型整数运算比，BigInteger不会有范围限制，但缺点是速度比较慢。

private static void test() {
    	BigInteger a = new BigInteger("324327543564685049860389045809768327483265873264578346593489");
    	BigInteger b = new BigInteger("100000000000000000000000000000000000000000000000000000000001");
    	
    	BigInteger c = a.add(b);
    	BigInteger d = a.multiply(b);
    	System.out.println(c.toString());//424327543564685049860389045809768327483265873264578346593490
    	System.out.println(d.toString());//32432754356468504986038904580976832748326587326457834659349224327543564685049860389045809768327483265873264578346593489
    }

**2、BigDecimal：**

和BigInteger类似，BigDecimal可以表示一个任意大小且精度完全准确的浮点数。如果查看BigDecimal的源码，可以发现，实际上一个BigDecimal是通过一个BigInteger和一个scale来表示的，即BigInteger表示一个完整的整数，而scale表示小数位数。

**1）除法运算：**

对BigDecimal做加、减、乘时，精度不会丢失，但是做除法时，存在无法除尽的情况，这时，就必须指定精度以及如何进行截断：

BigDecimal d1 = new BigDecimal("123.456");
    BigDecimal d2 = new BigDecimal("23.456789");
    BigDecimal d3 = d1.divide(d2, 10, RoundingMode.HALF_UP); // 保留10位小数并四舍五入
    BigDecimal d4 = d1.divide(d2); // 报错：ArithmeticException，因为除不尽

**2）比较：**

在比较两个BigDecimal的值是否相等时，要特别注意，使用equals()方法不但要求两个BigDecimal的值相等，还要求它们的scale()相等：

BigDecimal d1 = new BigDecimal("123.456");
    BigDecimal d2 = new BigDecimal("123.45600");
    System.out.println(d1.equals(d2)); // false,因为scale不同
    System.out.println(d1.equals(d2.stripTrailingZeros())); // true,因为d2去除尾部0后scale变为2
    System.out.println(d1.compareTo(d2)); // 0

所以，必须使用`compareTo()`方法来比较，它根据两个值的大小分别返回负数、正数和`0`，分别表示小于、大于和等于。

**3）求余数**

BigDecimal n = new BigDecimal("12.345");
    BigDecimal m = new BigDecimal("0.12");
    BigDecimal[] dr = n.divideAndRemainder(m);
    System.out.println(dr[0]); // 102
    System.out.println(dr[1]); // 0.105

调用divideAndRemainder()方法时，返回的数组包含两个BigDecimal，分别是商和余数，其中商总是整数，余数不会大于除数。我们可以利用这个方法判断两个BigDecimal是否是整数倍数：

BigDecimal n = new BigDecimal("12.75");
    BigDecimal m = new BigDecimal("0.15");
    BigDecimal[] dr = n.divideAndRemainder(m);
    if (dr[1].signum() == 0) {
        // n是m的整数倍
    }

[  
https://www.cnblogs.com/pam-sh/p/17368429.html][https_www.cnblogs.com_pam-sh_p_17368429.html]

[C/C++ gmp库之浮点数实例 | 织梦先生][C_C_ gmp_ _]

[Link 1]: https://gmplib.org/#DOWNLOAD
[Top _GNU MP 6.2.1]: https://gmplib.org/manual/
[https_gmplib.org_gmp-man-6.2.1.pdf]: https://gmplib.org/gmp-man-6.2.1.pdf
[https_www.cnblogs.com_pam-sh_p_17368429.html]: https://www.cnblogs.com/pam-sh/p/17368429.html
[C_C_ gmp_ _]: http://mrdede.com/?p=4294