Zitat:
wo ist nun der genaue unterschied zwischen MOD und REM ?
MOD und REM unterscheiden sich darin wie das Vorzeichen des Ergebnisses ausgerechnet wird. Während REM = Remainder = Rest sich exakt so verhält wie wir es in der Schule gelernt haben, sprich Vorzeichen des Restes ist das Vorzeichen des Dividenden, wird bei MOD = Modular = das Vorzeichen aus dem Divisor ermittelt. Somit wird MOD auch sehr häufig nicht als mathematische Operation einer Division gesehen sondern als Kongruenzklassen Operator. D.h. MOD stellt in modularen Ringen die Kongruenz einer Restklasse sicher.
Zitat:
// modular squaring, A = A^2 mod 2^k, A = B^2 mod 2^k
procedure NSqrMod2k(var A: IInteger; const B: IInteger; K: Cardinal); overload;
was ist MOD2K?
wie muß man sich das vorstellen?
Der Remark sagt schon alles:
-> A = A^2 mod 2^k
Vorstellen kannst du es dir so:
-> x = 1234^2 mod 2^16 == 1234^2 mod $10000;
Solche Operationen sind enorm schnelle Divisionen auf Binärrechnern, logisch da eine Division zu 2^k = ein Exponent zu Basis 2, eben nichts anders wie eine UND Verknüpfung mit 2^k -1 darstellen. Nach A^2 wird also das Resultat auf k Bits abgeschnitten, da man ja mit einer Binärzahl modular dividiert die aus k-1 ein Einsen besteht. Zb. A mod 2^1024 == A and (2^k-1) == A and 0b111111111.111111. Der Divisor besteht also als Binärzahl aus k-1 Einsen. Technisch gesehen bedeutet dies aber nur das man jeden Dividenden einfach auch k Bits in der Größe anbschneidet. Intern im DECMath wird zu jedem IInteger die Größe der verwendeten 32 Bit Werte verwaltet. D.h. die IInteger bestehen aus einem Linearen Speicherbereich der die Zahl enthält und einem Zähler wieviele Cardinal == 32Bit Werte man benötigt um diese große Zahl zu speichern. Eine MOD 2^k Operation wird also im Grunde immer nur diesen Zähler verkleinern und maximal den höchsten 32 Bit Wert im Speicher AND verknüpfen. Der Performancetechnisch Aufwand der MOD 2^k Operationen beschränkt sich demnach immer nur auf eine 32Bit breite AND Operation, auf bei Zahlen und einem k von vielen tausenden Bits.
Will man Zb. 1 Million Nachkommastellen von Pi berechnen, benötigt davon aber nur die letzten 8 Hexadezimalen Ziffern, dann kann man das so machen das nach jeder Operation mit MOD 2^32 -> k = 32, modular verkürzt. Du kannst dir nun vorstellen das es ein gewaltiger Unterschied in der Performance ist ob man nur mit 32 Bit großen Werten oder mit 125.000 Bit großen Zahlen rechnet.
Man berechnet also nur Teilziffern der gesuchten Zahl und kann so effizient und sehr schnell seine Ergebnisse mit zB. Testdaten aus dem Internet vergleichen. Man erhöht nun k, ausgehend von 32 so das nach jeder richtigen Teilberechnung die nächste Berechnung mit k * 2 durchführt. So kann man sehr effizient Überprüfungen durchführen.
In NCombi.pas findest du viele solcher Verfahren die intern modulare Divisionen mit 2^k durchführen können. Zb. möchtest du 2*3*5*7*13.....65537 mod 2^32 berechnen, also das Primorial = Produkt aller Primzahlen zwischen 0 bis 65538 modulo 2^32, also nur die letzten 32 Bits = 8 Hexadezimalen Ziffern. Du benutzt dazu NPrimorial(A, 0, 65538, NInt("HEX:100000000")); d.h. der Modulare Divisor ist 2^32. Intern ruft nun NPrimorial nach jedem Rechenschritt NMod(x, 2^32) auf, und NMod() wiederum kann überprüfen ob der Divisor eine echte Potenz von 2 ist, d.h. NMod() berechnet wenn möglich das k == 32. Falls das zutrifft wird nicht mehr mit einer langsammen Standarddivision gerechnet sondern eben einfach mit Beschneidung des Resultates auf k == 32 Bits.
Solche Feinheiten werden erst dann relevant wenn man Zb. bestehende Algorithmen in/aus anderen Libraries nach/von DECMath umsetzt, und sich dann bei Berechnungen mit mod 2^k Zahlen wundert warum DECmath um so vieles schneller als andere Libraries ist. Dies liegt eben daran das DECMath intern so weit dies effizient möglich ist bei vielen Operationen das schnellste Verfahren zur Lösung der Aufgabe ermittelt. Gerade die häufigsten Operationen wie die modulare Exponentation, modulare Multiplikation, modulare Quadrierung usw. profitieren dann davon wenn man mit mod 2^k berechnet.
Zitat:
was ist "montgomery domain" ???
Montgomery, war ein sehr trickreicher Mathematiker. Er hat einige wirklich interessante Algorithmen entdeckt die verschiedene mathematische Operationen, gerade im Langzahlbereich, sehr beschleunigen. Und da ist eben der Montgomery Trick zur Modularen Division hervorzuheben. Montgomery's Trick basiert im Grunde darauf das man alle Berechnungen zu einem ganz bestimmten Divisor in dessen Montgomery Darstellung durchführt. Dies vereinfacht und beschleunigt dann die Restebildung der nachfolgenden wiederholten modularen Montgomery Divisionen ernorm. D.h. mit Hilfe des Montgomery Tricks kann man zB. die Modulare Exponentation -> A = A^E mod M, beschleunigen. Allerdings darf M bestimmte Zahlenbereiche nicht überschreiten. In DECMath wird M < 2^8192 sein, damit intern dann Montgomerys Trick angewendet wird. Bei größeren Zahlen sind die in DECMath integrierten Divisionen wieder schneller als der Montgomery Trick.
Für eine genaue Beschreibung solltest du besser im Internet danach suchen. Interessant an den meisten Montgomery Tricks ist aber der Fakt das diese Tricks zu einer Zeit entdeckt wurden als man mit Langzahlen wie sie heute durch Computer möglich gemacht werden, damals noch garnicht gab. D.h. Montgomery hat viele Tricks gefunden die zu seiner Zeit keinerlei reale Bedeutungen hatten. Erst viel viel später besann man sich auf diese schon bekannten Tricks zurück um damit verschiedenen Computerberechnungen zu beschleunigen. Fazit: Montgomery hat Wissen entdeckt nur weil es entdeckbar war, und nicht weil man es zur Lösung eines konkreten Zieles nötig war
Oder anders ausgedrückt: man entdeckt irgendwas und erfindet erst danach eine konkrete Anwendung dafür.
Gruß Hagen