Euclid算法概述

Euclid算法定义

C语言的Euclid算法描述

RSA中Euclid算法的应用(例题及分析 Euclid算法的具体实现)

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算法描述

//no matter a is bigger or b

//you should call anyone of them below

//non-recursion

unsigned int gcd(unsigned int a,unsigned int b){

int r;

while(b>0){

r=a%b;

a=b;

b=r;

}

return a;

}

//non-recursion

unsigned int gcd(unsigned int a,unsigned int b){

while(b^=a^=b^=a%=b);

return a;

}

//recursion

unsigned int gcd(unsigned int a,unsigned int b){

return (b>0)?gcd(b,a%b):a;

RSA中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就是Private Key，只有你知道，而m,n就是Public Key。设信息为a,加密过程：a^m=b (mod n)，b就是密文，解密过程：b^r=a(mod n)，反过来用m加密，用r解密是一样的。

Euclid算法的具体实现

#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)

break;

}

if(temp==0)

{

return false ;

}

else

{

return true ;

}

}