Ich muss a*a mod n berechnen, aber a ist ziemlich groß, was zu einem Überlauf führt, wenn ich es quadriere. Doing ((a%n)*(a%n))%n funktioniert nicht, weil (n-1) 2 überlaufen kann. Das ist in C ++ und ich benutze Int 64's.
edit: Beispiel ein Wert = 821037907258 und n = 800000000000, der überläuft, wenn Sie ihn quadrieren.
Ich benutze DevCPP und ich habe bereits versucht, Big-Integer-Bibliotheken ohne Erfolg zu bekommen.
edit 2: Nein, zu diesen Zahlen gibt es kein Muster.
Wenn Sie keine Big-Integer-Bibliothek verwenden können und Sie kein natives uint128_t (oder ähnliches) haben, müssen Sie dies manuell tun.
Eine Option besteht darin, a als Summe zweier 32-Bit-Größen auszudrücken, dh a = 2 32 b + < em> c , wobei b die 32 msbs enthält und c die 32 lsbs enthält. Quadrieren ist dann ein Satz von vier Kreuzmultiplikationen; Jedes Ergebnis passt garantiert in einen 64-Bit-Typ. Sie führen dann die Modulo-Operation durch, indem Sie die einzelnen Terme neu kombinieren (unter sorgfältiger Berücksichtigung der Verschiebungen, die erforderlich sind, um alles neu auszurichten).
Ich weiß, dass Sie das nicht mehr brauchen, und es gibt eine alternative Lösung, aber ich möchte eine alternative Methode hinzufügen, um es zu implementieren. Es bietet zwei verschiedene Techniken: den Algorithmus zum Verdoppeln und Hinzufügen und die Methode zum Behandeln von mod(a + b, n) mit Überlauferkennung.
Der doppelte und addierende Algorithmus wird normalerweise in Feldern verwendet, in denen die Multiplikation nicht möglich oder zu teuer ist, um direkt zu berechnen (wie elliptische Kurven), aber wir könnten ihn in unserer Situation so handhaben, dass er Überläufe behandelt.
Der folgende Code ist wahrscheinlich langsamer als die akzeptierte Lösung (selbst wenn Sie ihn optimieren), aber wenn die Geschwindigkeit nicht kritisch ist, können Sie es aus Gründen der Übersichtlichkeit bevorzugen.
%Vor% Hier ist eine Doppel-und-hinzufügen-Implementierung einer Multiplikation a * b % m , ohne Überläufe, unabhängig von der Größe von a, b und m.
(Beachten Sie, dass die Zeilen res -= m und temp_b -= m auf einen 64-Bit-Integer-Überlauf ohne Vorzeichen angewiesen sind, um die erwarteten Ergebnisse zu erzielen. Dies sollte in Ordnung sein, da vorzeichenloser Integer-Überlauf in C und C ++ wohldefiniert ist Aus diesem Grund ist es wichtig , unsignierte Integertypen zu verwenden.
Dies ist meine Änderung von eine andere Antwort auf eine ähnliche Frage .
Tags und Links c++