来自当知百科
跳转到: 导航搜索

目录

Euclid算法概述

  历史上第一个称得上算法的好像就是这个欧几里得算法,其实就是地球人都知道

  的辗转相除,故又叫“辗转相除法”不要小看她,她是很美的。

  简单的描述就是,记gcd(a,b)表示非负整数a,b的最大公因数,那么:gcd(a,b)

  =gcd(b,a%b)

Euclid算法定义

  gcd(a,b)=gcd(b, a+kb) a,b,k为任意整数

  即gcd(a,b)=gcd(b, a mod b) a≥0,b>0

  • Example:gcd(55,22)=gcd(22, 55mod22)=gcd(22,11)=11 

  证明:假定d=gcd(a,b),那么有d|a和d|b.对任何正整数b,a

  可表示为如下形式: a=kb+r ≡r mod b, a mod b =r , 因

  此,有(a mod b )= a-kb,k为某个整数。但由于d|b,b也

  能整除kb, 而d|a,故有d|(a mod b), 这表明d 也是b 和(a

  mod b) 的公因子。由于这是可逆的,如果d 是b 和(a mod

  b) 的公因子,那么d|kb,且d|[kb+(a mod b)],这等同于

  d|a。这样a和b的公因子集合等同于b 和(a mod b) 的公因

  子集合。

C语言的Euclid算法描述

  int gcd(int a,intb)//注释:两个数辗转相除。a>b,如果a<b,需要将他们交换,这里不想写交换部分代码

  {

  if(a==0)

  return b;

  if(b==0)

  return a;

  return gcd(b,a%b);

  }

Euclid算法的应用

  求两个数的最大公约数gcd(55,22)=gcd(22, 55mod22)=gcd(22,11)=11 

  最常用的就是在RSA里边求密钥

  RSA算法,是非对称加密的标准算法,其实算法很简单:

  找到两个素数p,q,再找一个数r,使gcd(r,(p-1)(q-1))=1,也就是说互素,然后再找一个数m,使rm=1(mod(p-1)(q-1)),然后再作乘法n=pq,然后把pq丢掉,最好是让任何人都不知道,包括自己(免得说梦话的时候被人听到),然后手里拿到r,m,n,r就是PrivateKey,只有你知道,而m,n就是Public Key。设信息为a,加密过程:a^r=b (modn),b就是密文,解密过程:b^m=a(mod n),反过来用m加密,用r解密是一样的。

Euclid算法在RSA密码体系中的实现

  #include<iostream.h>

  #include<math.h>

  #include <windows.h>

  int mul(int x,int r,int n);//大树幂乘

  int niyuan(int n,int u); //求逆元

  int gcd(int a,int b);//求最大公约数

  bool IsPrime(int a );//判断是否为素数

  void main()

  {

  system("color 3f");

  system("title ☆★ RSA公钥密码 ★☆");

  cout<<"\t\t****RSA公钥密码加密解密系统****"<<endl;

  int p ,q ;

  cout<<" 请输入两个素数 :p , q :"<<endl;

  cin>>p>>q;

  int n=p*q;

  int w=(p-1)*(q-1);

  int e;

  cout<<"请输入加密密钥 e (与"<<w<<"最大公约数为 1)"<<endl;

  cin>>e;

  int d;

  d=niyuan(w,e);

  cout<<"经计算解密得到密钥 :"<<d<<endl;

  cout<<"输入需要加密的明文:"<<endl;

  int ming;

  cin>>ming;

  cout<<"经加密后得到的密文:"<<mul(ming,e,n)<<endl;

  cout<<"退出系统请按 1 "<<endl;

  cout<<"进行解密请按 2 "<<endl;

  int k;

  cin>>k;

  if(k==2)

  {

  cout<<"请输入需解密的密文:"<<endl;

  int miwen;

  cin>>miwen;

  cout<<"经解密后得到的明文:"<<mul(miwen,d,n)<<endl;

  }

  }

  int mul(int x,int r,int n)//大树幂乘函数

  {

  int a=x;

  int b=r;

  int c=1;

  while(b!=0)

  {

  if(b%2!=0)

  {

  b=b-1;

  c=(c*a)%n;

  }

  else

  {

  b=b/2;

  a=(a*a)%n;

  }

  }

  return c ;

  }

  int niyuan(int n,int u)//求逆元

  {

  int n1=n;

  int n2=u;

  int b1=0;

  int b2=1;

  int q=n1/n2;

  int r=n1-q*n2;

  while(r!=0)

  {

  n1=n2;

  n2=r;

  int t=b2;

  b2=b1-q*b2;

  b1=t;

  q=n1/n2;

  r=n1-q*n2;

  }

  if(n2!=1)

  {

  return 0 ;

  }

  else

  {

  return (b2+n)%n;

  }

  }

  int gcd(int a,int b)//求最大公约数

  {

  int n1=a;

  int n2=b;

  int q=n1/n2;

  int r=n1-q*n2;

  while(r!=0)

  {

  n1=n2;

  n2=r;

  q=n1/n2;

  r=n1-q*n2;

  }

  return n2 ;

  }

  bool IsPrime(int a)//判断是否为素数

  {

  int b=(int)sqrt(a);

  int temp;

  for(int i=2;i<=b;i++)

  {

  temp=a%i;

  }

  if(temp==0)

  {

  return false ;

  }

  else

  {

  return true ;

  }

  }

个人工具
名字空间

变换
查看
操作
导航
工具箱