ユークリッド+拡張ユークリッド+RSA

ユークリッドアルゴリズム:
転がり相除法、小学校のもの、gcd(a,b)=gcd(b,a%b)、
簡単で、用途が広く、テンプレートは以下の通りです.

int gcd(int a,int b)//     long long
{
   return b!=0 ? gcd(b,a%b):a;

}

拡張ユークリッドアルゴリズム:
拡張ユークリッドアルゴリズムはユークリッドアルゴリズム(転がり相除算とも呼ばれる)の拡張である.このアルゴリズムは、a、bの2つの整数の最大公約数を計算することに加えて、整数x、y(そのうちの1つは負の数である可能性が高い)を見つけることができる.通常、最大公因子について述べると、ax+by=gcd(a,b)となる整数xとyが必ず存在するという非常に基本的な事実に言及する.2つの数a,bがあり、それらを転がす相除法を行い、それらの最大公約数を得ることができる-これはよく知られている.そして,転がり相除去法で生じた式を収集し,逆戻りしてax+by=gcd(a,b)の整数解を得ることができる.
ex_gcd(a,b,x,y)はa>bを仮定する.1、b=0であればgcd(a,b)=aとなり、x=1、y=0となる.2、a*b!=0はax 1+by 1=gcd(a,b)である.  bx2+(a%b)y2=gcd(b,a%b);ユークリッドアルゴリズムから得られる:gcd(a,b)=gcd(b,a%b);すなわち、ax 1+by 1=bx 2+(a%b)y 2;すなわち、ax 1+by 1=bx 2+[a-(a/b)b]y 2=ay 2+bx 2-b(a/b)y 2;aとbは定値であり、式が一定であるため、x 1=y 2、y 1=x 2-(a/b)y 2;このようにx 2,y 2を解くことによってx 1,y 1が得られる.コードは次のとおりです.

#include
int exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-(a/b)*y;
	return r;
}  
int main()
{
	int a,b,x,y;
	scanf("%d %d",&a,&b);
	int c=exgcd(a,b,x,y);//      
	printf("%d %d
",c,(x+b)%b);
	return 0;
}

このアルゴリズムはgcd(a,b)を求めることができ,xとyを求めることもできる.
Zn * ={x| x>0 && x< n && gcd(x,n)=1 };
乗算逆要素:集合Zn*の要素に対して、各数aは、ax≡1(mod n)となるように、それに対応する唯一の乗算逆要素xを有する.
1つの数の逆元がある十分な必要条件はgcd(a,n)=1であり,この逆元は唯一存在する.逆元の意味:モードnの意味では、1つの数aに逆元xがある場合、aで割るとxを乗じることに相当する.拡張ユークリッドアルゴリズム乗算逆元:所与のモードn、aを求める逆はax=1(mod n)を解くことに相当し、この方程式はax-my=1に変換することができ、それから二元一次方程式の方法を組み合わせて、拡張ユークリッドアルゴリズムでx 0、y 0とgcdのセットを求める.gcdが1 gcdでないかどうかをチェックすることは、逆元が存在しないことを示し、1であればx 0から0~m-1の範囲で調整すればよい.コードは次のとおりです.

int mod_reverse(int a,int n)//ax=1(mod n)  a   x 
{
    int d,x,y;
    d=ex_gcd(a,n,x,y);
    if(d==1)
        return (x%n+n)%n;
    else
        return -1;
}

 
思い出した前にPythonでRSAの解読を求めるブログを書いたことがあります.19年のブルーブリッジカップの省試合の問題です.今、c++の解法を補充します.
タイトルリンク:https://blog.csdn.net/weixin_43107805/article/details/89515994

#include
#define ll long long 
using namespace std;
const int N=500000;
ll n=1001733993063167141;
ll p=891234941;
ll q=1123984201;
ll c=20190324; //   
ll d=212353;   //  
ll m=(p-1)*(q-1); //  X = c^e mod (p-1)*(q-1); 
ll e; // d*e≡1(mod Φ(n))     
// e        ，  long long
/*void  get_e( )
{
	for(int i=1;i<=N;i++)
	{
		if( (m*i+1)%d==0)
		{
		   cout<>= 1;
    }
    return res;
}
//         
ll quick_mod(ll a,ll b,ll m)
{
	ll ans=1;
	a=a%m;
	while(b!=0)
	{
		if( b&1 ) ans=mult_mod(ans,a,m)%m;//(ans*a)%m;             
		a=mult_mod(a,a,m)%m;  //a=(a*a)%m; 
	                
		b>>=1;            
	}
	return ans;
	
} 
int main()
{
	cout<

まず拡張ユークリッドで乗算逆元eを求め、(直接列挙は絶対にだめで、long long範囲を超える).
そして求めて、C^e mod mは高速べき乗で解いて、
(ただしa*a%mもlong longを超え、高速べき乗で高速乗を呼び出すしかなく、a=mult_mod(a,a,m)%m;計算a=(a*a)%m)
だから1つの問題は拡張ユークリッドが乗算逆元を求めなければならないことを総合して、急速にべき乗して、急速に3つの知識点を乗じます.
詳細は次のとおりです.
高速べき乗型取り(数が大きい場合、long longを乗算しても超過する解決策)
https://blog.csdn.net/wrf20162305/article/details/80385438
拡張ユークリッドアルゴリズムと求逆元:
https://blog.csdn.net/greenary/article/details/79343176