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.

Okay, du willst also rechnen a^b mod m. 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 Nummer, a1damit 0 <= a1 < mund a = a1 mod m. Dann wiederholt in einer Schleife mit multiplizieren a1und wieder 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 sind m^2. Das ist der Schlüssel. Der Grund, warum wir Zahlen vermeiden, die größer sind als, m^2ist, dass bei jedem Schritt 0 <= p < mund 0 <= a1 < m.

Als Beispiel berechnen wir 5^55 mod 221. Erstens 5ist 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 die Potenzierung durch Quadrieren verwenden . Dies ist der berühmte Trick, bei dem wir die Potenzierung so reduzieren, dass statt nur log bMultiplikationen erforderlich sind b. Beachten Sie, dass Sie mit dem oben beschriebenen Algorithmus, der Potenzierung durch Quadrierverbesserung, die Binärmethode 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 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, warum dies funktioniert, ist, weil

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 usw. berechnen 5^1 mod 221, stellen 5^2 mod 221wir fest, dass 5^(2^k)= 5^(2^(k-1)) * 5^(2^(k-1))weil, 2^k = 2^(k-1) + 2^(k-1)damit wir zuerst berechnen 5^1und reduzieren können mod 221, dies dann quadrieren und reduzieren mod 221, um 5^2 mod 221usw. zu erhalten .

Der obige Algorithmus formalisiert diese Idee.

Um Jasons Antwort zu ergänzen:

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

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

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

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

Der chinesische Restsatz kommt als Anfangspunkt in den Sinn: 221 = 13 * 17. Teilen Sie dies also in zwei Teile auf, die am Ende kombiniert werden, einen für Mod 13 und einen für Mod 17. Zweitens glaube ich, dass es einige Beweise gibt von a ^ (p-1) = 1 mod p für alle ungleich Null a, was auch dazu beiträgt, Ihr Problem zu reduzieren, da 5 ^ 55 für den Fall mod 13 zu 5 ^ 3 wird, da 13 * 4 = 52. Wenn Sie unter dem Thema "Endliche Felder" nachsehen, finden Sie möglicherweise einige gute Ergebnisse zur Lösung dieses Problems.

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

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

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

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

}

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 sequentieller Multiplikationen auch lange dauern, sodass Sie mit quadratischen Werten multiplizieren können:

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

Der modulare Exponentiationsalgorithmus geht davon aus, dass:

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

Und so sieht der rekursive modulare Exponentiationsalgorithmus in Java folgendermaßen aus:

/**
* 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.

Geben Sie einfach eine weitere Implementierung von Jasons Antwort von C.

Nachdem ich mit meinen Klassenkameraden diskutiert habe, basierend auf Jasons Erklärung, mag ich die rekursive Version mehr, wenn Sie sich nicht sehr 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;
}