如何求解函数f(x)=(6x mod 13)的逆函数？

嘿，我完全懂你卡在这儿的感觉！普通函数交换x、y解y的路子在模运算场景下得换个思路——核心是找模逆元，咱们一步步把这个问题拆明白：

问题本质：找6在模13下的逆元 #

你已经得到了交换后的方程：x = (6*y) mod 13，其实我们要做的是把y单独解出来。这时候需要找到一个整数k，使得6*k ≡ 1 mod 13——这个k就是6在模13下的逆元，找到它之后，两边同时乘k就能消掉6，直接得到y的表达式。

怎么找这个逆元？ #

因为13是个小质数，咱们可以用试数法快速搞定：

• 6*1=6 mod13≠1
• 6*2=12 mod13≠1
• 6*3=18≡5 mod13≠1
• 6*4=24≡11 mod13≠1
• 6*5=30≡4 mod13≠1
• 6*6=36≡10 mod13≠1
• 6*7=42≡3 mod13≠1
• 6*8=48≡9 mod13≠1
• 6*9=54≡2 mod13≠1
• 6*10=60≡8 mod13≠1
• 6*11=66≡1 mod13 ✔️

没错，6和11在模13下互为逆元，因为6*11=66，66除以13余1。

求解逆函数 #

现在把逆元代入方程，两边同时乘以11：

11*x ≡ 11*6*y mod13

因为11*6≡1 mod13，所以右边就简化为y，左边是11*x mod13，最终逆函数就是：
f⁻¹(x) = (11*x) mod13

验证一下 #

咱们拿几个例子测试：

• 原函数：f(2) = (62) mod13 =12，逆函数：f⁻¹(12)=(1112)mod13=132 mod13=2，完美还原
• 原函数：f(5)=(65)mod13=30 mod13=4，逆函数：f⁻¹(4)=(114)mod13=44 mod13=5，也完全正确

内容的提问来源于stack exchange，提问作者Sayan Chakraborti