ich eine bignum Bibliothek entwickle: http://pastebin.com/nFgF3zjW ich den Miller-Rabin-Algorithmus implementiert (isprime()), aber es ist extrem langsam, im Vergleich zu für BN_is_prime_fasttest das Beispiel OpenSSL.Bignum Bibliothek, langsam prime Generator
Ich versuchte Profiling und die Funktionen, die am meisten ausgeführt werden, sind bn_shr_atomic und bn_cmp. Irgendeine Idee, wie ich das schneller machen kann?
Die GNU Multiple Precision Arithmetic Library implementiert Miller-Rabin. Es ist Dokumentation befindet sich hier:
http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions
Ich würde vorschlagen, deren Umsetzung für Zeiger Prüfung auf Ihrer Berechnung zu beschleunigen. Arithmetik mit willkürlicher Genauigkeit ist jedoch inhärent langsamer als die Arbeit mit Zahlen, die in Register passen.
Edit:
Es gibt auch einen Kompromiss zwischen dem verwendeten Algorithmus und der Qualität der resultierenden Wahrscheinlichkeit. Das heißt, ich bin mir nicht sicher, welchen Test OpenSSL verwendet.
Sieht aus wie OpenSSL 'BN_is_prime_fasttest_ex()' verwendet eine sorgfältig optimierte Miller-Rabin. –
Große Vermutung: Wenn Sie wirklich Ihre eigene Bibliothek verwenden möchten, würde ich zuerst den Divisionsalgorithmus durch die lange Division ersetzen.
Um meine Vermutung zu bestätigen: Sie haben cmp und shr in der inneren Schleife Ihres Divison, sind diese Anrufe der Hauptverursacher in Ihrem Profil oder kommen sie von woanders? Im Allgemeinen sollten Sie sich bei der Profilerstellung zunächst auf Funktionen auf höherer Ebene konzentrieren, die einen großen Beitrag leisten. Das Ändern von Algorithmen ist in der Regel nützlicher als das Tunen von Funktionen auf niedriger Ebene.
Verwenden Sie einen schnelleren Test als Miller-Rabin? –