Schnelle Möglichkeit zum manuellen mod eine Zahl

Ich muss in der Lage sein, zu berechnen, (a^b) % c für sehr große Werte von a und b (einzeln schieben begrenzen und die Ursache überlauf-Fehler, wenn Sie versuchen zu berechnen, a^b). Für genügend kleine zahlen, über die Identität (a^b)%c = (a%c)^b%c funktioniert, aber wenn die c zu groß ist das nicht wirklich helfen. Ich schrieb eine Schleife zu tun, die mod-operation manuell, ein zu einer Zeit:

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 das dauert eine sehr lange Zeit. Gibt es irgendeine schnelle und einfache Möglichkeit, das zu tun diese operation ohne tatsächlich zu nehmen, um die macht von b UND ohne zeitaufwendiges Schleifen? Wenn alle Stricke reißen, kann ich einen bool-array zur Darstellung eines riesigen Daten-Typ und herausfinden, wie dies mit den bitweisen Operatoren, aber es muss einen besseren Weg geben.

  • Klingt wie ein Euler-problem... Wenn es ist, Sie sollte deutlich gemacht werden, dass die Frage, anstatt zu versuchen, zu betrügen...
  • Die Kenntnis der Palette von a, b und c, die uns helfen könnten.
  • Cheat?.........
  • Diese bool-array-Idee wird nicht funktionieren. Bool-arrays sind nicht bitvectors, und Sie werden nicht gespeichert gepackt. Plus, dann bist du nicht verlassen auf den direkten hardware-math.
  • Projekt Euler #188 ?
  • Ich weiß nicht, ob es wirklich Betrug. Das Lesen über das problem, das es aussieht, als würde er die Antwort kennt, er will einfach nur wissen, wie man es in angemessener Zeit-constraints in c#.
  • Ich war eigentlich nicht zu lösen versucht, dass problem ist, ich brauche dieses Algorithmus für ein Verschlüsselungs-Programm, das ich Schreibe.
  • Ist dies für Ihre eigenen Erbauung, oder wollen Sie tatsächlich sich auf Ihre Algorithmus zu schützen, Ihre Kunden von übeltätern? Wenn der ehemalige, gehen Sie. Wenn letzteres, ich bitte Sie eindringlich, noch einmal zu überdenken.

InformationsquelleAutor | 2009-06-12
Schreibe einen Kommentar