GNURZ - Arithmetik-Unit für große Zahlen

[Euklid]

GNURZ: Arithmetik zum Umgang mit (G)roßen (N)atürlichen (U)nd (R)ationalen (Z)ahlen

GNURZ stellt alle zum Umgang mit beliebig großen natürlichen und rationalen Zahlen notwendigen Grundoperationen bereit. Aufgrund einer übersichtlichen Struktur ist für die Verwendung der GNURZ keine lange Einarbeitungszeit notwendig. Die GNURZ ist OpenSource und ist zur GPL 2 und GPL 3 kompatibel.

Weitere Informationen, ein Demonstrations-Projekt, sowie eine Beschreibung aller Funktionen der GNURZ befindet sich auf der Projekthomepage:

http://forge.lazarusforum.de/projects/show/gnurz

[mschnell]

Gibt es nicht schon Tausende solcher Bibliotheken ?

-Michael

[Christian]

Ist doch egal, das ist was wo ich sagen muss wenn man aus interesse sowas bastelt ist mir das lieber als der 109998127276282874298347. Media Player.

[mschnell]

Im Detail:

Die meisten Arithmetik Pakete für große Interger Zahlen arbeiten mit arrays of 32 Bit Zahlen zur Darstellung der super-Integers. Dieses hier auch, ist natürlich auch OK, aber wenn man eine 64-Bit Prozessor hat ist die Arithmetik natürlich doppelt so schnell, wenn arrays of 64 Bit Zahlen verwendet werden.

