Public-Key Cryptography

EEA 拓展欧几里得算法

算法实现

#include<bits/stdc++.h>
using namespace std;
int t1,t0,q,tem;
int eea(int a,int m){//a>m
    if(a==0 || m==0)return t0;
    else{
        q=a/m;
        tem=m;
        m=a%m;
        a=tem;
        tem=t1;
        t1=t0-q*t1;
        t0=tem;
        // cout<<a<<' '<<m<<' '<<q<<' '<<t0<<endl;
        eea(a,m);
    }
}
int gcd(int a, int b)
{
    if(b == 0)return a;
    else return gcd(b , a % b);
}
int main()
{
    int a,m;
    cin>>a>>m;
    //cout<<gcd(a,m)<<endl;
    t1=1,t0=0;
    int esum=eea(a,m);
    cout<<"乘法逆元为"<<esum;
    return 0;
}

测试样例

3个测试用例截图：

1. 243 199

   

2. 15 7

   

   

3. 67 32

CRT 中国剩余定理

ing