Rechnen mit sehr großen Zahlen...

Für alles, was in den übrigen Lazarusthemen keinen Platz, aber mit Lazarus zutun hat.
MmVisual
Beiträge: 1219
Registriert: Fr 10. Okt 2008, 23:54
OS, Lazarus, FPC: Winuxarm (L 2.0.10 FPC 3.2)
CPU-Target: 32/64Bit

Rechnen mit sehr großen Zahlen...

Beitrag von MmVisual »

Hallo,

Gibt es in Lazarus/FPC eine Bibliothek um mit richtig großen Zahlen zu rechnen?
also größer als QWord 2^64? z.B. 2^4096 * 2^4096?

Oder habt Ihr Tipps dazu?

Es geht um Verschlüsselungstechniken. Also jeder normale Mensch sollte so etwas nutzen :D

Vielen Dank für die Hilfe.

Grüße Markus

u-boot
Beiträge: 302
Registriert: Do 9. Apr 2009, 10:10
OS, Lazarus, FPC: Ubuntu 9.10 (L 0.9.28 FPC 2.2.4)
CPU-Target: 32Bit
Wohnort: 785..

Re: Rechnen mit sehr großen Zahlen...

Beitrag von u-boot »

Vermutlich suchst du GNURZ. Ich habe es noch nicht ausprobiert. Es gibt aber schon den ein oder anderen Beitrag aus alten Zeiten dazu.
Ubuntu 9.10 (L 0.9.28 FPC 2.4.x)

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 4755
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Rechnen mit sehr großen Zahlen...

Beitrag von af0815 »

Ich habe eine Version gerettet, bevor Lazforge verschwunden ist. Euklid hat dann die aktuelle Version einpflegen lassen.

https://github.com/afriess/GNURZ

Keine Ahnung ob sich die mit neuen Lazarus kompilieren lässt, aber Euklid der Ersteller der Bibliothek ist auch hier im Forum.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

MmVisual
Beiträge: 1219
Registriert: Fr 10. Okt 2008, 23:54
OS, Lazarus, FPC: Winuxarm (L 2.0.10 FPC 3.2)
CPU-Target: 32/64Bit

Re: Rechnen mit sehr großen Zahlen...

Beitrag von MmVisual »

Vielen Dank, ich schaue es mir an.

... Das Demo läuft mit Lazarus V2.0.10 auf Anhieb.

Benutzeravatar
Winni
Beiträge: 980
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.0.12, fpc 3.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Winni »

Hi!

Falls 10^64 für Deinen Fall genug ist, kannst Du auch mit BCDs rechnen:

https://wiki.freepascal.org/BcdUnit

Winni

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 4755
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Rechnen mit sehr großen Zahlen...

Beitrag von af0815 »

Winni, er sprach von richtig großen Zahlen :-)
MmVisual hat geschrieben:
Sa 5. Dez 2020, 08:59
also größer als QWord 2^64? z.B. 2^4096 * 2^40966
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
Winni
Beiträge: 980
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.0.12, fpc 3.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Winni »

Hi!

Kannst Du nicht lesen???

Ich hab gesagt "Falls 10^64 für Deinen Fall genug ist...."

Damit ist doch alles gesagt.

Winni

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 4755
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Rechnen mit sehr großen Zahlen...

Beitrag von af0815 »

Winni hat geschrieben:
Sa 5. Dez 2020, 15:10
Kannst Du nicht lesen???
Das gebe ich glatt zurück, in der Frage im ersten Post stand es drinnen, für welche Zahlengröße. Damit ist der Hinweis auf BCD überflüssig.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
Winni
Beiträge: 980
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.0.12, fpc 3.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Winni »

Hauptsache der Balkan sabbelt ...

Warf
Beiträge: 1585
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Warf »

Der FPC liefert soweit ich weiß einen Wrapper für die GMP mit: https://wiki.lazarus.freepascal.org/gmp

Aber denk dran, nur die Fähigkeit mit großen Zahlen rechnen zu können allein macht dich wahrscheinlich nicht glücklich, da naive rechenansätze für diese dimensionen viel zu langsam sind, selbst mit gmp, was die wahrscheinlich am besten optimierte lib in diesem Bereich ist. Du musst halt auch intelligent rechnen (Chinese Remainder Theorem ist dein Freund).

