//下面的代码勉强算是bignum_beta1版本!
//实现了大整数的加减乘除四则运算,以及求两个整数的最大公约数,以及求乘法逆,miller_rabin素性检验,平方_乘法算法
//不足之处,位数还很难扩展至几千位,以及运算速度有一点慢,既然是beta1,说明bug还是挺多的
//程序缺少测试数据来测试,所以有的结果不敢保证其正确性
//由于使用c++复写了很多运算符,加入这个文件之后,大数bignum可以看做是一个如同如同int一样的基本类型
//可以像int一样加减乘除和输入输出
#include<iostream>
#include<string>
#include<ctime>//用于产生随机数
using namespace std;
const int base=1000;//base用来表示数组中每个数的进制,逢base向前一位进1
const int MAX_LEN=300;//数组的最大长度
class bigNum{
public:
int num[MAX_LEN];
int len;
int flag;//增设一个标志,表示正负,这样大数包就可以扩展置负数
friend istream& operator>>(istream& input,bigNum &obj);
friend ostream& operator<<(ostream& output,bigNum& obj);
bigNum &operator=(const bigNum &s);//对于"="号的重载
//类的赋值运算符"="只能重载为成员函数,而不能把它重载为友元函数
bigNum();//构造函数
void eucli_setnum(int x);//设置数值
};
void bigNum::eucli_setnum(int x)//设置这个函数主要应对扩展的欧几里德算法
{
num[0]=x;
if(x!=0)
len=1;
else len=0;
}
bigNum::bigNum()//构造函数
{
memset(num,0,sizeof(num));//清零
len=0;
flag=1;//默认的数为正数
}
//关于下面的运算符重载函数,有一点需要特别记住,那就是len一定要记得更新,不然会出错!
//以下的几个函数都是逻辑运算符的重载函数
bool operator==(bigNum &a,bigNum &b)//"=="号的重载
{
for(int i=MAX_LEN-1;i>=0;i--)
if(a.num[i]!=b.num[i])
return false;
return true;
}
bool operator!=(bigNum &a,bigNum &b)//"!="号的重载
{
for(int i=0;i<MAX_LEN;i++)
if(a.num[i]!=b.num[i])
return true;//只要有一个不相等,就返回true
return false;
}
/*
bool operator!=(bigNum &a,int &b)//"!="号的重载
{
if(a.num[0]!=b)
return false;//只要有一个不相等,就返回true
for(int i=1;i<MAX_LEN-1;i++)
if(a.num[i]!=0)
return false;
return true;
}*/
bool operator>(bigNum &a,bigNum &b)//">"号的重载
{
for(int i=MAX_LEN-1;i>=0;i--)//从最高位向下搜索
if(a.num[i]!=b.num[i])//如果有两个数不相等,必定有一大一小
if(a.num[i]>b.num[i])
return true;
else return false;
return false;//两个数相同也返回false
}
bool operator<(bigNum &a,bigNum &b)//"<"号的重载
{
for(int i=MAX_LEN-1;i>=0;i--)//从最高位向下搜索
{
if(a.num[i]!=b.num[i])//如果有两个数不相等,必定有一大一小
if(a.num[i]<b.num[i])
return true;
else
return false;
}
return false;
}
bool operator<=(bigNum &a,bigNum &b)
{
for(int i=MAX_LEN-1;i>=0;i--)//从最高位向下搜索
if(a.num[i]!=b.num[i])//如果有两个数不相等,必定有一大一小
if(a.num[i]<b.num[i])
return true;
else
return false;
return true;//最后相等返回true
}
bool operator>=(bigNum &a,bigNum &b)
{
for(int i=MAX_LEN-1;i>=0;i--)//从最高位向下搜索
if(a.num[i]!=b.num[i])//如果有两个数不相等,必定有一大一小
if(a.num[i]>b.num[i])
return true;
else
return false;
return true;//最后相等返回true
}
bigNum &bigNum::operator=(const bigNum &s)//"="号的重载
{
if(this==&s) return *this;//防止s=s
for(int i=0;i<MAX_LEN;i++)
num[i]=s.num[i];
len=s.len;
flag=s.flag;
}
//以下几个函数是四则运算符的重载函数
bigNum operator-(bigNum a,bigNum b);//声明,防止编译出错
bigNum operator+(bigNum a,bigNum b)//加法的重载
{
bigNum sum;//存储结果
int i;
if(a.flag<0 && b.flag>0)//a为负,b为正,则a+b=b-|a|
{
a.flag=1;//这里对a进行了修改(将a变为正数),以便于进行减法运算,这也是重写不用引用的reason
sum=b-a;
if(b>a)
sum.flag=1;//结果为正
else
sum.flag=-1;//结果为负
return sum;
}
if(a.flag>0 && b.flag<0)//a为正,b为负,则b+a=a-|b|
{
b.flag=1;
sum=a-b;
if(a>b)
sum.flag=1;//结果为正
else
sum.flag=-1;//结果为负
return sum;
}
//余下的情况是a,b两者符号相同,即a+b=(|a|+|b|)*flag,flag与a,b符号一致
for(i=0;i<MAX_LEN;i++)
{
sum.num[i]+=a.num[i]+b.num[i];
if(sum.num[i]>base)//超出base,则要进位
{
sum.num[i]-=base;
sum.num[i+1]++;
}
if(sum.num[i]!=0) sum.len=i+1;//len要同步更新
}
sum.flag=a.flag;//如果a,b不是一正一负,那么a,b必定同号
return sum;
}
bigNum operator-(bigNum a,bigNum b)//减法的重载
{
bigNum sum;//存储结果
if(a.flag<0 && b.flag>0)//a为负,b为正,则a-b=-(|a|+|b|)
{
a.flag=1;
sum=b+a;
sum.flag=-1;//两个负数相加,结果一定为负数
return sum;
}
if(a.flag>0 && b.flag<0 && a>b)//a为正,b为负,则a-b=|a|+|b|
{
b.flag=1;
sum=b+a;
sum.flag=1;//两个正数相加,结果一定为正数
return sum;
}
//下面a,b的符号值一致
if(a<b)//a<b,则|a|-|b|<0,转化为-(|b|-|a|)
{
sum=b-a;
sum.flag=-b.flag;
return sum;
}
//下面表示的就是|a|>|b|,且a,b同号
for(int i=0;i<MAX_LEN;i++)
{
a.num[i]-=b.num[i];
if(a.num[i]<0)//不够减时向前借位
{
a.num[i]+=base;
a.num[i+1]--;
}
if(a.num[i]!=0) a.len=i+1;//len要同步更新
}
return a;
}
bigNum operator*(bigNum &a,bigNum &b)//对于乘法的重载
{//乘法的flag已经设置完毕
bigNum sum;
int i,j;
for(i=0;i<b.len;i++)//用第二个数b乘以第一个数a
{
for(j=0;j<a.len;j++)
sum.num[i+j]+=b.num[i]*a.num[j];//先乘起来,后面统一进位
}
for(i=0;i<MAX_LEN;i++)//循环统一处理进位问题
{
if(sum.num[i]>=base)
{
sum.num[i+1]+=sum.num[i]/base;
sum.num[i]%=base;
}
if(sum.num[i]!=0) sum.len=i+1;//len要同步更新
}
//现在设置数的正负
if(a.flag+b.flag==0) sum.flag=-1;
else sum.flag=a.flag;
return sum;
}
int substract(int *p1,int *p2,int n1,int n2)
{
int i;
//被除数不能小于除数
if(n1<n2) return -1;//p2数的长度不能大于p1数的长度
if(n1==n2)//两数长度一致情况下(所占用数组长度),p2数要小于p1数
{
for(i=n1-1;i>=0;i--)
{
if(p1[i]>p2[i]) break;
else if(p1[i]<p2[i]) return -1;
}
}
for(i=0;i<n1;i++)
{//减去一个p2值
p1[i]-=p2[i];
if(p1[i]<0)
{
p1[i]+=base;
p1[i+1]--;
}
}
for(i=n1-1;i>=0;i--)
if(p1[i])
return i+1;//返回所占用的数组长度
return 0;
}
bigNum operator/(bigNum a,bigNum b)//除法的重载
{//除法的flag设置完毕
bigNum sum;
int i,j;
if(a<b)//a<b时返回0
return sum;
int nTimes=a.len-b.len;
if(nTimes>0)
{
for(i=a.len-1;i>=nTimes;i--)
b.num[i]=b.num[i-nTimes];//朝高位移动
for(;i>=0;i--)
b.num[i]=0;//低位补0
b.len=a.len;
}
for(j=0;j<=nTimes;j++)
{
int nTmp;
//一直减到不够减为止
while((nTmp=substract(a.num,b.num+j,a.len,b.len-j))>=0)
{
a.len=nTmp;
sum.num[nTimes-j]++;//每减成功一次,则将商的对应为加1
}
if(sum.len==0 && sum.num[nTimes-j]!=0)
sum.len=nTimes-j+1;//同步更新len
}
//现在设置数的正负
if(a.flag+b.flag==0) sum.flag=-1;
else sum.flag=a.flag;
return sum;
}
bigNum operator%(bigNum &a,bigNum &b)//取模运算的重载
{
return a-b*(a/b);
}
istream& operator>>(istream& input,bigNum& obj)//重载输入函数
{//输入flag已经设置完毕
string str;
input>>str;
int l=str.size();//l为字符串长度
int i,k,j;
for(j=0,i=base;i!=1;)
if(i>0)
{
j++;
i=i/10;
}//j用来表示base的位数
int p=l/j,q=l%j;//输入的数按照每个可以存放j个的标准,恰好放进,一共占用p个位置
if(q) obj.len=p+1;//当然,不一定恰好放进,就需要p+1个位置来放
else obj.len=p;
if(str[0]=='-')//输入为负数
obj.flag=-1;
else
obj.flag=1;//设置符号位,正数则flag为1,否则为-1
for(i=0;i<q;i++)//用来存放不能整除的高位部分
{
if(str[i]=='-') i++;//如果是负数的话,第一位不用处理
obj.num[p]=obj.num[p]*10+str[i]-'0';
}
p--;
for(;p>=0;p--)//下面的字符,以j为一组,字符个数恰好能够被j整除,一组组存入num数组里
{
for(k=1;k<=j;k++)
{
obj.num[p]=obj.num[p]*10+str[i]-'0';
i++;
}
}
return input;
}
ostream& operator<<(ostream& output,bigNum& obj)
{//输出flag就已经设置好了
int i;
for(i=MAX_LEN-1; (i>=0)&&(obj.num[i]==0);i--);
if(i>=0)
{
if(obj.flag==-1) output<<'-';
for(;i>=0;i--)
output<<obj.num[i];
}
else
output<<'0';//整个数组都是0
return output;
}
bigNum extended_euclidean(bigNum n,bigNum m,bigNum &x,bigNum &y)//扩展的欧几里德算法的另一种形式
{
bigNum x1, x2, x3=n;
x1.eucli_setnum(1);
x2.eucli_setnum(0);
bigNum y1, y2, y3=m;
y1.eucli_setnum(0);
y2.eucli_setnum(1);
bigNum zero;
while(x3%y3!=zero)
{
bigNum d=x3/y3;
bigNum t1,t2,t3;
t1=x1-d*y1;
t2=x2-d*y2;
t3=x3-d*y3;
x1=y1; x2=y2; x3=y3;
y1=t1; y2=t2; y3=t3;
}
x=y1; y=y2;
return y3;
}
bigNum gcd(bigNum &n,bigNum &m)//求两个大数的最大公约数
{
bigNum x,y;
return extended_euclidean(n,m,x,y);
}
//求乘法逆其实也没有特别好的算法,主要还是依靠欧几里德算法
bigNum mutirinverse(bigNum &n,bigNum &m)//求乘法逆
{
bigNum x,y;
extended_euclidean(m,n%m,x,y);
return x;
}
//平方——乘法算法
bigNum Square_and_Mutiply(bigNum a,bigNum m,bigNum n)
{
bigNum sum,zero,two;
two.eucli_setnum(2);
sum.eucli_setnum(1);
int length=1;
int bin[300];
//先将m转化为二进制
do
{
sum=m%two;
bin[length++]=sum.num[0];
m=m/two;
}while(m!=zero);
sum.eucli_setnum(1);
while(length>=0)
{
sum=(sum*sum)%n;
if(bin[length]==1)
{
sum=(sum*a)%n;
}
length--;
}
return sum;
}
//最后一个函数,用于素数判定的Miller-Rabin算法
bool wintess(bigNum a,bigNum n)
{
bigNum m,x,y,one,two,zero;
one.eucli_setnum(1);two.eucli_setnum(2);
bigNum i,j;
m=n-one;
while(m%two==zero)
{
m=m/two;
j=j+one;
}
x=Square_and_Mutiply(a,m,n);
for(i.eucli_setnum(1);i<=j;i=i+one)
{
y=Square_and_Mutiply(x,two,n);
if((y==one)&&(x!=one)&&(x!=n-one))
return true;
x=y;
}
if(y!=one) return true;
return false;
}
bool Miller_Robin(int times,bigNum &n)
//n为大于3的奇数,输出n是否通过素性检验
{
bigNum a,one,two,random;
one.eucli_setnum(1);two.eucli_setnum(2);
if(n==one) return false; if(n==two) return true;
srand((unsigned)time(0));
for(int i=1;i<=times;i++)
{
random.eucli_setnum(rand());
a=random%(n-two)+two;
if(wintess(a,n)) return false;
}
return false;
}
int main()
{
bigNum a,b;
while(1)
{
cin>>a;
cin>>b;
cout<<a*b<<endl;
}
system("pause");
return 0;
}
byte传输的最小单位
1bit =8 byte;
密码学算法最重要的就是大整数的运算和字符的装换
原文链接: https://www.cnblogs.com/Erma/p/7616675.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/260698
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!