75

電卓をあまり使わずに 5^55 モジュラス 221 のモジュラスを計算するにはどうすればよいですか?

そのようなことを計算するための暗号の数論には、いくつかの簡単な原則があると思います。

4

10 に答える 10

102

では、 を計算しますa^b mod m。まず単純なアプローチを採用し、次にそれを改良する方法を見ていきます。

まず、削減しa mod mます。つまり、と となる数a1を見つけます。次に、繰り返しループで乗算と削減を繰り返します。したがって、擬似コードでは次のようになります。0 <= a1 < ma = a1 mod ma1mod m

a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
    p *= a1
    p = p reduced mod m
}

こうすることで、 より大きい数を避けることができますm^2。これが鍵です。より大きい数を避ける理由はm^2、すべてのステップ0 <= p < mで と0 <= a1 < m.

例として、計算してみましょう5^55 mod 221。まず、5すでに削減されていmod 221ます。

  1. 1 * 5 = 5 mod 221
  2. 5 * 5 = 25 mod 221
  3. 25 * 5 = 125 mod 221
  4. 125 * 5 = 183 mod 221
  5. 183 * 5 = 31 mod 221
  6. 31 * 5 = 155 mod 221
  7. 155 * 5 = 112 mod 221
  8. 112 * 5 = 118 mod 221
  9. 118 * 5 = 148 mod 221
  10. 148 * 5 = 77 mod 221
  11. 77 * 5 = 164 mod 221
  12. 164 * 5 = 157 mod 221
  13. 157 * 5 = 122 mod 221
  14. 122 * 5 = 168 mod 221
  15. 168 * 5 = 177 mod 221
  16. 177 * 5 = 1 mod 221
  17. 1 * 5 = 5 mod 221
  18. 5 * 5 = 25 mod 221
  19. 25 * 5 = 125 mod 221
  20. 125 * 5 = 183 mod 221
  21. 183 * 5 = 31 mod 221
  22. 31 * 5 = 155 mod 221
  23. 155 * 5 = 112 mod 221
  24. 112 * 5 = 118 mod 221
  25. 118 * 5 = 148 mod 221
  26. 148 * 5 = 77 mod 221
  27. 77 * 5 = 164 mod 221
  28. 164 * 5 = 157 mod 221
  29. 157 * 5 = 122 mod 221
  30. 122 * 5 = 168 mod 221
  31. 168 * 5 = 177 mod 221
  32. 177 * 5 = 1 mod 221
  33. 1 * 5 = 5 mod 221
  34. 5 * 5 = 25 mod 221
  35. 25 * 5 = 125 mod 221
  36. 125 * 5 = 183 mod 221
  37. 183 * 5 = 31 mod 221
  38. 31 * 5 = 155 mod 221
  39. 155 * 5 = 112 mod 221
  40. 112 * 5 = 118 mod 221
  41. 118 * 5 = 148 mod 221
  42. 148 * 5 = 77 mod 221
  43. 77 * 5 = 164 mod 221
  44. 164 * 5 = 157 mod 221
  45. 157 * 5 = 122 mod 221
  46. 122 * 5 = 168 mod 221
  47. 168 * 5 = 177 mod 221
  48. 177 * 5 = 1 mod 221
  49. 1 * 5 = 5 mod 221
  50. 5 * 5 = 25 mod 221
  51. 25 * 5 = 125 mod 221
  52. 125 * 5 = 183 mod 221
  53. 183 * 5 = 31 mod 221
  54. 31 * 5 = 155 mod 221
  55. 155 * 5 = 112 mod 221

したがって、5^55 = 112 mod 221.

ここで、二乗による累乗を使用してこれを改善できます。log bこれは、累乗をの代わりに乗算のみを必要とするように減らす有名なトリックですb。上で説明したアルゴリズムの 2 乗によるべき乗の改善により、右から左へのバイナリ法になることに注意してください。

