Rechnen mit sehr großen Zahlen...
-
- Beiträge: 1445
- Registriert: Fr 10. Okt 2008, 23:54
- OS, Lazarus, FPC: Winuxarm (L 3.0 FPC 3.2)
- CPU-Target: 32/64Bit
Rechnen mit sehr großen Zahlen...
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
Vielen Dank für die Hilfe.
Grüße Markus
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
Vielen Dank für die Hilfe.
Grüße Markus
EleLa - Elektronik Lagerverwaltung - www.elela.de
-
- Beiträge: 306
- 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...
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)
- af0815
- Lazarusforum e. V.
- Beiträge: 6198
- Registriert: So 7. Jan 2007, 10:20
- OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
- CPU-Target: 32Bit (64Bit)
- Wohnort: Burgenland
- Kontaktdaten:
Re: Rechnen mit sehr großen Zahlen...
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.
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).
-
- Beiträge: 1445
- Registriert: Fr 10. Okt 2008, 23:54
- OS, Lazarus, FPC: Winuxarm (L 3.0 FPC 3.2)
- CPU-Target: 32/64Bit
Re: Rechnen mit sehr großen Zahlen...
Vielen Dank, ich schaue es mir an.
... Das Demo läuft mit Lazarus V2.0.10 auf Anhieb.
... Das Demo läuft mit Lazarus V2.0.10 auf Anhieb.
EleLa - Elektronik Lagerverwaltung - www.elela.de
- Winni
- Beiträge: 1577
- Registriert: Mo 2. Mär 2009, 16:45
- OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
- CPU-Target: 64Bit
- Wohnort: Fast Dänemark
Re: Rechnen mit sehr großen Zahlen...
Hi!
Falls 10^64 für Deinen Fall genug ist, kannst Du auch mit BCDs rechnen:
https://wiki.freepascal.org/BcdUnit
Winni
Falls 10^64 für Deinen Fall genug ist, kannst Du auch mit BCDs rechnen:
https://wiki.freepascal.org/BcdUnit
Winni
- af0815
- Lazarusforum e. V.
- Beiträge: 6198
- Registriert: So 7. Jan 2007, 10:20
- OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
- CPU-Target: 32Bit (64Bit)
- Wohnort: Burgenland
- Kontaktdaten:
Re: Rechnen mit sehr großen Zahlen...
Winni, er sprach von richtig großen Zahlen
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).
- Winni
- Beiträge: 1577
- Registriert: Mo 2. Mär 2009, 16:45
- OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
- CPU-Target: 64Bit
- Wohnort: Fast Dänemark
Re: Rechnen mit sehr großen Zahlen...
Hi!
Kannst Du nicht lesen???
Ich hab gesagt "Falls 10^64 für Deinen Fall genug ist...."
Damit ist doch alles gesagt.
Winni
Kannst Du nicht lesen???
Ich hab gesagt "Falls 10^64 für Deinen Fall genug ist...."
Damit ist doch alles gesagt.
Winni
- af0815
- Lazarusforum e. V.
- Beiträge: 6198
- Registriert: So 7. Jan 2007, 10:20
- OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
- CPU-Target: 32Bit (64Bit)
- Wohnort: Burgenland
- Kontaktdaten:
Re: Rechnen mit sehr großen Zahlen...
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).
- Winni
- Beiträge: 1577
- Registriert: Mo 2. Mär 2009, 16:45
- OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
- CPU-Target: 64Bit
- Wohnort: Fast Dänemark
Re: Rechnen mit sehr großen Zahlen...
Hauptsache der Balkan sabbelt ...
-
- Beiträge: 1908
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Rechnen mit sehr großen Zahlen...
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.
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.
-
- 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...
Hallo Markus,
Du meinst so?
a x b = 2^4096 * 2^4096
1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336
* 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336
= 1090748135619415929462984244733782862448264161996232692431832786189721331849119295216264234525201987223957291796157025273109870820177184063610979765077554799078906298842192989538609825228048205159696851613591638196771886542609324560121290553901886301017900252535799917200010079600026535836800905297805880952350501630195475653911005312364560014847426035293551245843928918752768696279344088055617515694349945406677825140814900616105920256438504578013326493565836047242407382442812245131517757519164899226365743722432277368075027627883045206501792761700945699168497257879683851737049996900961120515655050115561271491492515342105748966629547032786321505730828430221664970324396138635251626409516168005427623435996308921691446181187406395310665404885739434832877428167407495370993511868756359970390117021823616749458620969857006263612082706715408157066575137281027022310927564910276759160520878304632411049364568754920967322982459184763427383790272448438018526977764941072715611580434690827459339991961414242741410599117426060556483763756314527611362658628383368621157993638020878537675545336789915694234433955666315070087213535470255670312004130725495834508357439653828936077080978550578912967907352780054935621561090795845172954115972927479877527738560008204118558930004777748727761853813510493840581861598652211605960308356405941821189714037868726219481498727603653616298856174822413033485438785324024751419417183012281078209729303537372804574372095228703622776363945290869806258422355148507571039619387449629866808188769662815778153079393179093143648340761738581819563002994422790754955061288818308430079648693232179158765918035565216157115402992120276155607873107937477466841528362987708699450152031231862594203085693838944657061346236704234026821102958954951197087076546186622796294536451620756509351018906023773821539532776208676978589731966330308893304665169436185078350641568336944530051437491311298834367265238595404904273455928723949525227184617404367854754610474377019768025576605881038077270707717942221977090385438585844095492116099852538903974655703943973086090930596963360767529964938414598185705963754561497355827813623833288906309004288017321424808663962671333528009232758350873059614118723781422101460198615747386855096896089189180441339558524822867541113212638793675567650340362970031930023397828465318547238244232028015189689660418822976000815437610652254270163595650875433851147123214227266605403581781469090806576468950587661997186505665475715792896
= 2^8192
Beste Grüße
Andreas
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
-
- Beiträge: 1445
- Registriert: Fr 10. Okt 2008, 23:54
- OS, Lazarus, FPC: Winuxarm (L 3.0 FPC 3.2)
- CPU-Target: 32/64Bit
Re: Rechnen mit sehr großen Zahlen...
Ja, genau. solche schönen Zahlenreihen lassen sich mit recht einfacher Berechnung wunderbar verschlüsseln.
EleLa - Elektronik Lagerverwaltung - www.elela.de
-
- Lazarusforum e. V.
- Beiträge: 2808
- 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...
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:
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.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
Liebe Grüße, Euklid
Zuletzt geändert von Euklid am So 6. Dez 2020, 19:21, insgesamt 1-mal geändert.
-
- Beiträge: 1908
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Rechnen mit sehr großen Zahlen...
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
- corpsman
- Lazarusforum e. V.
- Beiträge: 1496
- 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...
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
https://web.archive.org/web/20190628091 ... index.html
--
Just try it
Just try it