大数运算

最近在做一个RSA签名认证有关的项目，涉及到了大数的计算。所谓大数，指的就是较大规模的高精度的数值。

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法来实现高精度数值的计算，这就产生了大数运算。

运算方法

大数往往都超过了计算机基本数据类型的表示范围，对于这些大数的运算，可以借助线性表来完成，将大数拆分后存储在线性表中。利用数组的连续性，将大数每一位上的数字单独取出放入对用的数组单元中，然后再对每一位做单独的运算。

但是，有一种叫做Python的神奇编程语言可以不用担忧大数运算溢出，因为Python支持“无限精度”的整数。上图

#取两个2048bit的数，用a,b表示
a='00b95f9da8f8db203fb679fa40911fb840fb02acd55ad88a0056782e676a71065d602e3e98a9ae28f2c26c419b601c508b6becf803fad54c8c141005fe9bebdcaf8fa88e7133b322bd5d643c1543e6d33eb4a9dfbede99d896da53c4f2ca2ecab25e2b1765e214ef45c2579256550e195220ce86a77f6da7cef55232760c173761568522ea85cbfc0c625fa51a5ef90de79871afdfccff18e0fcdd81a057e8ff0cc3633665366306deecce40aceef9da433bf50da06e1bdd12b81033329de99400fb09e1a00d2cfd9765e2862355346228b7e49e5e0b2e33098c29563dd877e43ef7e562c6fb99e01210851fcb5cf6dcc25d42fbdd607ad2b9a897c1f5786bde4d' 
b='00cded4cb44cae8eb24af380131f051c297e60fac04bb182b474c6492c6dc3f5797488f9118710e2cfc0a7032a4f5990a9c76b3e7d70a451f66585cda0e904dd8ecd1e0e5450fa1321eca772895c4d5c65da9cce1838028146a2817476794498b91e70c29ae6f4f32436371dea5bc825baa0b5154acdebbb611926ae6d17dcf3661a2ba379b8fe0ec66808e8c8dac30b679032c9daafb23803a4d956f00ed1924c233bf6cbdd2014dc4e6756b877c3f225891282dd3f9402a93d4b6a6b26ae5858f77d0daf08164434cb414edaa261427742c7c83dfd8458f36ac3e9548a93e653b07e116295d3d179f24cb5e1f6b53668d5d9a863f09162917003288b52745d81'

#将16进制字符串转换成int类型
int_a=int(a,16)
#int_a=23401236356371892932096630270509142082114328690571955976396432364865990979949522683690312347112281076047383014543749226300816695599296322551418425912774828987292623458114612564311138276393966434587133554696204495780402488685337525946471119145993517342348324347001073620326389431518218377648660796782738148550199876635140134930966766757293887935402105467090404751999510871198765175823653924000031537980247504424625877803612132534618237574426156035486876189199508876938431747713290846838841678737696987732536054988444111697742483990654660033075686136490297006435618400185001798305130411540121552123372876822978497338957L
int_b=int(b,16)
#int_b=25995869324973997927596980963612910098011971190804022977113499105179787120767287289098948978363555692588542251535160954844088631481542456855959767010752743336405445867650973723027156312221409291969441814754462812778971323907051940995172057494314351825554753218639755084012214121800815235248361487996691864932644077947603274773043614856019054244583001229014203528237573745316222626445814181948214407358574171231380185246718398242596619642935089410620207254051119549417162128033310707435037701722641116954950520598467842869352854670910254578745547982754902079497206268505331596009771841507688015324567998640382922743169L

#计算int_a+int_b

sum=int_a+int_b
#sum=49397105681345890859693611234122052180126299881375978953509931470045778100716809972789261325475836768635925266078910181144905327080838779407378192923527572323698069325765586287338294588615375726556575369450667308559373812592389466941643176640307869167903077565640828704338603553319033612897022284779430013482843954582743409704010381613312942179985106696104608280237084616514987802269468105948245945338821675656006063050330530777214857217361245446107083443250628426355593875746601554273879380460338104687486575586911954567095338661564914611821234119245199085932824668690333394314902253047809567447940875463361420082126L

速度?

Python固然可以进行大整数的计算，但是计算速度怎么样呢，我们使用一个1024位的大整数a进行了测试，进行了10000次的乘法运算，其中a=23769212733180789852543173334969864767440839510021864106522933617495425817873248853654373500854197188380263474699292780069149617563559557158850842032876695260241644991254908888823489478808130642209769616321338160626958521884372830379090457415654649204131807945455717749171573231709836253751812278185468165182801101532788809804419848953873506241798675719448891079611843862295748407378418438871600248330612581936707388898788310906777897020139142340441576524430808597472950372802927365163629929995101176030705906222537595215149626397344604095330687752853791824752879076446550161322839285796132431373437719385191193969729

m=1
for i in range(10000):
    m=m*a

上述测试代码需要的时间为249秒（4分钟）。这么慢的速度怎么能忍，于是查阅资料发现Python有个叫gmpy2的扩展库，是对GMP（一个开源的高精度运算库）的封装，它的前身是gmpy。经过作者的调整和封装，使得gmpy2的使用大大简化。再Python中使用gmpy2，跟在C/C++中使用GMP相比，至少有以下优势：

1. 简化的函数名：作者对GMP的大量函数名做了简化，比如素数的概率性测试，在C/C++中，命令是`mpz_probab_prime_p`，在gmpy2中，只需要简单的`is_prime`；
2. 方便的运算符重载：如果在C/C++中，两个mpz整数相加，需要用`mpz_add(z_i,z_i,z_o)`，在gpy2中，只需要用`+`号即可，更一般的，将一个mpz整数与int整数相加，也只需要`+`号，类似的还有减、乘、除、求模、乘方等。

使用gmpy2对a进行10000次乘法运算

import gmpy2 as gp
m=gp.mpz(1)
for i in range(10000):
    m=m*a

时间仅用了34秒，gmpy2真是Python大数计算的利器啊。

具体的gmpy2教程

Linux安装gmpy2

安装gmpy2需要依赖库GMP、MPRF、MPC，下面依次解释如何安装

• 安装MPC 在终端直接安装 sudo apt-get install libmpc-dev
• 安装GMP 同MPC一样，通过命令直接在终端安装 sudo apt-get install libgmp-dev
• 安装MPRF 官网下载MPRF的源码，自己编译安装

tar -jxvf mpfr-4.0.1.tar.bz2 && cd mpfr-4.0.1
./configure
make && make check $$ make install