# 模逆元
已知在有限元256中: ((a*17)+133)mod256 对于密文进行逆向解密 ((a-133)/17)mod256会导致数据丢失
因此引入模逆元
学习时碰到一个问题：b=(a×k)+c mod m 为什么可以通过a≡b′× X mod m推导出a来。
这里的 a 是原始数据，k 是一个常数因子，c 是一个常数偏移，m 是模数（通常是一个素数形式，以保证逆元的存在），而 b 是加密后的结果。
脑子笨想了好久 然后发现还得是写公式推导。
已知 b k c m 求a
“`
由模逆元得到x
kx≡1 mod m
首先，从 b 中减去 c：b′=b−c
然后，将结果乘以 k 的模逆元 x：a≡ b′ * x mod m
这样，我们就可以得到原始的 a，因为：
a≡(b−c)*xmod m
a≡(a*k+c−c)*xmod m //此处注意 通过推导可知b≡(a*k+c)mod m
a≡(a*k)*xmod m //到这里就很明显啦 kx≡1 mod m带入
a≡a*(kx)mod m
由于 kx≡1mod m，我们有：
a≡a*1mod m
a≡amod m
从而有a=(b-c)*x mod m
而在c语言中char自动mod 256 顾在代码中所有mod 256都被省略掉了
“`
寻找模逆元exp
```
def extended_gcd(a, b):
"""使用扩展欧几里得算法计算最大公约数和贝祖等式系数。"""
if a == 0:
return b, 0, 1
else:
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def mod_inverse(a, m):
"""计算a模m的模逆元。"""
gcd, x, _ = extended_gcd(a, m)
if gcd != 1:
raise ValueError("Modular inverse does not exist.")
else:
return x % m
# 寻找17模256的逆元
a = 17
m = 256
inverse = mod_inverse(a, m)
print(f"The modular inverse of {a} mod {m} is: {inverse}")
