怎样求axmodp=1的逆x比如说a=79,p=3220

Question

怎样求ax mod p=1的逆x
比如说a=79,p=3220

Answer 1

不知道你有没有学过辗转相除法?
辗转相除法则是寻找ax+py=1的解,这时候p是质数的条件不重要,只需要gcd(a,p)=1,对a,p做辗转相除序列就行了,比如说p=am+r,那么ax+py=a(x+my)+ry,归约成关于(r,a)的问题,对于你的例子,
17=10+7
10=7+3
7=2×3+1
从最后一个式子倒推回去得到
1=7-2×3=7-2×(10-7)=3×7-2×10=3×(17-10)-2×10=3×17-5×10
所以可以取x=-5,或者说x=12