a1 = a reduced mod m
p = 1
while (b > 0) {
     if (b is odd) {
         p *= a1
         p = p reduced mod m
     }
     b /= 2
     a1 = (a1 * a1) reduced mod m
}

したがって、バイナリで 55 = 110111 であるため、

  1. 1 * (5^1 mod 221) = 5 mod 221
  2. 5 * (5^2 mod 221) = 125 mod 221
  3. 125 * (5^4 mod 221) = 112 mod 221
  4. 112 * (5^16 mod 221) = 112 mod 221
  5. 112 * (5^32 mod 221) = 112 mod 221

したがって、答えは5^55 = 112 mod 221です。これが機能する理由は、

55 = 1 + 2 + 4 + 16 + 32

となることによって

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
     = 5 * 25 * 183 * 1 * 1 mod 221
     = 22875 mod 221
     = 112 mod 221

5^1 mod 221、などを計算するステップで、 =5^2 mod 221に注意します。これは、最初に を計算して削減し、次にこれを 2 乗して削減してなどを取得できるためです。5^(2^k)5^(2^(k-1)) * 5^(2^(k-1))2^k = 2^(k-1) + 2^(k-1)5^1mod 221mod 2215^2 mod 221

上記のアルゴリズムは、この考え方を形式化したものです。

于 2010-02-01T15:36:12.493 に答える
29

ジェイソンの答えに追加するには：

指数のバイナリ展開を使用して、プロセスを高速化できます (指数が非常に大きい場合に役立つ場合があります)。最初に 5, 5^2, 5^4, 5^8 mod 221 を計算します - これは 2 乗を繰り返すことによって行います。

 5^1 = 5(mod 221)
 5^2 = 5^2 (mod 221) = 25(mod 221)
 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)

今、私たちは書くことができます

55 = 1 + 2 + 4 + 16 + 32

so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 
        = 5   * 25  * 625 * 1    * 1 (mod 221)
        = 125 * 625 (mod 221)
        = 125 * 183 (mod 183) - because 625 = 183 (mod 221)
        = 22875 ( mod 221)
        = 112 (mod 221)

非常に大きな指数の場合、これがはるかに高速になることがわかります（bでは線形ではなく対数だと思いますが、確実ではありません。）

于 2010-02-01T15:53:26.383 に答える
12 
/* The algorithm is from the book "Discrete Mathematics and Its
   Applications 5th Edition" by Kenneth H. Rosen.
   (base^exp)%mod
*/

int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int power = base % mod;

    for (int i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}
于 2012-01-23T14:03:18.953 に答える
3 
5^55 mod221

