求助：Affine加密中Modular Inverse的正确计算方法

嘿，我来帮你理清这个模逆元的困惑！首先得明确：你用的公式(n % 26 + 26) % 26根本不是求模逆元的方法——这个公式只是用来把任意整数（尤其是负数）转换成0到25之间的等价模26值，和模逆元完全是两码事，难怪结果不对呢。

先搞懂什么是模逆元 #

对于整数a和模数m，模逆元a'需要满足的核心条件是：(a * a') ≡ 1 mod m。而且只有当a和m互质（也就是它们的最大公约数gcd(a,m)=1）时，逆元才存在。比如你的例子里，5和26互质，所以存在逆元21，因为5*21=105，105%26=1，完美符合条件。

给你几种实用的模逆元求解方法 #

1. 扩展欧几里得算法（通用首选）

这是求模逆元的标准算法，核心思路是找到整数x和y，使得a*x + m*y = gcd(a,m)。当a和m互质时，gcd是1，此时x就是a模m的逆元（如果x是负数，再用你那个范围调整公式转成正数就行）。

拿你的例子a=5，m=26一步步算：

• 26 = 5*5 + 1
• 5 = 1*5 + 0
• 回代推导：1 = 26 - 5*5 → 也就是5*(-5) + 26*1 = 1
• 这里x=-5，转成模26的正数：(-5 %26 +26)%26=21，就是我们要的逆元。

2. 暴力枚举（小模数时超简单）

因为26是个很小的数，直接从1到25挨个试就行，看哪个数和5相乘后模26等于1：

• 5*1=5 mod26≠1
• 5*2=10≠1
• ...
• 5*21=105，105减去4个26（104）正好剩1，搞定！

3. 费马小定理（仅限模数是质数的情况）

如果你的模数是质数（比如字母表长度是29），那可以用这个快捷公式：a^(m-2) ≡ a' mod m。不过26不是质数，所以这个方法在这里用不上，记下来备用就好。

最后再划个重点 #

你之前用的公式是用来调整模运算结果范围的，不是求逆元的工具。选上面的任意一种方法（小模数推荐暴力枚举，通用场景用扩展欧几里得），就能得到正确的模逆元啦。

内容的提问来源于stack exchange，提问作者aymen medjader