Bruch-Arithmetik ist natürlich ein super-Spezial-Ding (auch dafür gibt es sicher irgendwelche Anwendungen (weil exakte Rechnung und nicht gerundet wie bei normaler Gleitpunkt-Arithmetik). Normale Gleitpunkt-Arithmetik (mit Exponent und Mantisse) arbeitet aber viel schneller und lässt sich auch auf langen Integers aufbauen.

-Michael

[Euklid]

Gibt es nicht schon Tausende solcher Bibliotheken ?

Ja, es gibt einige. Die meisten sind in C geschrieben, einige wenige in Pascal. Viele der in Pascal geschriebenen sind unfrei.

GNURZ ist ein aus Promathika hervorgehendes Projekt. Promathika wird zu einem Computer-Algebra-System ausgebaut und da ist die Unterstützung großer Zahlen natürlich Pflicht.

Die meisten Arithmetik Pakete für große Interger Zahlen arbeiten mit arrays of 32 Bit Zahlen zur Darstellung der super-Integers. Dieses hier auch, ist natürlich auch OK, aber wenn man eine 64-Bit Prozessor hat ist die Arithmetik natürlich doppelt so schnell, wenn arrays of 64 Bit Zahlen verwendet werden.

Es ist kein Problem, aus dem dword ein qword zu machen. Jedoch muss dazu FreePascal ein 16-Byte-Typ unterstützen, damit es mit der Multiplikation keine Probleme gibt. Denn dword mal dword gibt qword, doch welchen Typ für qword-Multiplikationen?
32-Bit-Prozessoren unterstützen 64-bit "nativ", indem zwei Register hintereinander geschaltet werden können. Ich nehme an, ähnliches geht mit 64-bit-Prozessoren hinsichtlich 128-bittigen Zahlen. Wenn diese bald durch FreePascal unterstützt werden sollten, werde ich die entsprechenden Anpassungen an GNURZ vornehmen.

Bruch-Arithmetik ist natürlich ein super-Spezial-Ding (auch dafür gibt es sicher irgendwelche Anwendungen (weil exakte Rechnung und nicht gerundet wie bei normaler Gleitpunkt-Arithmetik). Normale Gleitpunkt-Arithmetik (mit Exponent und Mantisse) arbeitet aber viel schneller und lässt sich auch auf langen Integers aufbauen.

Routinen zur Gleitpunkt-Arithmetik sind in Planung, haben aber eine niedrige Priorität, da Promathika intern exakt (d.h. mit Brüchen) rechnet und so von dieser Seite her keine Notwendigkeit besteht.

[mschnell]

Es ist kein Problem, aus dem dword ein qword zu machen. Jedoch muss dazu FreePascal ein 16-Byte-Typ unterstützen, damit es mit der Multiplikation keine Probleme gibt. Denn dword mal dword gibt qword, doch welchen Typ für qword-Multiplikationen?
32-Bit-Prozessoren unterstützen 64-bit "nativ", indem zwei Register hintereinander geschaltet werden können. Ich nehme an, ähnliches geht mit 64-bit-Prozessoren hinsichtlich 128-bittigen Zahlen. Wenn diese bald durch FreePascal unterstützt werden sollten, werde ich die entsprechenden Anpassungen an GNURZ vornehmen.

Hmmm. Und wie unterstützt der 32 Bit FP-Compiler 32Bit*32Bit => 64 Bit ? Oder verwendest Du Assembler an dieser Stelle ?

-Michael

[Euklid]

Hmmm. Und wie unterstützt der 32 Bit FP-Compiler 32Bit*32Bit => 64 Bit ? Oder verwendest Du Assembler an dieser Stelle ?

Für 32-Bit-Prozessoren gilt:
Wird der Prozessor-Befehl "MUL" auf ein dWord in Verbindung mit dem EAX-Register (beide 32 Bit) angewandt, so wird das 64-Bit-Ergebnis in den beiden Registern EDX:EAX abgelegt. Hier werden also schlicht zwei 32-Bit-Register belegt, was einer 64-Bit-Zahl entspricht.

Ich habe leider nur eine 32-Bit-Assembler-Referenz. Ob eine ähnliche Bündelung bei 64-Bit-Rechnern möglich ist, d.h. die Belegung zweier 64-Bit-Register zur Repräsentation einer 128-Bit-Zahl gibt, kann ich nicht sagen. Ich vermute es aber. Sollte es so sein, müsste ich grundlegende Operationen in Assembler schreiben, um eine große natürliche Zahl vom GNZTyp durch ein qword-Array für 64-Bit-Rechner darzustellen, da FreePascal keinen 128 bit großen ganzzahligen Datentyp unterstützt.

[Euklid]

Hallo Leute,

die GNURZ-Arithmetik-Unit hat heute auf Anregung von EugenE einige Erweiterungen erfahren, die insbesondere für die Kryptographie interessant sein dürften:

Code: Alles auswählen

function GNZMillerRabin(zahl:GNZTyp; it:word):boolean;

Ein schneller Primzahltest. it=Anzahl der Iterationen. Mit jeder zusätzlichen Iteration, viertelt sich die Wahrscheinlichkeit, dass eine Zahl den Test besteht, die keine Primzahl ist. D.h. Die Wahrscheinlichkeit, dass zahl keine Primzahl ist, ist mit it=25 nur etwa 0,0000000000000001 groß. Empfohlen wird also it=25.

Code: Alles auswählen

function GNZMRPrimdanach(zahl:GNZTyp; it:word):GNZTyp;

Man gibt eine beliebige Zahl ein, und die Funktion berechnet die nächste Primzahl, die größer ist als die eingegebene Zahl. Empfohlen wird it=25.

Code: Alles auswählen

function GNZPotenzMod(Basis,Exponent,Modulo:GNZTyp):GNZTyp;

Berechnet Basis^Exponent mod Modulo sehr effizient.


Ein paar Bemerkungen zur Kryptographie mittels RSA-Algorithmus:
Der RSA kann nur geknackt werden, wenn es gelingt, eine Zahl, die Produkt zweier Primzahlen ist, zu faktorisieren (d.h. in die beiden Faktoren zu zerlegen).
Der derzeitige Rekord im Faktorisieren solcher Zahlen liegt bei dem Produkt zweier 100-stelliger Primzahlen, d.h. bei einem 10000-stelligen Produkt. 100-stelligen Primzahlen lassen sich mit obiger Routine GNZMRPrimdanach in etwa einer Sekunde finden. Man kann sichergehen, dass das Produkt dieser Zahlen nur von Supercomputern faktorisiert werden kann. Die Berechnung von 200-stelligen Primzahlen zur Faktorisierung machen eine Verschlüsselung also mit derzeitiger Technik unknackbar. Wer Zeit mit sich bringen möchte, kann beliebig große Primzahlen mit der Funktion berechnen - die Zeitdauer zur Berechnung steigt aber sehr schnell mit der Lange der gewünschten Primzahlen an.

Viele Grüße, Euklid

[mschnell]

Klasse !!!

Hast Du inzwischen was über einen 64Bit * 64 Bit = 128 Bit Assembler-Befehl gefunden ?

P.S.: FPC kann doch operator overloading. Wäre das nicht praktisch ?

Gruß, Michael

[EugenE]

daran habe ich auch schon gedacht, ich denke ich könnte das machen gnurz_utils.pas ^^ fange sofort , werde es dann in den nächsten Tagen posten^^

[mschnell]

Ich hab' 'mal nach den Assembler-befehlen für 64*64 Multiplikation gesucht:

http://www.cs.cmu.edu/~fp/courses/15213 ... andout.pdf:

Figure 5 show instructions used to generate the full 128-bit product of two 64-bit words, as well as ones to
support 64-bit division. They are similar to their 32-bit counterparts (CS:APP Figure 3.9). Several of these
instructions view the combination of registers %rdx and %rax as forming a 128-bit oct word. For example,
the imulq and mulq instructions store the result of multiplying two 64-bit values—the first as given by
the source operand, and the second from register %rax.

-Michael

[Euklid]

Hallo,

Die GNURZ Arithmetik-Unit beinhaltet in der Version 0.99.3 nun auch einen Zufallsgenerator:

Code: Alles auswählen

function GNZZufall(Obergrenze:GNZTyp):GNZTyp;

Diese Funktion gibt eine große natürliche Zufallszahl zurück, die kleiner als Obergrenze ist.

EUGENE: Habe ein vorzeitiges Weihnachtsgeschenk an dich :
Werde im laufe der kommenden Tage einen neuen Variablentyp einführen, den GGZTyp. Er wird negative Zahlen unterstützen.
Alle Funktionen werden analog mit dem GGZTyp funktionieren, nur einfacher, da sie mit negativen Zahlen umgehen können werden. Ev. Wird es auch bald negative rationale Zahlen geben, dazu werde ich den GRaZTyp umdefinieren.

P.S.: FPC kann doch operator overloading. Wäre das nicht praktisch ?

Mit der Einführung von 64bit-Operatoren ließe sich die Berechnungsgeschwindigkeit für sehr große Zahlen fast verdoppeln. Wen EugenE das machen möchte, wäre daher eine von mir sehr willkommene Optimierung.

Ein paar Informationen: Die Multiplikation und Division tausendstelliger Zahlen ist mit GNURZ in wenigen Millisekunden möglich. Addition und Subtraktion gehen sowieso noch schneller. Für die Berechnung von unknackbaren öffentlichen Schlüsseln benötigt man Sekunden bis wenige Minuten, je nachdem wie sicher der Schlüssel sein soll. Obwohl die GNURZ mit speicherbegrenzend großen Zahlen umgehen kann, werden in der Praxis aber kaum größere als tausendstellige Zahlen benötigt.

Aber dennoch möchte ich nicht verschweigen, dass es noch erhebliches Optimierungspotential gibt. Neben Hardware-Anpassungen würde ich schätzen, dass sich die Geschwindigkeit vieler Gnurz-Funktionen nicht unwesentlich steigern ließen, wenn man die dahinter steckenden Algorithmen optimiert. Beispiele:
1. Die Berechnung von Primzahlen lässt sich weiter insbesondere durch die Einführung von Primzahltabellen im niedrigen Zahlenbereich und deren Nutzung für die Berechnung im großen Zahlenbereich sowie durch die Ausnutzung deterministischer Eigenschaften des Miller-Rabin-Algorithmus für bestimmte Zahlenbereiche optimieren.
2. GNZmul benutzt eine wichtige Optimierung: Für Zahlen mit mehr als 44 Stellen (GlobZahlenbasis) wird der Karazuba-Algorithmus benutzt, der für große Zahlen wesentlich schneller ist als herkömmliche Algorithmen aus der Schulmathematik. Mit dem Karazuba-Algorithmus ist das Ende der Fahnenstange der Optimierung aber noch nicht erreicht. Die Geschwindigkeit zur Berechnung des Produkts zweier Zahlen kann weiter durch die Nutzung der schnellen Fourier-Transformation beschleunigt werden.
Weiter habe ich festgestellt, dass die Nutzung von Arrays für den GNZTyp zwar vor unnötigen Speicherfehlern schützt, da die Arrays pascalintern gemanagt werden. Durch eine agressivere (und dadurch natürlich sehr fehleranfälligen) Programmierung mit Hilfe von Pointern könnten die von Pascal geregelten Array-Operationen durch an die Gegebenheit angepasste und daher schnellere Routinen ersetzt werden. Als weitere Optimierung kann man MMX benutzen - eine CPU-Einheit, die für die schnelle und vor allem parallele Berechnung von großen ganzen Zahlen geschaffen wurde. Durch die Nutzung mehrerer Threads lässt sich die Rechenlast auf mehrere Kerne einer CPU verteilen, was die Geschwindigkeit bei einem Vierkernprozessor z.B. nocheinmal fast vervierfachen kann. Alle Optimierungen zusammen genommen würden viele der Routinen schätzungsweise mindestens um einen Faktor 50 schneller machen.

Solche Optimierungen sind zwar möglich - sie machen den Code aber unübersichtlich, sind fehleranfällig und folglich schwer zu warten. Zudem sind die Optimierungen enorm aufwendig und benötigen Detailkenntnisse nicht nur hinsichtlich der Programmierung, sondern auch aus dem Bereich der Mathematik.

Man muss dabei beachten, welchen Stand die GNURZ-Unit vor einem halben Jahr hatte: Die Division dreißigstelliger Zahlen dauerte eine knappe Sekunde. Heute liegt die Zeitdauer für die Division tausendstelliger Zahlen im unteren Millisekunden-Bereich. Die Multiplikation arbeitete ineffizient und konnte inzwischen für große Zahlen ganz enorm beschleunigt werden, die Multiplikation zweier tausendstelliger Zahlen liegt im Bereich der Messungenauigkeit von gettickcount (2ms). Die Code-Optimierung ist wie gesagt sehr zeitaufwendig. Alleine für diese beiden, wenn auch beträchtlichen Optimierungen habe ich 6 Wochen arbeiten müssen.
Ich werde zwar mit der Zeit die ein- oder andere der oben genannten Optimierung umsetzen. In Anbetracht der Tatsache, dass ich mit der derzeiten Geschwindigkeit von GNURZ sehr gut zurecht komme, lege ich mein Hauptaugenmerk eher darauf, neue Features zu implementieren. Daher bin ich froh, dass die Arbeit an der GNURZ-Arithmetik-Unit manche, wie EugenE hinsichtlich 64bit, bei der Optimierung der Routinen unterstützen möchten.

Viele Grüße, Euklid

[EugenE]

...

Die GNURZ Arithmetik-Unit beinhaltet in der Version 0.99.3 nun auch einen Zufallsgenerator:

EUGENE: Habe ein vorzeitiges Weihnachtsgeschenk an dich :
Werde im laufe der kommenden Tage einen neuen Variablentyp einführen, den GGZTyp. Er wird negative Zahlen unterstützen.

Jippiiee

P.S.: FPC kann doch operator overloading. Wäre das nicht praktisch ?

Mit der Einführung von 64bit-Operatoren ließe sich die Berechnungsgeschwindigkeit für sehr große Zahlen fast verdoppeln. Wen EugenE das machen möchte, wäre daher eine von mir sehr willkommene Optimierung.

Ich glaube da gibts etwas verwirrung, ich wollte die Operatoren wie * / mod + - usw überladen damit man nicht mehr GNZMul GNZMod etc schreiben muss. Das mit 64-Bit habe ich leider nicht gemeint.

Tut mir leid das es zu einer Verwirrung gekommen ist

[Euklid]

Werde im laufe der kommenden Tage einen neuen Variablentyp einführen, den GGZTyp. Er wird negative Zahlen unterstützen.

Dieser Zahlentyp ist nun eingeführt worden. Negative Zahlen werden also von der GNURZ ab Version 0.99.4 zunächst experimentell unterstützt. Habe die Datei unten angehängt.

EugenE: Wäre dir sehr dankbar, wenn du mir auch ein "Weihnachtsgeschenk" machen könntest und die GGZ-Funktionen auf Herz und Nieren überprüfst, ob sie denn richtig arbeiten. Wenn du mir dann sagst, die Funktionen arbeiten fehlerfrei, werden sie von dem experimentellen Status in den offiziellen gehoben.

Integriert wurden die folgenden Funktionen:

Code: Alles auswählen

function GNZtoGGZ(NatZ:GNZTyp;Vorzeichen_positiv:boolean): GGZTyp;  
      //Wandelt eine GNZ-Zahl in eine GGZ.
      function GGZtoGNZ(Zahl:GGZTyp):GNZTyp;  
      //schneidet das Vorzeichen ab und gibt eine GNZ zurück.
      function GGZadd(a,b:GGZTyp):GGZTyp; 
      //Gibt die Summe a + b zurueck.
      function GGZsub(Minuent,Subtrahend:GGZTyp):GGZTyp; 
      // Rechnet Minuend-Subtrahend.
      function GGZmul(a,b:GGZTyp):GGZTyp;  
      //Gibt das Produkt a*b zurueck.
      function GGZmulword(a:dword;b:GGZTyp):GGZTyp; 
      // Wie GGZmul, nur ist a vom Typ dword
      function GGZakleinerb(a,b:GGZTyp):boolean; inline; 
      // Prueft, ob a kleiner ist als b
      function GGZagleichb(a,b:GGZTyp):boolean; inline; 
      // Prueft, ob sich a und b gleichen.
      function GGZdiv(Divident, Divisor:GGZTyp):GGZTyp;  
      //dividiert Divident durch Divisor und gibt das Ergebnis zurueck
      function GGZmod(Divident, Divisor:GGZTyp):GGZTyp; 
      //Gibt Divident mod Divisor zurueck
      function GGZistgerade(zahl:GGZTyp):boolean; inline; 
      //Prueft, ob zahl mod 2 = 0

Eine GGZ kann man durch die Funktion GNZtoGGZ erstellen - hier wird eine positive natürliche Zahl NatZ übergeben. Vorzeichen_positiv muss bei positivem Vorzeichen true und bei negativem Vorzeichen false sein.
Die Rücktransformation geschieht über GGZtoGNZ.

Viele Grüße, Euklid

[EugenE]

Hey,

ich habe noch nicht mit dem Testen und dem Operatoren-Overload angefangen jedoch vllt kannst du mir helfen ^^.

Kann man die GNZPotenzMod irgendwie verschnellern? ( ich weiß, machs selber xD , aber kp wie^^)

Also mein Rechner ( Dual Core 1.73GHz, mit 2GB Ram) braucht ca 3-5 Sekunden fuer diese Rechnung:

( aufgeteilt damit man es lesen kann xD )

Code: Alles auswählen

 
1018403188188111241473327790049056819374171287458066325110414569683
7124189161711984272884348651335847261443444275649905562839583004732
3549072317112368671754351361393425631187333448712634399571658198707
9949228100933774960721707770417974898090797578147319435850611145774
7945052613334208162647468947319257246914069777082660172096599627566
1435480949039912340023718736596494628257019128042533338157955137787
1163174901831120931491114041716511064972446847591319754880627720262
8482027304233273150871793911899680700857331825479302705388164456464
635323735211573881344703555741679
 
^ ( potenz )
 
2964882407392307851332923206234880919373556372533612561062281245348
4169110960380384960826410972342485824886199341383837048860241018889
3792631654979092643715448924957905471001256939451842829864798262060
9958485464578608079846124545374736619569296133987166556897523468457
1143180355837490982790357078237176518260289646352525921943996124801
8690729736870879758610131514036239031137084258834607977471660498849
8255700302636793031304894132442468019100280080974435917248519120005
8419353022794620124728059792976524921321179049752326500312564164289
694174637445047028458199328463553
 
MOD
 
6013997149289886484491301977584039255762598169503138003692084875331
9116667909242910086169381520239045140742116754781557535145334470973
5728003964983704828521085864528534726422663169715522740379026907068
2735944546517203216359019050297509879777007710223258101715634840807
8235477874327110807120309275353868419425694704664152842136499249894
1026209464115274491360653550958043943351638795234358041833659030857
0274562291826229076591408400617491691037235847262918522499396379670
0459226436023773677185954297308912761892467364285181970482656162106
133463348196991684245467051288867
 

Das was ihr da seht ist eine Entschlüsselung eines mit einem RSA-1900 ( ca ^^) noch nicht mal 2048 , weil das dann noch langsamer wäre ^^

Gibt es da vielleicht irgendwelche Mathematische Lösungen um solche Formeln unter ner Sekunde zu rechnen?