整数判断是否互质并求逆元的 python 实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了整数判断是否互质并求逆元的 python 实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含832字，纯文字阅读大概需要2分钟。

内容图文

算法来自《密码学原理与实践》page129

#!/usr/dev/python
#-*- coding:utf-8 -*-

'''
Extended Euclidean algorithm(a,b)
code by ShaNgZ
algorithm from <cryptography theory and pratice,third editon>
2019_01_09
'''

a = input("a=")
b = input("b=")

s0 = 0
s  = 1
t0 = 0
t  = 1
q  = a/b
r  = a%b
# Ri = Si*R0 + Ti*R1

def euclidean_algorithen():
	pass

def extended_euclidean():
	global a,b,s0,s,t0,t,q,r
	ex_a = a
	ex_b = b
	ex_s0 = s0
	ex_s = 1
	ex_t0 = 0
	ex_t = 1
	ex_q = q
	ex_r = r
	while(ex_r>0):
		
		temp = ex_t0-ex_q*ex_t
		ex_t0 = ex_t
		ex_t = temp

		temp = ex_s0-ex_q*ex_s
		ex_s0 = ex_s
		ex_s = temp

		ex_a = ex_b
		ex_b = ex_r
		ex_q = ex_a/ex_b
		ex_r = ex_a%ex_b
	ex_r = ex_b
	print "exr_gcd(%d,%d) = "  % (a,b) + str(ex_r)
	if ex_r == 1:
		print "inverse(%d) mod %d = %d" % (a,b,ex_s)

	#comment: r=gcd(a,b) and sa+tb=r

def multiplicative_inverse():
	pass

if __name__ == '__main__':
	extended_euclidean()

内容总结

以上是互联网集市为您收集整理的整数判断是否互质并求逆元的 python 实现全部内容，希望文章能够帮你解决整数判断是否互质并求逆元的 python 实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端