Python——实现密码学中的模逆运算

00 前情提要

最近临近期末，这学期上的现代密码学要求我们实现密码学上一些小知识点的代码实现，这就从最简单的模逆运算开始。

01 实现背景

先简单介绍一下什么是模逆运算呢，要定义这个运算，需要三个整数。a的模逆元素(对n取模) 为b,意味着a*b mod n= 1。则我们称b为a的模逆。比如17mod26的模逆值为19，其中a = 17 ; m = 26 ; b=19

再比如：
35 mod 7=1 , 3 关于 7 的模逆元素就是5
33 mod 8=1,3 关于 8的模逆元素是3

02 实现源码

#要定义这个运算，需要三个整数。a的模逆元素（对n取模）为b，意味着a*b mod m=1，则称a关于m的模逆为b
def     gcd(a,b):
        while a!=0:
            a,b = b%a,a
        return b
#定义一个函数，参数分别为a,n，返回值为b
def     findModReverse(a,m):#这个扩展欧几里得算法求模逆

        if gcd(a,m)!=1:
            return None
        u1,u2,u3 = 1,0,a
        v1,v2,v3 = 0,1,m
        while v3!=0:
            q = u3//v3
            v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
        return u1%m

print('''"******************欢迎来到模逆计算器******************

            提示信息：a关于m的模逆为b
示范： 17mod26的模逆值为19，其中a = 17 ; m = 26 ; b=19 
'''
)

a = int(input("现在，请输入a值>>>>>"))
m = int(input("现在，请输入m值>>>>>"))
print(f'你所求的b值为：{findModReverse(a,m)}')


print('''"*********************感谢您的使用*********************


                by： 3171106127 XXX


    ''')

部分代码参考自CSDN的博主

03 实现效果