# Demo entry 6780234

py

Submitted by huang on Dec 24, 2018 at 00:54
Language: C++. Code size: 2.0 kB.

```#include <iostream>
#include<stdlib.h>
#include <cmath>
using namespace std;

int exEuclidean(int a,int b,int &x,int &y)
{
////扩展的欧几里得算法,存在整数对 x，y ，使得 gcd（a，b）=ax+by
if (b==0)
{
x=1,y=0;
return a;
}
int q=exEuclidean(b,a%b,y,x);
y-=a/b*x;
return q;
}

int modOFmi(int x,int r,int n)
{
//x^r mod n快速幂
int a=x,b=r,c=1;
while(b)
{
if(b&1)
c=a*c%n;
a=a*a%n;
b=b>>1;
}
return c;
}

int IsPrime(int iNumber)
{
//检测iNumber是否为素数，是返回1，否返回0
int iCount;
iCount=2;
if(iNumber<2)
return 0;
while(iCount<=(iNumber/2))
{
if(iNumber%iCount==0)
return 0;
iCount++;
}
return 1;
}

int computeBYY(int p)
{
//计算p的本原元//这里求的是最小的一个
for(int a=2; a<p; a++)
{
if(modOFmi(a,p-1,p) == 1)
return a;
}
return 0;
}

int main()
{
int p;//素数
int Plain_text;//明文
int pri_root;//素数p的一个原根
int pri_k;//私钥
int pub_k;//公钥
int k;//过程随机数k
int c1,c2;//密文
cout<<endl<<"输入素数p:";
cin>>p;
while(!IsPrime(p))
{
cout<<"p不是素数！"<<endl;
cout<<endl<<"输入素数p:";
cin>>p;
}
cout<<"输入小于素数p的明文:";
cin>>Plain_text;

pri_root=computeBYY(p);
cout<<"找出p的一个原根为:"<<pri_root<<endl;

pri_k=rand()%(p-1)+1;//私钥 1≤a≤p-2
cout<<endl<<"输入完成，开始计算密文！"<<endl<<endl;

pub_k=modOFmi(pri_root,pri_k,p);
cout<<"公钥为:"<<pub_k<<endl;
k=rand()%(p-1)+1;	//随机数k 1≤k≤p-2
c1 = modOFmi(pri_root,k,p);
c2 = ( Plain_text%p*modOFmi(pub_k,k,p) )%p;
cout<<"密文Dk(c1,c2)为("<<c1<<","<<c2<<")"<<endl;
cout<<"密文完成，开始计算明文！"<<endl<<endl;

int x,y;//存在整数对 x，y ，使得 gcd（a，b）=ax+by
exEuclidean(modOFmi(c1,pri_k,p),p,x,y);
x=(x+p)%p;
Plain_text=(c2*x)%p;
cout<<"计算出的明文为:"<<Plain_text<<endl;
return 0;
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.