0

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

这就是我的理解：

如果 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' ，我使用了Extended Euclidean Algorithm。 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 .

但是在做了这一切之后，我得到了错误的答案。

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

非常感谢您。

4

3 回答 3

2

a模的逆仅在且互质m时才存在。如果它们不是互质的，那么没有任何帮助。例如：mod的倒数是什么？am24

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

所以没有逆。

这确实可以通过使用扩展欧几里得算法来计算（虽然我不确定你是否做对了），但在我看来，最简单的方法是使用欧拉定理：

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)

totient 函数phi在哪里：

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).

然后可以使用通过平方取幂来计算取幂。

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

于 2015-06-14T20:19:32.243 回答
2

我相信以下功能会做你想做的事。适当时从 更改long为。int如果没有逆，则返回 -1，否则返回 range 中的正数[0..m)。

  public static long inverse(long a, long m) { // mult. inverse of a mod m
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    long tmp;
    while (nr != 0) {
      long q = r/nr;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) return -1; // no inverse
    if (t < 0) t += m;
    return t;
  }

我不能按照你的算法来确切地知道它有什么问题，但我有一些一般性的评论：欧拉的 totient 函数通常计算起来相当慢，这取决于它对素数分解的作用。中国剩余定理在许多情况下对于组合结果 mod coprimes 很有用，但它没有必要在这里一次又一次地过度复杂化这个特定问题，因为你最终不得不考虑你的模数，这是一个非常缓慢的操作。而且在循环中实现 GCD 和模逆比使用递归更快，当然这两种方法同样有效。

于 2015-06-14T23:59:54.350 回答
0

如果您尝试计算 p 素数的 a^(-1) mod p^k，请首先计算 a^(-1) mod p。给定一个 x 使得 ax = 1 (mod p^(k-1))，你可以“Hensel lift”---你正在寻找 0 和 p-1 之间的 y 使得 a(x + yp^( k-1)) = 1 (mod p^k)。做一些代数，你会发现你正在寻找 y 使得 ayp^(k-1) = 1 - ax (mod p^k)---ie = (1 - ax)/p^(k- 1) (mod p)，其中除以 p^(k-1) 是精确的。您可以使用 (mod p) 的模逆来解决此问题。

（或者，只需注意 a^(p^(k-1)(p-1) - 1) = 1 (mod p^k)。我提到 Hensel 提升是因为它具有更大的通用性。）

于 2015-06-14T19:09:58.923 回答