模逆涉及两个数的除法

Question

我知道 (a/b)mod M = ab^-1 mod M

而且当 M 是质数时 b^-1 = b^(M-2)

我必须计算 (121/2)mod M 其中 M = 1000000007 (1e9 + 7)

使用简单除法：(121/2)modM = (60)mod M = 60%M = 60

使用 modular 逆：(121/2)mod M = ( (121 mod M ) * ( 2 ^ (M-2) mod M) ) mod M.

2 ^(M-2) mod 这里的M是500000004 (link: http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?n=2&p=1000000007)

所以上面的表达式变成了(121 mod M * 500000004)mod M = 60500000484 mod M = 500000064

我可能做错了什么？

Answer 1

您不能执行整数除法并期望得到相同的结果。你的计算应该是：

121/2 (mod M) = 60 + 1/2 (mod M) = 60 + 50000004 = (mod M) = 50000064

而不是

121/2 (mod M) = 60 (mod M)

由于没有定义从有理数 Q 到组 Z_n (only defined for rational numbers into natural numbers, floor: Q -> N) you should treat the divisions in Z_n 的 floor 函数，就像使用有理数那样，即使用余数。