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

次の関数はあなたが望むことをすると思います。必要に応じて からlongに変更します。int逆数がない場合は -1 を返し、そうでない場合は範囲​​内の正の数を返します[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;
  }

あなたのアルゴリズムをたどって何が問題なのかを正確に理解することはできませんが、いくつかの一般的なコメントがあります.Eulerのtotient関数は、素因数分解に依存するため、一般的に計算がかなり遅い. 中国剰余定理は、結果 mod 余素を結合するための多くのコンテキストで役立ちますが、ここでは必要ではなく、モジュラスを因数分解する必要があり、非常に遅い操作になるため、この特定の問題が非常に複雑になります。また、再帰を使用するよりも、ループ内で GCD とモジュラー インバースを実装する方が高速ですが、もちろん 2 つの方法は同じように効果的です。

于 2015-06-14T23:59:54.350 に答える
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)。

累乗は、累乗による 2 乗を使用して計算できます。

拡張ユークリッド アルゴリズムを使用して逆をより速く見つける方法について読みたい場合は、このをお読みください。中国の剰余定理はここでは役に立たないと思います。

于 2015-06-14T20:19:32.243 に答える
0

p 素数に対して a^(-1) mod p^k を計算しようとしている場合は、最初に a^(-1) mod p を計算します。ax = 1 (mod p^(k-1)) となる x が与えられると、「ヘンゼル リフト」が可能になります。つまり、a(x + yp^( k-1)) = 1 (mod p^k)。代数を計算すると、 ayp^(k-1) = 1 - ax (mod p^k) --- つまり ay = (1 - ax)/p^(k- 1) (mod p)、p^(k-1) による除算は正確です。これは、a (mod p) のモジュラー逆数を使用して解決できます。

(あるいは、単に a^(p^(k-1)(p-1) - 1) = 1 (mod p^k) であることに注意してください。ヘンセル リフティングについて言及するのは、はるかに一般的に機能するためです。)

于 2015-06-14T19:09:58.923 に答える