Wie berechnet man den Modul großer Zahlen?

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)

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

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

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.

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

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

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