Zitat:
Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig?
Nicht für die Exponentation ansich. Im obigen Link zum Fastcode Projekt findest du verschiedene Verfahren. In meiner
Unit wurde diese Exponentation einerseits mit normalen Division, also in der Normal Domain, und andererseits in der Montgomery Domain implementiert.
Man kann also die modulare Exponentation durchaus mit normalen Zahlen umsetzen und benötigt dazu nicht zwangsweise den Montgomery Trick. Der Trick ansich ändert nur die Zahlendarstellung auf eine Art & Weise das die wiederholt nötigen modularen Redukationen nach den modularen Multiplikationen eben nicht per Divisionen sondern mit Multiplkationen durchgeführt werden können. Da nun Multiplikationen auf Intel CPU's weitaus schneller sind ist diese Vorgehensweise sinnvoll.
Essentiell benutze ich zb. den Montgomery Trick in meiner Large Integer Library mit Integern bis zu 2^4096. Alles was darüber ist ist dann mit der schnellen Karatsuba Division nach Burnikel&Ziegler wieder wesentlich Performanter.
Mein erster Source den ich vor ca. 10 Jahren schrieb nutzt eben nicht die Montgomery Domain. Erst vor 2 Jahren, in der FastCode Competition, habe ich meinen IsPrime() Algo. auf Montgomery umgesetellt. Dies wurde sozusagen nötig da meine Competior meinen ursprüglichen Code durch Detailverbesserungen immer schneller machten. Eine weitere Beschleinigung des Verfahrens war also nur noch möglich indem ich neben dem Montgomery Trick die Trial Division ins Rennen warf und später diese Trial Division mit den modularen Inversen + Multiplikationen ausbaute
Sogesehen: der obige Source konnte nur entstehen weil sich verschiedene Leute in der FastCode Competition gegenseitig motivierten.
Gruß Hagen