C++实现大整数运算包（加、减、乘、除、幂模、GCD、乘法逆）

2019-04-13 13:48发布

站内文章 / 模拟电子
15626 0 973
1．问题描述大整数运算是现代密码学算法实现的基础，重要性不言而喻。大整数我们指的是二进制位512、1024和2048的数，一般的语言不支持。2．基本要求以类库头文件的形式实现。3．实现提示   在选择了大整数的存储结构之后，主要实现以下运算：① 模加；② 模减；③ 模乘；④ 模整除；⑤ 模取余。这五种运算模拟手算实现。⑥ 幂模：利用“平方-乘法”算法实现。⑦ GCD：利用欧几里得算法实现。⑧ 乘法逆: 利用扩展的欧几里得算法实现。⑨ 素数判定与生成：概率性素数产生方法产生的数仅仅是伪素数，其缺点在于，尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中较著名的算法有:Miller Rabin算法、Solovay-Strassen算法等。本文讨论Miller  Rabin算法。Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下:设n>2是一个奇数，设n-1=2sm，其中s是非负整数，m>0是奇数，设0bm≡－1(mod n)，或者存在一个r,0≤rb 2^r m≡－1(modn)则称n通过以b为基的Miller-Rabin测试。可以利用Miller-Rabin素性测试算法来随机生成大素数，随即生成一个奇数n>2，随即均匀的选取序列b1,b2...,bk∈{1,2,...,n-1}，对n进行k次Miller-Rabin素性测试，如果每次输出都为“n可能是素数”，则n是合数的概率小于 1/4k当k足够大时，1/4k是一个十分小的数。    同学们在具体实现时，为了提高速度最好以空间换时间，在主程序运行前先构造一个大素数表。 代码如下：#include #include #include #include //reverse函数所需添加的头文件 using namespace std; /* 大整数类 */ class BigInt { private: inline int compare(string s1, string s2) { if(s1.size() < s2.size()) return -1; else if(s1.size() > s2.size()) return 1; else return s1.compare(s2); } public: bool flag;//true表示正数，false表示负数，0默认为正数 string values;//保存所有位上的数字 BigInt():values("0"),flag(true){};//构造函数 BigInt(string str)//类型转换构造函数(默认为正整数) { values = str; flag = true; } public: friend ostream& operator << (ostream& os, const BigInt& bigInt);//重载输出操作符 friend istream& operator>>(istream& is, BigInt& bigInt);//输入操作符重载 BigInt operator+(const BigInt& rhs);//加法操作重载 BigInt operator-(const BigInt& rhs);//减法操作重载 BigInt operator*(const BigInt& rhs);//乘法操作重载 BigInt operator/(const BigInt& rhs);//除法操作重载 BigInt operator%(const BigInt& rhs);//求余操作重载 }; /* 重载流提取运算符'>>'，输出一个整数 */ ostream& operator << (ostream& os, const BigInt& bigInt) { if (!bigInt.flag) { os << '-'; } os << bigInt.values; return os; } /* 重载流插入运算符'>>'，输入一个正整数 */ istream& operator >> (istream& is, BigInt& bigInt) { string str; is >> str; bigInt.values = str; bigInt.flag = true; return is; } /* 两个正整数相加 */ BigInt BigInt::operator+(const BigInt& rhs) { BigInt ret; ret.flag = true;//正整数相加恒为正数 string lvalues(values), rvalues(rhs.values); //处理特殊情况 if (lvalues == "0") { ret.values = rvalues; return ret; } if (rvalues == "0") { ret.values = lvalues; return ret; } //调整s1与s2的长度 unsigned int i, lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); if (lsize < rsize) { for (i = 0; i < rsize - lsize; i++)//在lvalues左边补零 { lvalues = "0" + lvalues; } } else { for (i = 0; i < lsize - rsize; i++)//在rvalues左边补零 { rvalues = "0" + rvalues; } } //处理本质情况 int n1, n2; n2 = 0; lsize = lvalues.size(); string res = ""; reverse(lvalues.begin(), lvalues.end());//颠倒字符串，以方便从低位算起计算 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < lsize; i++) { n1 = (lvalues[i] - '0' + rvalues[i] - '0' + n2) % 10;//n1代表当前位的值 n2 = (lvalues[i] - '0' + rvalues[i] - '0' + n2) / 10;//n2代表进位 res = res + char(n1 + '0'); } if (n2 == 1) { res = res + "1"; } reverse(res.begin(), res.end()); ret.values = res; return ret; } /* 两个正整数相减 */ BigInt BigInt::operator-(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); //负数减负数 if(flag==false&&rhs.flag==false) { string tmp = lvalues; lvalues = rvalues; rvalues = tmp; } //负数减正数 if(flag==false&&rhs.flag==true) { BigInt res(lvalues); ret=res+rhs; ret.flag = false; return ret; } if(flag==true&&rhs.flag==false) { BigInt rel(lvalues),res(rhs.values); ret=rel+res; ret.flag = true; return ret; } //处理特殊情况 if (rvalues == "0") { ret.values = lvalues; ret.flag = true; return ret; } if (lvalues == "0") { ret.values = rvalues; ret.flag = false; return ret; } //调整s1与s2的长度 unsigned int i, lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); if (lsize < rsize) { for (i = 0; i < rsize - lsize; i++)//在lvalues左边补零 { lvalues = "0" + lvalues; } } else { for (i = 0; i < lsize - rsize; i++)//在rvalues左边补零 { rvalues = "0" + rvalues; } } //调整使‘-’号前边的数大于后边的数 int t = lvalues.compare(rvalues);//相等返回0，str1str2返回正数 if (t < 0) { ret.flag = false; string tmp = lvalues; lvalues = rvalues; rvalues = tmp; } else if (t == 0) { ret.values = "0"; ret.flag = true; return ret; } else { ret.flag = true; } //处理本质情况 unsigned int j; lsize = lvalues.size(); string res = ""; reverse(lvalues.begin(), lvalues.end());//颠倒字符串，以方便从低位算起计算 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < lsize; i++) { if (lvalues[i] < rvalues[i])//不足，向前借一维 { j = 1; while(lvalues[i+j] == '0') { lvalues[i+j] = '9'; j++; } lvalues[i+j] -= 1; res = res + char(lvalues[i] + ':' - rvalues[i]); } else { res = res + char(lvalues[i] - rvalues[i] + '0'); } } reverse(res.begin(), res.end()); res.erase(0, res.find_first_not_of('0'));//去掉前导零 ret.values = res; return ret; } /* 两个正整数相乘 */ BigInt BigInt::operator*(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); //处理0或结果正负 if (lvalues == "0" || rvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(flag==false||rhs.flag==false) { ret.flag=false; } //处理特殊情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); string temp; BigInt res, itemp; //让lvalues的长度最长 if (lvalues < rvalues) { temp = lvalues; lvalues = rvalues; rvalues = temp; lsize = lvalues.size(); rsize = rvalues.size(); } //处理本质情况 int i, j, n1, n2, n3, t; reverse(lvalues.begin(), lvalues.end());//颠倒字符串 reverse(rvalues.begin(), rvalues.end()); for (i = 0; i < rsize; i++) { temp = ""; n1 = n2 = n3 = 0; for (j = 0; j < i; j++) { temp = temp + "0"; } n3 = rvalues[i] - '0'; for (j = 0; j < lsize; j++) { t = (n3*(lvalues[j] - '0') + n2); n1 = t % 10;//n1记录当前位置的值 n2 = t / 10;//n2记录进位的值 temp = temp + char(n1 + '0'); } if (n2) { temp = temp + char(n2 + '0'); } reverse(temp.begin(), temp.end()); itemp.values = temp; res = res + itemp; } ret.values = res.values; return ret; } /* 两个正整数相除 */ BigInt BigInt::operator/(const BigInt& rhs) { BigInt ret; string lvalues(values), rvalues(rhs.values); string quotient; string temp; //处理特殊情况 if(rvalues == "0") { ret.values = "error";//输出错误 ret.flag = true; return ret; } if(lvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(compare(lvalues, rvalues) < 0) { ret.values = "0"; ret.flag = true; return ret; } else if(compare(lvalues, rvalues) == 0) { ret.values = "1"; ret.flag = true; return ret; } else { //处理本质情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); int i; if(rsize > 1) temp.append(lvalues, 0, rsize-1); for(i = rsize - 1; i < lsize; i++) { temp = temp + lvalues[i]; //试商 for(char c = '9'; c >= '0'; c--) { BigInt t = (BigInt)rvalues * (BigInt)string(1, c); BigInt s = (BigInt)temp - t; if(s.flag == true) { temp = s.values; quotient = quotient + c; break; } } } } //去除前导零 quotient.erase(0, quotient.find_first_not_of('0')); ret.values = quotient; ret.flag = true; return ret; } /* 两个正整数取余 */ BigInt BigInt::operator%(const BigInt& rhs) { BigInt ret,kj(values),ki(rhs.values); string lvalues(values), rvalues(rhs.values); string quotient; string temp; //处理特殊情况 if(rvalues == "0") { ret.values = "error";//输出错误 ret.flag = true; return ret; } if(lvalues == "0") { ret.values = "0"; ret.flag = true; return ret; } if(compare(lvalues, rvalues) < 0) { if(flag==false) { ret.values=(ki-kj).values; ret.flag = true; return ret; }else{ ret.values = lvalues; ret.flag = true; return ret; } } else if(compare(lvalues, rvalues) == 0) { ret.values = "0"; ret.flag = true; return ret; } else { //处理本质情况 unsigned int lsize, rsize; lsize = lvalues.size(); rsize = rvalues.size(); int i; if(rsize > 1) temp.append(lvalues, 0, rsize-1); for(i = rsize - 1; i < lsize; i++) { if(temp=="0"){ temp=lvalues[i]; }else{ temp = temp + lvalues[i]; } //试商 for(char c = '9'; c >= '0'; c--) { BigInt t = (BigInt)rvalues * (BigInt)string(1, c); BigInt s = (BigInt)temp - t; if(s.flag == true) { //cout<

热门文章