Und natürlich der typische disclaimer: Crypto algorithmen zu implementieren ist zwar schön und gut zu übungszwecken, aber wenn du was für den produktionseinsatz suchst, greif lieber auf Bibliotheken zurück die von profis geschrieben wurden, z.b. für RSA kannst du ganz einfach die OpenSSL benutzen, denn es gibt einen haufen Probleme auf die man selbst nicht so einfach kommt, mit denen sich projekte wie die OpenSSL aber schon (z.T. schmerzhaft) auseinander setzen mussten.

AndreasMR
Beiträge: 98
Registriert: Di 4. Aug 2015, 15:29
OS, Lazarus, FPC: Linux, Raspbian, Windows
CPU-Target: 64/32 Bit

Re: Rechnen mit sehr großen Zahlen...

Beitrag von AndreasMR »

Hallo Markus,

Du meinst so?

a x b = 2^4096 * 2^4096
1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336
* 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336

= 1090748135619415929462984244733782862448264161996232692431832786189721331849119295216264234525201987223957291796157025273109870820177184063610979765077554799078906298842192989538609825228048205159696851613591638196771886542609324560121290553901886301017900252535799917200010079600026535836800905297805880952350501630195475653911005312364560014847426035293551245843928918752768696279344088055617515694349945406677825140814900616105920256438504578013326493565836047242407382442812245131517757519164899226365743722432277368075027627883045206501792761700945699168497257879683851737049996900961120515655050115561271491492515342105748966629547032786321505730828430221664970324396138635251626409516168005427623435996308921691446181187406395310665404885739434832877428167407495370993511868756359970390117021823616749458620969857006263612082706715408157066575137281027022310927564910276759160520878304632411049364568754920967322982459184763427383790272448438018526977764941072715611580434690827459339991961414242741410599117426060556483763756314527611362658628383368621157993638020878537675545336789915694234433955666315070087213535470255670312004130725495834508357439653828936077080978550578912967907352780054935621561090795845172954115972927479877527738560008204118558930004777748727761853813510493840581861598652211605960308356405941821189714037868726219481498727603653616298856174822413033485438785324024751419417183012281078209729303537372804574372095228703622776363945290869806258422355148507571039619387449629866808188769662815778153079393179093143648340761738581819563002994422790754955061288818308430079648693232179158765918035565216157115402992120276155607873107937477466841528362987708699450152031231862594203085693838944657061346236704234026821102958954951197087076546186622796294536451620756509351018906023773821539532776208676978589731966330308893304665169436185078350641568336944530051437491311298834367265238595404904273455928723949525227184617404367854754610474377019768025576605881038077270707717942221977090385438585844095492116099852538903974655703943973086090930596963360767529964938414598185705963754561497355827813623833288906309004288017321424808663962671333528009232758350873059614118723781422101460198615747386855096896089189180441339558524822867541113212638793675567650340362970031930023397828465318547238244232028015189689660418822976000815437610652254270163595650875433851147123214227266605403581781469090806576468950587661997186505665475715792896
= 2^8192



Beste Grüße

Andreas
Ubuntu 14.04 LTS / Raspbian / Windows: Lazarus ab 0.9 bis 3.0

MmVisual
Beiträge: 1219
Registriert: Fr 10. Okt 2008, 23:54
OS, Lazarus, FPC: Winuxarm (L 2.0.10 FPC 3.2)
CPU-Target: 32/64Bit

Re: Rechnen mit sehr großen Zahlen...

Beitrag von MmVisual »

Ja, genau. solche schönen Zahlenreihen lassen sich mit recht einfacher Berechnung wunderbar verschlüsseln. :D

Euklid
Lazarusforum e. V.
Beiträge: 2807
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Euklid »

MmVisual hat geschrieben:
So 6. Dez 2020, 10:57
Ja, genau. solche schönen Zahlenreihen lassen sich mit recht einfacher Berechnung wunderbar verschlüsseln. :D
Hallo MmVisual,

falls Du sie für Verschlüsselung verwenden möchtest, eignet sich besonders der schnelle Primzahltest für sehr große Zahlen mit der Bezeichnung "GNZMillerRabin" und "GNZMRPrimdanach". Er basiert auf dem blitzschnellen Miller-Rabin-Primzahltest für außerordentlich große Zahlen: https://de.wikipedia.org/wiki/Miller-Rabin-Test
it gibt die Anzahl der Iterationen an. Die Wahrscheinlichkeit, dass eine Zahl, die den Test mit it Interationen besteht und nicht Prim ist, ist (1/4)^it - das geht für einige Iterationen sehr schnell gegen Null.

