Modulo -Algorithmus: übersetzng von pseudocode

[Sequitar]

Auf der suche nach schnelleren Modulo Berechnungen bin ich auf Folgendes gestoßen:
"Computing Mod Without Mod" (Will, Mark A & Ko,, Ryan)
Die Autoren schlagen beigefügten pseudo-code vor (section 2.4,algorithmus 3), den ich versucht habe in delphi zu übersetzen, leider nur mäßig erfolgreich, wie meine tests belegen

wäre mal einer so nett und könnte das mal checken?

Anbei mein code,
! ich habe für die "einfachen" mathe optionen eine bestehende library, die funktionalität der eingesetzten teile wurde nach bestem wissen erfolgreich getestet

(hierzu lade ich noch ein basis package und die entsprechende dll hoch)

Ansonsten bin ich natürlich auch dankbar für Vorschläge bzgl integer division / modulo verbesserungen

Vielen Dank

[Michael II]

Wieso baust du Algo3 aus 2.4 nach? Die Autoren schlagen doch Algo4 aus 3.1 vor. (This [Algo3] is the main reduction, but some further can be required hence the last two
while loops.)

Baust du den Algo für den Schulunterricht nach? Oder willst du die vorgeschlagene mod Funktion in Delphi Programmen verwenden? Wenn Letzteres: Der Algo ist für den Einbau in Prozessoren gedacht und nicht für die Schicht in welcher Delphi werkelt.

Welchen Teil von Algo3 aus 2.4 kannst du nicht umsetzen/verstehst du nicht?

[Andreas13]

Hallo Sequitar,
wenn Du den Modulo-Algorithmus nicht als „programmiertechnische Herausforderung“ suchst, sondern in Deinen Delphi-Programmen z. B. für kryptographische Zwecke etc. eine Modulo-Funktion mit hoher Genauigkeit (z. B. 2048 Bits und meeeeeeehr) brauchst, dann könntest Du die Multipräzisions-Bibliotheken von unserem leider viel zu früh verstorbenen Gammatester (Wolfgang Ehrhardt) benutzen. Zu finden sind sie auf dem Web-Archiv unter:
http://web.archive.org/web/*/wolfgang-ehrhardt.de
Gruß, Andreas

[himitsu]

Oder mal ins DEC (Delphi Encryption Compendium) schauen, das ist ja sauschnell, also enthält es auch ein schnelles Modulo. :stupid:

Und natürlich auch nochmal im DECMath.

[Sequitar]

Hallo und vielen Dank für eure tips (! insb, wenn der vorgeschlagene Algorithmus nur in prozessoren werkeln soll, ist das definitiv ein falscher ansatz von mir)

Derzeit würde ich das dingen für größenordnungen um die 500bt (aufgrund der aktuellen hardware nicht die standardmäßigen 2048bt) anwenden wollen, insb für hash checks, angedacht war ursprunglich auch mal ein key-austausch, aber das projekt hab ich auf eis gelegt, und werde da wohl auf eine standard lib umsteigen,falls mein aktueller prozessor das zulässt (i5-u mobile version)

ich glaub' von Dir, himitsu, hatte ich vor langer, langer zeit mal eine math unit erhalten, auf deren basis ich seitdem immer mal wieder erweitert hab'. Merci dafür noch mal, hat mir seinerzeit gute Dienste erwiesen und ist auch gut nachvollziehbar. Derzeit stelle ich das für die - noch limitierten Anwendungsbereiche (s.o, und derzeit im rahmen diverser Präsentationsszwecke für schüler, @Michael II) auf byte-arrays um, von daher war der gedanke, bei der division vielleicht nebenbei etwas effizienteres einzubauen

Habt Ihr evtl passende alternativ-algortithmen (also jetzt nur für die division) in peto? Als referenz würde wohl reichen, nachbauen würde ich dann ggf selber.

Merci
schönen abend!

[himitsu]

Wobei meine paar MathLibs und der Taschenrechner mehr Proof-of-Concept waren.
Schauen was möglich ist, von den Schnittstellen her, aber nicht wirklich auf Effizienz ausgelegt. :oops:

