一个求乘法逆元的打表方法

前几天看到Neal_Wu的youtube视频中用的一个求INV11(对11的乘法逆元)在mod一个大数M下的方法. 视频链接: https://www.youtube.com/watch?v=8ukwV6rCvPg&t=367s

假设, 我们在11*i ≡ 1 mod 31中求i, 那么相当于我们在求一个x使得11 * ((x*31+1) / 11) ≡ 1 mod 31 where x∈[1,2,3,….].

然后, 我们从1开始, 逐个试(x*31+1) % 11 ?= 0中的这个x是多少, 因为只有整除的x才是我们想要的.

这里我们从1一直试到6, 然后发现(6*31+1) % 11 = 0, 所以这里的(6*31+1) / 11 = 17的17就是INV11在模31下. 我们直接记录这个INV11可以减少运算时间. 这里的31是很小的数字, 有很多别的方法也可以求, 比如费马小定理, 但是如果是很大的数字就用这个比较省时间.