西电现代密码学大作业1-欧几里德及其扩展算法的实现

• 一、实验名称：欧几里德及其扩展算法的实现
• 二、实验原理：学习及其扩展算法。
• 三、实验目的：
• 四、实验内容：
• 五、实验器材（设备、元器件）：
• 六、实验思路，代码及运行结果：
• • • • • 1．解题思路或方法：
        • 2.代码
        • 运行结果：

创新互联公司是一家集网站建设,新津县企业网站建设,新津县品牌网站建设,网站定制,新津县网站建设报价,网络营销,网络优化,新津县网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。一、实验名称：欧几里德及其扩展算法的实现 二、实验原理：学习及其扩展算法。 三、实验目的：

1、掌握欧几里德算法求解大公因子；
2、掌握欧几里德扩展算法求解乘法逆元。

四、实验内容：

1．编程实现：输入两个整数a和b，利用欧几里德算法计算两个整数的大公因子gcd(a,b)。
2. 编程实现欧几里德扩展算法，计算gcd(a,b)=ax+by中的x和y。其中一个整数a是你的学号，另一个整数为素数p= f4f47f05794b256174bba6e9b396a7707e563c5b，求整数a在模p下的逆元。

五、实验器材（设备、元器件）：

一台PC，安装Windows 10操作系统及VC++\Python开发环境等。

六、实验思路，代码及运行结果： 1．解题思路或方法：

欧几里德算法：
众所周知，欧几里得算法gcd是用来求两个整数的大公因子。其中gcd（a,0）或gcd（0，b）分别等于a和b。对于任意两个整数a,b(对其大小没有要求，不妨设a>=b),有gcd(a,b)=gcd(b,a mod b)，这是欧几里德算法基本内容。只需a mod b等于0时，此时式子中的a自然是a和b的大公因子。
欧几里德拓展算法：
欧几里得拓展算法是用来计算乘法逆元的，并且两个数字大公约数为1。我的学号是：XXXXXXXXXX(我的学号是7位，就不拿出来展示了，就用X表示了)，素数p转为十进制后结果为：1398446195032410252040217410173702390108694920283。
既然已知p是素数，a又比p小，故a与p是互质的，符合欧几里德拓展算法的要求。给出正整数a和p，扩展的欧几里得算法可以计算a和p的大公约数d，同时得到两个整数x和y满足：d=gcd(a, b) = ax+by。
根据扩展的欧几里得算法求乘法逆元：简单说，如果有：ab mod p = 1成立，则称a和b互为模p意义下的乘法逆元（a与b均与q互质）。若a与p互质，那么d=gcd(a, p)=1, 即 ax + py = 1, 于是 py = (-x)a+1
也即：ax(mod p)=1，于是x即为a在模p意义下的乘法逆元。
在欧几里得算法中，可以把过程写的更清晰一些：
（仍以d=gcd(a,p)=ax+py为例）
a = q1p + p1, p1=ax1+by1;
p = q2p1 + p2, p2=ax2+by2;
p1 = q3p2 + p3, p3=ax3+by3;
… … … …
p(n-2) = q(n)p(n-1)+p(n), p(n)=ax(n)+by(n)
p(n-1) = q(n+1)p(n)+0
则：p(i-2) = q(i)p(i-1)+p(i)或 p(i) = p(i-2) - p(i-1)q(i)
又p(i-1) = ax(i-1)+by(i-1)且p(i-2) = ax(i-2)+by(i-2)
带入得：
x(i) = x(i-2)-qx(i-2)
y(i) = y(i-2)-qy(i-2)
求出x（i）（i为大）的值，即为a在模p意义下的乘法逆元。
正常来说完成上述代码，实验到这里应该结束了，但是由于实验所涉及的a和p数字太大，c语言的代码并不能
直接运算，故在这里我们选择使用Python进行计算。

2.代码

欧几里得算法（c语言)：

#includeint gcd(int a, int b)
{	if (b == 0) return a;
	else
	{return gcd(b, a % b);
	}
}
int main()
{int a, b,temp;
	scanf_s("%d %d", &a, &b);
	if (a< b)
	{temp = a;
		a = b;
		b = temp;
	}
	temp=gcd(a, b);
	printf("%d和%d的大公约数是%d", a, b, temp);
	return 0;
}

根据扩展的欧几里得算法求乘法逆元：

#includeusing namespace std;

int exgcd(int a, int b, int& x, int& y) {if (b == 0)
    {//最里面ax+0=a的情况,注意此时a经过多次递归已经不是刚开始的啊
        x = 1;
        y = 0;
        return a;
    }
    //要先调用ngcd来进到最里层确定x，y的值，从逐步到外层计算出x，y
    int ngcd = exgcd(b, a % b, x, y);
    //根据相关理论有如下的逆公式 x==y1,y==x1-a/b*y1
    int temp = x; 
    x = y;
    y = temp - a / b * y;
    return ngcd;
}
int inverse(int a, int p) {int x, y, gcd;
    gcd = exgcd(a, p, x, y);
    if (gcd == 1) {x = (x % p + p) % p;//保证x为正数;
        return x;
    }
    else {cout<< "a,p不互质";
        return 0;
    }
}
int main() {//实际上是求ax + py = gcd(a,p) = 1  /a,p互质
    int a, p;
    cout<< "请输入 a p"<< endl;
    cin >>a >>p;
    cout<< "a mod p的乘法逆元是"<< inverse(a, p);

    return 0;
}

将以上的所有c语言代码转换为Python代码如下：

a=int(input("请输入数字a：\n"))
p=str(input("请输入数字p：\n"))
p1=int(p,16)
#print(a,p1) 测试程序是否正确
x=1
y=0
def exgcd(a,b):
    global x
    global y
    if(b==0):
        x=1
        y=0
        return a
    ngcd=exgcd(b,a%b)
    temp=x
    x=y
    y=temp-a//b*y
    return ngcd
def inverse(a,p):
    global x
    gcd=exgcd(a,p)
    if(gcd==1):
        x=(x%p+p)%p
        return x
    else:
        print("a,p不互质")
c=inverse(a,p1)
print("a mod p的乘法逆元是：",c)

运行结果：

欧几里得算法：

在Python的基础上使用扩展的欧几里得算法求乘法逆元：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：XD现代密码学大作业-欧几里德及其扩展算法的实现-创新互联
文章出自：http://scyanting.com/article/ceghoi.html