DECMath war/ist praktisch eine der schnellsten Libs im kostenlosen Bereich (Ein-Mann-Projekt).
Problem dort war, dass der Quellcode nicht öffentlich ist/war und demnach es mit neuen Delphi-Versionen Probleme gibt, so lange nicht jemand dafür das Compilat (DCU's) bereitstellt.
Aber es gibt mehrere BigMathLibs, wovon welche auch auf Cryptographie spezialisiert sind.

[TurboMagic]

Hagen, der ursprüngliche Entwickler der DEC hat von dem Teil leider nie den Quellcode rausgegeben. Die DCUs in DEC 5.2 sind für D7 also steinalt. Habe es daher im 6.0 Entwicklungszweig rausgenommen.

Wie sieht die Lizenzsituation bei W. Regards Code aus? Könnte das jemand problemfrei bei GitHub oder so einstellen?

[himitsu]

Regards?


Part I gibt es als Pascal, glaub ich, aber Part II ........
Joar, dann wäre für DEC-Math wohl die einzige Möglichkeit das mit Delphi 7 / C++Builder 7 zu versuchen in eine .OBJ zu kompilieren und das dann wie ZLib/Jpeg/PNG/RegEx ins Delphi zu ziehen.
(ich glaub hab seit 4 Jahren nichts mehr von ihm gehört)

[TurboMagic]

Verflixte Autokorrektur auf'm Tablet.
Meinte W. Erhardt.

Ich fänd's gut wenn man das in irgend ein Open SOurce Repository
(oder mehrere falls es unterschiedliche Themen sind) überführen könnte.
Würde die Sichtbarkeit erhöhen, die Nützlichkeit steigern und evtl.
käme dann auch noch die eine oder andere kleine Verbesserung dazu.

[himitsu]

Er ist ja letzten Jahres verstorben.
https://www.delphipraxis.net/200202-...mmatester.html

Ich denke mal es wäre OK, wenn man es dort hin transferiert, dazumal die Webseite ja von 'nem Spammer/Grabber übernommen und misshandelt wurde.

Zitat:

Wolfgang hat seinen Code mit einer sehr freigiebigen Lizenz ausgestattet, so dass niemand Probleme haben sollte, den Code in seinen Projekten zu verwenden.

So als Idee, vielleicht könnte man es ins DEC integrieren, bzw. daneben legen.
Hagen Reddmann wird wohl noch leben, aber er hat seine Verschlüsselungs-Bibliothek abgegeben.

[TurboMagic]

Hallo,

nach Außen hin ist zwar noch das Forenmitglied Assertor "Herr der DEC". An den ging
das damals von Hagen über, da Assertor aber stark ausgelasteter Freelancer ist und derzeit
auch leider nichts mehr wirklich mit Delphi macht, bin ich der Hauptentwickler.
Eigentlich warte ich auch drauf, dass mir Assertor das ganze Projekt richtig transferiert,
was er selber sogar will, aber krieg mal 'ne Kommunikation mit dem zustande...

Kurz und gut: momentan ist der Plan DEC 6.0 fertig zu stellen. Da sind dann keine wirklich
neuen Algorithmen drin (ok, neueste Variante vom Whirlpool Hash wurde nachgerüstet und
als erkannt wurde, dass Hagen's KDF2 eigentlich der KDF1 ist wurden es umbenannt und
KDF2 und KDF3 wurden nachgerüstet). Es gibt aber genug neue Dinge in 6.0 (siehe auch Doku):

1. Doku erstellt (darfst die ruhig mal probelesen, ist meiner Meinung nach weitestgehend fertig)
2. XMLDOC hinzugefügt (bis auf wenige Stellen wo ich den Code noch nicht verstanden habe)
3. Über einen Compilerschalter Üurepascal Umsetzung aktivierbar, dadurch Crossplattform fähig
4. Umbau des kryptischen Testprogramms auf DUnit tests
5. Ergänzung weiterer Tests auch für bisher ungetestete Bereiche
6. Erstellung einiger Demo Programme, 2 davon sind auch in Google Play (DEC Hash Demo und DEC Cipher Demo)
7. Klassenregistrierungsmechanismus überarbeitet
8. IsValid für die restlichen TFormatXXX Klassen umgesetzt

Ich glaube das ist doch schon mal einiges.
Der Plan für nach 6.0 sieht aus neuere und fehlende Algorithmen umzusetzen, eine Quelle
dafür dürfte sicherlich auch W. Erhardt's Bibliothek sein. Ich denke da z.B. an SHA224 und SHA3.
Das wären jedenfalls die nächsten Kandidaten und auch Passwort Hashes, die fehlen noch komplett.
Da hatte er glaube ich zumindest BCrypt umgesetzt. Auch weitere Kandidaten des SHA3 Wettbewerbs
sind denkbar. Das eine oder ander müsste man halt aus anderen Sprachen übersetzen.

Weitere Mitstreiter (außer mir hat an der 6.0 dankenswerterweise auch noch Norman etwas mitgearbeitet,
der anders als ich scheinbar auch mehr Zeit hat) gerne willkommen! Manchmal wäre auch schon das
Ergänzen/Schreiben von Unit-Tests eine Hilfe!

[Michael II]

Hallo Sequitar

falls ich deinen Code richtig lese (kompilieren kann ich ihn nicht und ich habe gerade weder Zeit noch ...), dann berechnest du den Vektor T bei jedem Aufruf von Tmod.quickmod() neu.

In den beiden Fällen 1. "X < Y" und 2. "bitlength(X) = k" benötigst du T nicht => nicht berechnen.

Ziel des Algos ist es, teure Divisionen durch "billige" Additionen zu ersetzen. Wenn du zur Ermittlung des Funktionswerts von Tmod.quickmod(X,Y) bitlength(Y) Mal Math.Modulo(Result, Y) aufrufst, wirkst du diesem Ziel (je nach Implementation von Math.Modulo) u.U. entgegen. [ Wenn du Tmod.quickmod(X,Y):=Math.Modulo(X, Y) setzen würdest, hättest du ja nur einen einzigen Math.Modulo() Aufruf und gleich noch das Resultat von Tmod.quickmod() [wobei man für eine genaue Bewertung die Bit-Längen von x und y und die Implementierung von Math.Modulo kennen muss].
Du müsstest prüfen, wie schnell deine Kombi aus Bitshift und Math.Modulo die bitlength(Y) Werte von T berechnet. (Wenn Y k:=bitlength(Y) Bit breit ist, blähst du mit deiner Bitshift Funktion Y auf bis zu 2*k-1 Bit Werte auf - muss das sein (?)) => evt. T anders berechnen.

Wenn du Tmod.quickmod(X,Y) für mehrere (x,y) berechnest und der Wert y dabei gleich bleibt, dann lohnt es sich (je nach Umgebung) die Werte von T abzuspeichern (T ist ja nur abgängig von y). Dies wird im Paper breit diskutiert. Der Algo ist genau in diesem Fall (mehrere quickmod() Berechnungen, y immer gleich) besonders effektiv (nur noch Additionen). Diesen Teil sehe ich in deinem Code noch nicht umgesetzt.

[KodeZwerg]

Zitat:

Zitat von himitsu (Beitrag 1472253)

aber Part II ........

Ich glaube ich habe noch von DEC 5.1 die Part II Sourcen, wenn die benötigt werden kann ich mal suchen.

[himitsu]

DEC war glaub ich komplett öffentlich, aber bei DECMath fehlte was.

[KodeZwerg]

Hier ist das von meinem Share. Kann gerade nicht prüfen ob komplett oder was fehlt. Das entstammt dem DEC 5.1c Archiv.

[TurboMagic]

Hallo,

danke mal für's Suchen!
Nur: das ist im Prinzip genau das, was auch bei DEC 5.1c bzw. 5.2
auf der "offiziellen" DEC Release Seite ist:
https://github.com/winkelsdorf/Delph...ndium/releases
Und das sind leider bloß Interfaces.
Also keine Notwendigkeit das zu Veröffentlichen.

Grüße
TurboMagic