Schnelle Möglichkeit, eine Zahl manuell zu ändern

Question

Ich muss (a^b)% c für sehr große Werte von a und b berechnen können (die einzeln die Grenze drücken und Überlauffehler verursachen, wenn Sie versuchen, ein^zu berechnen b). Für klein genug Zahlen funktioniert die Verwendung der Identität (a^b)% c = (a% c)^b% c, aber wenn c zu groß ist, hilft das nicht wirklich. Ich schrieb eine Schleife manuell die Mod Operation zu tun, der eine ein zu einem Zeitpunkt:

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    { 
     long answer = 1; 
     for (int x = 0; x < num_exponent; x++) 
     { 
      answer = (answer * num_base) % mod; 
     } 
     return answer; 
    } 

aber eine sehr lange Zeit in Anspruch nimmt. Gibt es einen einfachen und schnellen Weg, um diese Operation auszuführen, ohne tatsächlich die Macht von b UND ohne zeitaufwendige Schleifen zu nehmen? Wenn alles andere fehlschlägt, kann ich ein Bool-Array erstellen, um einen riesigen Datentyp darzustellen, und herausfinden, wie man das mit bitweisen Operatoren macht, aber es muss einen besseren Weg geben.

Answer 1

Kurz von Ihrem eigenen fast modular exponentiation, die einfachste Idee, die ich finden kann, ist die Verwendung der F # BigInt Typ: , die Operationen mit beliebig großen Maßstab unterstützt - einschließlich Potenzierung und modulare Arithmetik.

Es ist ein integrierter Typ, der mit der nächsten Version Teil des vollständigen .NET-Frameworks sein wird. Sie müssen F # nicht verwenden, um BitInt zu verwenden - Sie können es direkt in C# verwenden.

Answer 2

Ich würde empfehlen, über die Dezimaldokumentation zu überprüfen und zu sehen, ob es Ihren Anforderungen entspricht, da es ein eingebauter Typ ist und den Mod-Operator verwenden kann. Wenn nicht, dann brauchst du eine beliebige Präzisions-Bibliothek wie Java's Bignum.

Answer 3

Können Sie a, b oder c faktorisieren? Hat C eine bekannte Reichweite?

Dies sind 32 Bit Ganzzahlen! Gehen Sie prüfen dieses site

Zum Beispiel hier, wie Sie die Mod von n% d, wo d 1 >> s (1,2,4,8, ...)

int n = 137;  // numerator 
    int d = 32;  // denom d will be one of: 1, 2, 4, 8, 16, 32, ... 
    int m;   // m will be n % d 
    m = n & (d - 1); 

Es gibt Code für n% d wobei d 1 ist >> s - 1 (1, 3, 7, 15, 31, ...)

Dies wird nur wirklich helfen, wenn c ist klein, obwohl, wie Sie sagten.

Answer 4

Fast Modular Exponentiation (ich glaube, das ist, wie es heißt) könnte funktionieren.

 
Given a, b, c and a^b (mod c): 

1. Write b as a sum of powers of 2. (If b=72, this is 2^6 + 2^3) 
2. Do: 
    (1) a^2 (mod c) = a* 
    (2) (a*)^2 (mod c) = a* 
    (3) (a*)^2 (mod c) = a* 
    ... 
    (n) (a*)^2 (mod c) = a* 

3. Using the a* from above, multiply the a* for the powers of 2 you identified. For example: 
    b = 72, use a* at 3 and a* at 6. 
    a*(3) x a*(6) (mod c) 

4. Do the previous step one multiplication at a time and at the end, you'll have a^b % c. 

Nun, wie Sie das mit Datentypen tun werden, weiß ich nicht. Solange Ihr Datentyp c^2 unterstützt, denke ich, dass es Ihnen gut geht.

Wenn Sie Strings verwenden, erstellen Sie einfach String-Versionen von addieren, subtrahieren und multiplizieren (nicht zu schwer). Diese Methode sollte schnell genug sein. (und Sie können Schritt 1 mit einem Mod c beginnen, so dass a nie größer als c ist).

EDIT: Oh schau, eine Wiki-Seite auf Modular Exponentiation.

Answer 5

Sie konnten dieses versuchen:

C#: Handeln mit einem Modul (mod) Betrieb auf eine sehr große Zahl (> Int64.MaxValue)
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus-mod-operation-on-a-very-large-number-int64maxvalue/

Answer 6

Sie können versuchen, 'a' Factoring in ausreichend kleine Zahlen.

wenn die Faktoren von 'A' 'x', 'y' und 'Z', dann

a^b = (x^b) (y^b) (z^B).

Dann können Sie Ihre Identität verwenden: (a^b)% c = (a% c)^b% c

Answer 7

Es scheint mir, wie es irgendeine Art von Beziehung zwischen Macht und mod. Macht ist nur wiederholte Multiplikation und Mod ist mit Division verbunden. Wir wissen, dass Multiplikation und Division Inversen sind, also würde ich annehmen, dass zwischen Power und Mod ein Zusammenhang besteht.

Zum Beispiel nehmen Kräfte von 5:

5 % 4 = 1 
25 % 4 = 1 
125 % 4 = 1 
625 % 4 = 1 
... 

Das Muster ist klar, dass 5%^b 4 = 1 für alle Werte von b.

Es ist weniger klar in dieser Situation:

5 % 3 = 2 
25 % 3 = 1 
125 % 3 = 2 
625 % 3 = 1 
3125 % 3 = 2 
15625 % 3 = 1 
78125 % 3 = 2 
... 

Aber es ist immer noch ein Muster.

Wenn Sie die Mathematik hinter den Mustern erarbeiten könnten, wäre ich nicht überrascht, wenn Sie den Wert der Mod herausfinden könnten, ohne die eigentliche Macht zu tun.

Answer 8

Python hat pow (a, b, c), das (a ** b)% c (nur schneller) zurückgibt, also muss es einen cleveren Weg dafür geben. Vielleicht machen sie nur die Identität, die du erwähnt hast.

Answer 9

Sieht aus wie Hausaufgaben in der Kryptographie.

Hinweis: Auschecken Fermat's little theorem.

Answer 10

ich Sie erraten suchen: http://en.wikipedia.org/wiki/Montgomery_reduction oder die einfachere Art und Weise basierend auf der modularen Potenzierung (aus Wikipedia)

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) { 

    Bignum result = 1; 

    while (exponent > 0) { 
     if ((exponent & 1) == 1) { 
      // multiply in this bit's contribution while using modulus to keep result small 
      result = (result * base) % modulus; 
     } 
     // move to the next bit of the exponent, square (and mod) the base accordingly 
     exponent >>= 1; 
     base = (base * base) % modulus; 
    } 

    return result; 
} 

Answer 11

Hier ist ein Beispiel von Fast modularen Potenzierung (in einer der früheren Antworten vorgeschlagen) in Java . Sollte nicht allzu schwer sein, das zu C#

zu konvertieren

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html

und die Quelle ...

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.java