void resetNumA(string numAStr);
//使用string重置numB
void resetNumB(string numBStr);
//将数组转换为字符串，用于输出
string getNumString(int* num);
//判断两个数字哪个大
int compare(string numAStr, string numBStr);
//加法
string sum(string numAStr, string numBStr);
//减法
string sub(string numAStr, string numBStr);
//乘法
string mul(string numAStr, string numBStr);
//除
string div(string numAStr, string numBStr);
//取余
string mod(string numAStr, string numBStr);
//模幂算法
string getMod(string m, string pow, string n);
//求2的n次方函数
string mul_2(int i);
//求m的n次方
string mul_m(string m, string n);
#endif
#include<iostream>
#include"operation.h"
#include<string>
#include<vector>
using namespace std;//结果支持的最大位数
const static int M = ;int numA[M];
int numB[M];//使用string重置numA
void resetNumA(string numAStr)
{
memset(numA, , M * sizeof(int)); //将字符串的每一位都转换成数字传入数组
for (int i = ; i < numAStr.length(); i++)
{
numA[i] = numAStr[numAStr.length() - i - ] - '';
}
}//使用string重置numB
void resetNumB(string numBStr)
{
memset(numB, , M * sizeof(int)); //将字符串的每一位都转换成数字传入数组
for (int i = ; i < numBStr.length(); i++)
{
numB[i] = numBStr[numBStr.length() - i - ] - '';
}
}//将数组转换为字符串，用于输出
string getNumString(int* num)
{
string numString;
bool isBegin = false;
for (int i = M - ; i >= ; i--)
{
if (num[i] != )
{
isBegin = true;
} if (isBegin)
{
numString += num[i] + '';
}
}
return numString;
}//判断两个数字哪个大
int compare(string numAStr, string numBStr)
{
int i = ;
int la = ;
while (numAStr[i] == '') {
la++;
i++;
}
i = ;
int lb = ;
while (numBStr[i] == '') {
lb++;
i++;
}
string a(numAStr.substr(la, numAStr.length()));
string b(numBStr.substr(lb, numBStr.length()));
if (a.length() > b.length())
{
return ;
}
else if (a.length() < b.length())
{
return -;
}
else
{
for (int i = ; i < a.length(); i++)
{
if (a[i]>b[i])
{
return ;
} if (a[i]<b[i])
{
return -;
}
}
return ;
}
}//加法
string sum(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); for (int i = ; i < M; i++)
{
//结果保存在numA中
numA[i] += numB[i]; //数字大于9则进位
if (numA[i]>)
{
numA[i] -= ;
numA[i + ]++;
}
} return getNumString(numA);
}//减法
string sub(string numAStr, string numBStr)
{
bool isNegative = false; //如果numA比numB小
//则结果为负数
//调换位置进行计算
if (compare(numAStr, numBStr) == -)
{
isNegative = true;
string temp = numAStr;
numAStr = numBStr;
numBStr = temp;
}
else if (compare(numAStr, numBStr) == )
{
return "";
} resetNumA(numAStr);
resetNumB(numBStr); for (int i = ; i < M; i++)
{
//减数小于被减数就借位
if (numA[i]<numB[i])
{
numA[i] = numA[i] + - numB[i];
numA[i + ]--;
}
else
{
numA[i] -= numB[i];
}
}
if (isNegative)
{
return "-" + getNumString(numA);
}
else
{
return getNumString(numA);
}}//乘法string mul(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); vector<string> nums;
for (int i = ; i < numBStr.length(); i++)
{
//初始化一个临时数据来保存被乘数与乘数的某一位相乘的结果
int temp[M];
memset(temp, , M * sizeof(int)); for (int j = i; j < numAStr.length() + i; j++)
{
temp[j] += numA[j - i] * numB[i] % ; temp[j + ] = numA[j - i] * numB[i] / ; //如果大于9，那么就做进位处理
if (temp[j]>)
{
temp[j] -= ;
temp[j + ]++;
}
}
nums.push_back(getNumString(temp));
} //每位相乘的结果再用加法加起来
string result = nums[];
for (int i = ; i < nums.size(); i++)
{
result = sum(result, nums[i]);
} return result;
}//除,结果精确到个位
string div(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); string result;
string left; if (compare(numAStr, numBStr) == -)
{
return "";
} //标记第一个不为0的位数的出现
bool flag = false;
for (int i = ; i < numAStr.length(); i++)
{
left += numAStr[i]; //余数比除数大
if (compare(left, numBStr) == )
{
flag = true; int count = ;
string temp = numBStr; while (true)
{
//每循环一次加上一个余数
temp = sum(temp, numBStr); //余数仍然大于除数，继续累加
if (compare(left, temp) == )
{
count++;
}
//余数小于除数
//可以计算结果
else if (compare(left, temp) == -)
{
result += count + '';
left = sub(left, sub(temp, numBStr));
break;
}
//此时余数刚好是除数的倍数
else if (compare(left, temp) == )
{
count++;
result += count + '';
left = "";
break;
}
}
}
//刚好除尽
else if (compare(left, numBStr) == )
{
flag = true;
result += "";
left = "";
}
//余数比除数小，跳到下一位
else if (flag)
{
result += "";
} } return result;
}
//取模
string mod(string numAStr, string numBStr)
{ string result = ""; if (compare(numAStr, numBStr) == -)
{
return numAStr;
}
else if (compare(numAStr, numBStr) == ) {
return result;
}
else {
string d = div(numAStr, numBStr);
string x = mul(numBStr, d);
result = sub(numAStr, x);
return result;
}
}//加密解密模幂算法
string getMod(string m, string pow, string n)
{
string temp;
while (compare(pow,"") == ) {
if(mod(pow,"")=="")
temp = temp + "";
else
temp = temp + "";
pow = div(pow,"");
}
temp = temp + "";
int length = temp.length();
string T[M];
string M = "";
T[] = mod(m, n);
for (int i = ; i < length; i++) {
T[i] = mod(mul(T[i-],T[i-]),n);
}
for (int i = ; i < length; i++) {
if (temp[i] == '') {
M = mul(M, T[i]);
}
}
string result = mod(M, n);
return result;
}//求2的n次方函数
string mul_2(int i) {
string result = "";
for (int j = ; j < i; j++) {
result = mul(result, "");
}
if (i == )
return "";
else
return result;
}//求m的t次方函数
string mul_m(string m,string t) {
string result = m;
string j;
for ( j = ""; compare(j, t) == -; j = sum(j, "")) {
result = mul(result, m);
}
return result;
}
#include<iostream>
#include"operation.h"
using namespace std;int main() {
string char_number_p;
string char_number_q; string temp[][];
//p=17,q=11
//p=17,q=19
//p=41,q=43
//67,71
//797 809
//49993 49999
//116747 110221
//1000017077
//
char_number_p="";
char_number_q=""; string n = mul(char_number_p, char_number_q);
string tmp1 = "";
string On = mul(sub(char_number_p, tmp1),sub(char_number_q, tmp1)); string e = ""; //拓展欧几里得算法
temp[][] = e;
temp[][] = "";
temp[][] = On;
temp[][] = "";
int i = ;
do {
temp[i][] = temp[i - ][];
temp[i][] = "";
temp[i][] = temp[i - ][];
temp[i][] = "";
if (compare(temp[i][], temp[i][]) == ) {
temp[i][] = mod(temp[i][], temp[i][]);
}
else {
temp[i][] = mod(temp[i][], temp[i][]);
}
i++;
} while (compare(temp[i - ][], "") == );
int value = i - ;
temp[value][] = "";
value--;
while (value >= ) {
if (temp[value + ][] != "")
temp[value][] = div(sub(mul(temp[value][], temp[value + ][]), ""), temp[value][]);
else if (temp[value + ][] != "")
temp[value][] = div(sum(mul(temp[value][], temp[value + ][]), ""), temp[value][]);
value--;
}
string d = temp[][]; cout << "e:" << e << endl;
cout << "p*q:" << n << endl;
cout << "O(n):" << On << endl;
cout << "d:" << d << endl;
cout << "密钥{ " << e << " , " << n << " }" << endl;
cout << "公钥{ " << d << " , " << char_number_p <<" , "<< char_number_q << " }" << endl; string miwen;
cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
cout << "密文:" << miwen << endl;
string C1 = getMod(miwen, e, n);
cout << "加密后的明文:" << C1 << endl;
string M1 = getMod(C1, d, n);
cout << "解密后的密文:" << M1 << endl; cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
string C2 = getMod(miwen, e, n);
cout << "加密后的明文:" << C2 << endl;
string M2 = getMod(C2, d, n);
cout << "解密后的密文:" << M2 << endl; cout << "请输入密文(暂小于10的29次方)" << endl;
cin >> miwen;
string C3 = getMod(miwen, e, n);
cout << "加密后的明文:" << C3 << endl;
string M3 = getMod(C3, d, n);
cout << "解密后的密文:" << M3 << endl; system("pause");
return ;
}
以上为测试实现的代码。
思路：先实现string类型的加减乘除的重写，以及用到的其他的操作函数，比较，取模，加解密函数，以及其他的m的n次方的操作。
然后在主函数里面嵌入欧几里得算法，调用求得d，之后就是简单的调用加解密函数
pq的值也是测试得到的
这是运行截图：
//拓展欧几里得算法
temp[0][0] = e;
temp[0][1] = "";
temp[0][2] = On;
temp[0][3] = "";
int i = 1;
do {
temp[i][0] = temp[i - 1][0];
temp[i][1] = "";
temp[i][2] = temp[i - 1][2];
temp[i][3] = "";
if (compare(temp[i][0], temp[i][2]) == 1) {
temp[i][0] = mod(temp[i][0], temp[i][2]);
}
else {
temp[i][2] = mod(temp[i][2], temp[i][0]);
}
i++;
} while (compare(temp[i - 1][0], "1") == 1);
int value = i - 1;
temp[value][1] = "1";
value--;
while (value >= 0) {
if (temp[value + 1][1] != "")
temp[value][3] = div(sub(mul(temp[value][0], temp[value + 1][1]), "1"), temp[value][2]);
else if (temp[value + 1][3] != "")
temp[value][1] = div(sum(mul(temp[value][2], temp[value + 1][3]), "1"), temp[value][0]);
value--;
}
string d = temp[0][1];
这部分拓展的欧几里得算法也可以单独使用，这里是用空间换取的时间效率。
