webentwicklung-frage-antwort-db.com.de

Wie berechnet man den Modul großer Zahlen?

Wie berechnet man den Modul von 5 ^ 55 Modul 221 ohne viel Taschenrechner?

Ich denke, es gibt einige einfache Prinzipien in der Zahlentheorie in der Kryptographie, um solche Dinge zu berechnen.

64
Priyank Bolia

Okay, Sie möchten _a^b mod m_ berechnen. Zuerst werden wir einen naiven Ansatz verfolgen und dann sehen, wie wir ihn verfeinern können.

Reduzieren Sie zunächst _a mod m_. Das heißt, finden Sie eine Zahl _a1_, so dass _0 <= a1 < m_ und _a = a1 mod m_. Dann mehrmals in einer Schleife mit _a1_ multiplizieren und erneut reduzieren _mod m_. Also im Pseudocode:

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

Auf diese Weise vermeiden wir Zahlen, die größer als _m^2_ sind. Das ist der Schlüssel. Der Grund, warum wir Zahlen vermeiden, die größer als _m^2_ sind, ist, dass bei jedem Schritt _0 <= p < m_ und _0 <= a1 < m_.

Als Beispiel berechnen wir _5^55 mod 221_. Erstens ist _5_ bereits reduziert _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_

Daher _5^55 = 112 mod 221_.

Jetzt können wir dies verbessern, indem wir Potenzierung durch Quadrieren ; Dies ist der berühmte Trick, bei dem wir die Potenzierung auf das Erfordernis von nur _log b_ Multiplikationen anstelle von b reduzieren. Beachten Sie, dass mit dem Algorithmus, den ich oben beschrieben habe, die Potenzierung durch Quadrieren der Verbesserung, Sie am Ende die binäre Methode von rechts nach links erhalten.

_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
}
_

Somit ist da 55 = 110111 in binär

  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

Daher lautet die Antwort _5^55 = 112 mod 221_. Der Grund dafür ist, dass

_55 = 1 + 2 + 4 + 16 + 32
_

damit

_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
_

In dem Schritt, in dem wir _5^1 mod 221_, _5^2 mod 221_ usw. berechnen, stellen wir fest, dass 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)), weil 2^k = 2^(k-1) + 2^(k-1), so dass wir zuerst _5^1_ berechnen und dann _mod 221_ reduzieren können und reduzieren Sie _mod 221_, um _5^2 mod 221_ usw. zu erhalten.

Der obige Algorithmus formalisiert diese Idee.

93
jason

Zu Jasons Antwort hinzufügen:

Sie können den Prozess beschleunigen (was für sehr große Exponenten hilfreich sein kann), indem Sie die binäre Erweiterung des Exponenten verwenden. Berechnen Sie zuerst 5, 5 ^ 2, 5 ^ 4, 5 ^ 8 mod 221 - Sie tun dies durch wiederholtes Quadrieren:

 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)

Jetzt können wir schreiben

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)

Sie können sehen, wie dies für sehr große Exponenten viel schneller sein wird (ich glaube, es ist log im Gegensatz zu linear in b, aber nicht sicher)

27
Tom Smith
/* 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;
}
12
Timothy Kwok
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
3
Udhayakumar.c

Dies ist Teil des Codes, den ich für die IBAN-Validierung erstellt habe. Fühlen Sie sich frei zu verwenden.

    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);
    }
2

Chinese Remainder Theorem kommt als Anfangspunkt in den Sinn: 221 = 13 * 17. Also, teilen Sie dies in zwei Teile auf, die am Ende kombiniert werden, einer für Mod 13 und einer für Mod 17. Zweitens glaube ich Es gibt einen Beweis für a ^ (p-1) = 1 mod p für alle Nicht-Null-Werte von a, was auch dazu beiträgt, Ihr Problem zu verringern, da 5 ^ 55 für den Mod-13-Fall 5 ^ 3 wird, da 13 * 4 = 52. Wenn Sie unter dem Thema "Finite Fields" nachschauen, finden Sie möglicherweise gute Ergebnisse, wie Sie dieses Problem lösen können.

EDIT: Der Grund, warum ich die Faktoren erwähne, ist die Möglichkeit, Null in Elemente von Nicht-Null zu faktorisieren, als ob Sie etwas wie 13 ^ 2 * 17 ^ 4 mod 221 versucht hätten. Die Antwort ist null, da 13 * 17 = 221. Viele große Zahlen werden keine Primzahl sein, obwohl es große Möglichkeiten gibt, große Primzahlen zu finden, da sie häufig in der Kryptographie und in anderen Bereichen der Mathematik verwendet werden.

2
JB King

Was Sie suchen, ist die modulare Exponentiation, insbesondere die modulare binäre Exponentiation. Dieser Wikipedia-Link hat einen Pseudocode.

2
job

Jasons Antwort in Java (Anmerkung 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);
    }

}
1
Martin Pfeffer

Dies wird als modulare Exponentiation bezeichnet ( https://en.wikipedia.org/wiki/Modular_exponentiation ). 

Nehmen wir an, Sie haben den folgenden Ausdruck:

19 ^ 3 mod 7

Anstatt 19 direkt mit Strom zu versorgen, können Sie Folgendes tun:

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

Dies kann jedoch aufgrund vieler aufeinanderfolgender Multiplikationen sehr lange dauern, sodass Sie die Quadratwerte multiplizieren können:

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

Der modulare Exponentiationsalgorithmus macht Annahmen, die:

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

Und so wird der rekursive modulare Exponentiationsalgorithmus in Java folgendermaßen aussehen:

/**
* 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);
}

Besonderer Dank geht an @chux für den gefundenen Fehler mit falschem Rückgabewert beim Vergleich von y und 0. 

1
Stepan Pogosyan

Geben Sie einfach eine weitere Implementierung der Antwort von Jason durch C.

Nach Diskussionen mit meinen Klassenkameraden, basierend auf Jasons Erklärung, mag ich die rekursive Version mehr, wenn Sie sich nicht besonders für die Leistung interessieren:

Zum Beispiel:

#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;
}
0
Boris