= (   5^10         * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221    

= ( ( 5^10) mod221 * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= (   77           * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221   

= ( ( 77           * 5^10) mod221 * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= (   183                         * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= ( ( 183                         * 5^10) mod221 * 5^10          * 5^10          * 5^5) mod221 

= (   168                                        * 5^10          * 5^10          * 5^5) mod221 

= ( ( 168                                        * 5^10) mod 221 * 5^10          * 5^5) mod221 

= (   118                                                        * 5^10          * 5^5) mod221 

= ( ( 118                                                        * 5^10) mod 221 * 5^5) mod221 

= (   25                                                                         * 5^5) mod221 

=     112
于 2011-08-18T19:15:53.367 に答える
2

これは IBAN 検証用に作成したコードの一部です。お気軽にご利用ください。

    static void Main(string[] args)
    {
        int modulo = 97;
        string input = Reverse("100020778788920323232343433");
        int result = 0;
        int lastRowValue = 1;

        for (int i = 0; i < input.Length; i++)
        {
            // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number                                                                        
            if (i > 0)
            {
                lastRowValue = ModuloByDigits(lastRowValue, modulo);
            }
            result += lastRowValue * int.Parse(input[i].ToString());
        }
        result = result % modulo;
        Console.WriteLine(string.Format("Result: {0}", result));            
    }

    public static int ModuloByDigits(int previousValue, int modulo)
    {
        // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number                        
        return ((previousValue * 10) % modulo);
    }
    public static string Reverse(string input)
    {
        char[] arr = input.ToCharArray();
        Array.Reverse(arr);
        return new string(arr);
    }
于 2010-02-11T17:53:25.387 に答える
2

中国の剰余定理は 221 = 13 * 17 として最初に頭に浮かびます。したがって、これを 2 つの部分に分解し、最終的に結合される部分を 13 と 17 の mod に分けます。次に、いくつかの証拠があると思います。 of a^(p-1) = 1 mod p すべての非ゼロ a に対して、5^55 が 13*4=52 の mod 13 の場合に 5^3 になるため、問題を軽減するのにも役立ちます。「Finite Fields」の件名の下を見ると、これを解決する方法について良い結果が得られるかもしれません。

編集: 要因について言及する理由は、13^2 * 17^4 mod 221 のようなものを試したかのように、ゼロをゼロ以外の要素に因数分解する方法を作成するためです。答えは 13*17=221 からゼロです。多くの大きな数は素数にはなりませんが、大きな素数は暗号や数学の他の分野でよく使用されるため、大きな素数を見つける方法があります。

于 2010-02-01T15:45:32.077 に答える
2

あなたが探しているのはモジュラ累乗、特にモジュラバイナリ累乗です。このウィキペディアのリンクには疑似コードがあります。

于 2010-02-01T15:48:07.297 に答える
2

Javaでのジェイソンの答え（注i < exp）。

private static void testModulus() {
    int bse = 5, exp = 55, mod = 221;

    int a1 = bse % mod;
    int p = 1;

    System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod);

    for (int i = 1; i < exp; i++) {
        p *= a1;
        System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod);
        p = (p % mod);
    }

}
于 2016-01-09T23:45:34.030 に答える
1

これは剰余累乗 ( https://en.wikipedia.org/wiki/Modular_exponentiation ) と呼ばれます。

次の式があるとします。

19 ^ 3 mod 7

19 に直接電力を供給する代わりに、次のことができます。

(((19 mod 7) * 19) mod 7) * 19) mod 7

ただし、これには多くの連続した乗算が原因で時間がかかる可能性があるため、二乗値で乗算できます。

x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N

累乗剰余アルゴリズムは、次のことを前提としています。

x ^ y == (x ^ |y/2|) ^ 2 if y is even
x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd

したがって、再帰的なべき乗剰余アルゴリズムは、Java では次のようになります。

/**
* Modular exponentiation algorithm
* @param x Assumption: x >= 0
* @param y Assumption: y >= 0
* @param N Assumption: N > 0
* @return x ^ y mod N
*/
public static long modExp(long x, long y, long N) {
    if(y == 0)
        return 1 % N;

    long z = modExp(x, Math.abs(y/2), N);

    if(y % 2 == 0)
        return (long) ((Math.pow(z, 2)) % N);
    return (long) ((x * Math.pow(z, 2)) % N);
}

y と 0 の比較の場合に誤った戻り値で間違いを発見した@chuxに感謝します。

于 2017-10-15T20:00:14.490 に答える
1

Cによるジェイソンの答えの別の実装を提供するだけです.

ジェイソンの説明に基づいて、クラスメートと話し合った後、パフォーマンスをあまり気にしないのであれば、再帰バージョンがより好きです。

例えば：

#include<stdio.h>

int mypow( int base, int pow, int mod ){
    if( pow == 0 ) return 1;
    if( pow % 2 == 0 ){
        int tmp = mypow( base, pow >> 1, mod );
        return tmp * tmp % mod;
    }
    else{
        return base * mypow( base, pow - 1, mod ) % mod;
    }
}

int main(){
    printf("%d", mypow(5,55,221));
    return 0;
}
于 2013-10-15T05:58:20.060 に答える