algorithm - 当 m 不是素数时，如何找到数字的反模，即 (a%m)

Question

我搜索了这个问题的答案，我得到了各种有用的链接，但是当我实现这个想法时，我得到了错误的答案。

这是我的理解:

如果m是素数，那就很简单了。任意数“a”的反模可以计算为:inverse_mod(a) = (a^(m-2))%m

但是当 m 不是质数时，我们必须找到 m 的质因数，即 m= (p1^a1)*(p2^a2)*....*(pk^ak). 这里 p1,p2,....,pk 是 m 的质因数和a1,a2,....,ak是他们各自的权力。

然后我们必须计算:

m1 = a%(p1^a1),

m2 = a%(p2^a2), 

.......

mk = a%(pk^ak)

然后我们必须使用中国剩余定理 ( https://en.wikipedia.org/wiki/Chinese_remainder_theorem ) 合并所有这些余数

我实现了这个想法 m=1000,000,000，但我仍然得到错误的答案。

这是我对 m=1000,000,000 不是素数的解释

m= (2^9)*(5^9) 其中 2 和 5 是 m 的质因数。

设 a 是必须计算反模 m 的数。

m1 = a%(2^9) = a^512

m2 = a%(5^9) = a^1953125

Our answer will be = m1*e1 + m2*e2

where e1= {  1 (mod 512)

             0 (mod 1953125)
          }
  and e2= {     1 (mod 1953125)

                0 (mod 512)
           } 

现在要计算 'e1' 和 'e2' ，我使用了扩展欧几里德算法。 https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

代码是:

    void extend_euclid(lld a,lld b,lld& x,lld& y)
    {
          if(a%b==0)
          {
             x=0;
             y=1;
             return ;
          }
          extend_euclid(b,a%b,x,y);
          int tmp=x;
          x=y;
          y=tmp-(a/b)*y;
    }

Now e1= 1953125*y and e2=512*y;

So, Our final answer will be = m1*e1 + m2*e2 .

但在完成所有这些之后，我得到了错误的答案。

请解释并指出我在理解中国剩余定理时所犯的任何错误。

非常感谢。

Answer 1

只有 a 和 m 为 coprime 时，a 模 m 的逆运算才存在.如果它们不是互质的，则没有任何帮助。例如:2 mod 4 的逆是什么？

2*0 = 0 mod 4
2*1 = 2 mod 4
2*2 = 0 mod 4
2*3 = 2 mod 4

所以没有逆。

这确实可以通过使用扩展欧几里得算法来计算(虽然我不确定你是否做对了)，但在我看来，最简单的方法是使用 Euler's theorem :

a^phi(m) = 1 (mod m)
a*a^(phi(m) - 1) = 1 (mod m)
=> a^(phi(m) - 1) is the invers of a (mod m)

phi 是 totient function :

phi(x) = x * (1 - 1/f1)(1 - 1/f2)...(1 - 1/fk)
where fi > 1 is a divisor of x (not necessarily a prime divisor)

phi(36) = 36(1 - 1/2)(1 - 1/3)(1 - 1/4)(1 - 1/6)(1 - 1/9)(1 - 1/12)(1 - 1/18)(1 - 1/36)

所以它可以在 O(sqrt n) 中计算。

然后可以使用 exponentiation by squaring 计算取幂.

如果您想了解如何使用扩展欧几里得算法更快地求逆，请阅读 this .我认为中国剩余定理在这里没有帮助。