Da die Demo nicht alle Funktionen für ganze Zahlen umfasst, hier ein Überblick:
function GNZadd(a,b:GNZTyp):GNZTyp; //Gibt die Summe a + b zurueck. Rechnet mit Grossen Natuerlichen Zahlen (GNZ); Zbasis=Zahlenbasis (Dezimalsystem:Zbasis=10)
function GNZsub(Minuent,Subtrahend:GNZTyp):GNZTyp; // WICHTIG: Es muss Minuend>Subtrahend sein!; Rechnet Minuend-Subtrahend.
function GNZmul(a,b:GNZTyp):GNZTyp; //Gibt das Produkt a*b zurueck. Rechnet mit grossen natuerlichen Zahlen.
function GNZmulword(a:dword;b:GNZTyp):GNZTyp; // Wie GNZmul, nur ist a vom Typ dword
function GNZakleinerb(a,b:GNZTyp):boolean; inline; // Prueft, ob a kleiner ist als b
function GNZagleichb(a,b:GNZTyp):boolean; inline; // Prueft, ob sich a und b gleichen.
function GNZdiv(Divident, Divisor:GNZTyp):GNZTyp; //dividiert Divident durch Divisor und gibt das Ergebnis zurueck
function GNZmod(Divident, Divisor:GNZTyp):GNZTyp; //Gibt Divident mod Divisor zurueck
function GNZggt(a,b:GNZTyp):GNZTyp; inline; //Wie ggt, nur fuer grosse natuerliche Zahlen (GNZ)
function GNZkgv(a,b:GNZTyp):GNZTyp; inline; //Wie kgv, nur fuer GNZ
function GNZistgerade(zahl:GNZTyp):boolean; inline; //Prueft, ob zahl mod 2 = 0
function GNZPotenz(Basis,Exponent:GNZTyp):GNZTyp; //Gibt Zahl^Exponent zurueck. Nach einem im Internet gefundenen Algorithmus
function GNZPotenzMod(Basis,Exponent,Modulo:GNZTyp):GNZTyp; //Rechnet Basis^Exponent mod Modulus.
function GNZFakultaet(nFak:dword):GNZTyp; // Gibt n! zurueck
function GNZIstPrim(zahl:GNZTyp):boolean; //Wahr, wenn zahl Primzahl
function GNZMillerRabin(zahl:GNZTyp; it:word):boolean; //Miller-Rabin Primzahltext. Wenn Zahl Test besteht: Mit Wahrscheinlichkeit (1/4)^it Primzahl.
function GNZMRPrimdanach(zahl:GNZTyp; it:word):GNZTyp; //Bestimmt die nach zahl nächste Primzahl.
function GNZZufall(Obergrenze:GNZTyp):GNZTyp; // Gibt eine Zufallszahl wieder, die kleiner ist als Obergrenze.
function GNZeins:GNZTyp; // Gibt 1 zurueck
function GNZnull:GNZTyp; // Gibt 0 zurueck
Die GNURZ enthält keine bekannten Bugs. Im Ordner von Andi auf Github befindet sich auch eine assembleroptimierte Variante, die allerdings noch BETA ist und nicht den vollen Funktionsumfang hat.

Liebe Grüße, Euklid
Zuletzt geändert von Euklid am So 6. Dez 2020, 19:21, insgesamt 1-mal geändert.

Warf
Beiträge: 1585
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Rechnen mit sehr großen Zahlen...

Beitrag von Warf »

Euklid hat geschrieben:
So 6. Dez 2020, 19:17
Die GNURZ enthält keine bekannten Bugs. Im Ordner von Andi auf Github befindet sich auch eine assembleroptimierte Variante, die allerdings noch BETA ist und nicht den vollen Funktionsumfang hat.
Man sollte erwähnen das die GNZZufall funktion nicht kryptografisch sicher ist, daher nicht für den einsatz von verschlüsselungen die in produktionssoftware verwendet wird geeignet

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1251
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Rechnen mit sehr großen Zahlen...

Beitrag von corpsman »

Ich nutze für Große Zahlen ganz gerne die leider nicht mehr gepflegte MPArith Lib von Wolfgang Erhardt

https://web.archive.org/web/20190628091 ... index.html
--
Just try it

Antworten