[C++] klasse bigint met pow()

[Verwijderd]

Ik ben bezig met een encryptieprogramma voor willekeurige files m.b.h.v. RSA encryptie. In java is er een klasse bigint ter beschikking met alles erop en eraan maar in C++ dus blijkbaar niet. De bedoeling is dus dat ik net zoals rekenprogramma's als maple en matlab symbolisch kan rekenen zodat astronomisch grote getallen (lees 512 bitgetallen en groter) kunnen verwerkt worden.

Ik heb al gezocht op google en heb o.a. een interessant werk gevonden van AP Computer Science betreffende "THE LARGE INTEGER CASE STUDY IN C++" en ik moet zeggen daar staat heel erg interessante informatie in hoe de klasse bigint moet opgebouwd worden enzo. Maar voor de machtsfunctie slaan ze de boot mis. Er wordt daar wel vermelding van gedaan maar de functie pow() werkt niet correct (wat ze zelf ook aangeven).

Nu is mijn vraag weet iemand waar ik een werkende bibliotheek kan vinden voor "big numbers" in C++ met een pow() en een modulo (%) functie?

Via google zijn er overigens nog andere bibliotheken te vinden (zonder al te veel uitleg zoals in eerder gevonden werk) maar vaak werken ze niet of compileren ze niet of zijn de links niet meer werkend.

[curry684]

Verwijderd schreef op 09 april 2004 @ 13:28:
Nu is mijn vraag weet iemand waar ik een werkende bibliotheek kan vinden voor "big numbers" in C++ met een pow() en een modulo (%) functie?

Psst officieel is dit een scriptrequest... dit lijkt me echter iets wat je toch ook wel zelf kunt schrijven? Heb je al eens over de benodigde algoritmes nagedacht om een bigint hiermee te bakken?

[Zoijar]

Efficiente "big-int" algoritmes zijn niet zo triviaal toch? Ik heb een keer een vermenigvuldiging moeten schrijven, en daar kwam van alles bij kijken, tot aan FFT transformaties. Wat ik me van algebra kan herinneren, was een efficiente 'modulo macht' ook niet zo triviaal...

[curry684]

Zoijar schreef op 09 april 2004 @ 13:36:
Efficiente "big-int" algoritmes zijn niet zo triviaal toch? Ik heb een keer een vermenigvuldiging moeten schrijven, en daar kwam van alles bij kijken, tot aan FFT transformaties. Wat ik me van algebra kan herinneren, was een efficiente 'modulo macht' ook niet zo triviaal...

Dat zeg ik: ik ruik hier een interessant topic

[Nvidiot]

Van wat ik mij nog kan herinneren van de laatste keer dat ik met RSA bezig was, is het verrekte nuttig om de pow en de mod in een functie te houden om de getalgrootte een beetje te beperken

[12_0_13]

Verdiep je wat meer in de algoritmes, je hebt namelijk helemaal geen big ints nodig meestal


Bijv als je bij a^71 % 93 wilt uitrekenen:

a^71 % 93 = ((a^64 % 93) * (a^4 % 93) * (a^2 % 93) * (a^1 % 93)) % 93

a^2 % 93 = ((a^1 %93) * (a^1 %93)) % 93
a^4 % 93 = ((a^2 %93) * (a^2 %93)) % 93

etc.

edit + + + vervangengen door * * *
edit2: % 93 toegevoegd (het ging ook eigenlijk alleen maar om het idee )

[ Voor 25% gewijzigd door 12_0_13 op 09-04-2004 13:54 ]

[Verwijderd]

12_0_13 schreef op 09 april 2004 @ 13:42:
Verdiep je wat meer in de algoritmes, je hebt namelijk helemaal geen big ints nodig meestal


Bijv als je bij a^71 % 93 wilt uitrekenen:

a^71 % 93 = a^64 % 93 + a^4 % 93 + a^2 % 93+ a^1 % 93

a^2 % 93 = ((a^1 %93) * (a^1 %93)) % 93
a^4 % 93 = ((a^2 %93) * (a^2 %93)) % 93

etc.

Niet waar...
Die optelling kan meer dan 93 worden...

[kris_112]

12_0_13 schreef op 09 april 2004 @ 13:42:
Verdiep je wat meer in de algoritmes, je hebt namelijk helemaal geen big ints nodig meestal


Bijv als je bij a^71 % 93 wilt uitrekenen:

a^71 % 93 = a^64 % 93 + a^4 % 93 + a^2 % 93+ a^1 % 93

a^2 % 93 = ((a^1 %93) * (a^1 %93)) % 93
a^4 % 93 = ((a^2 %93) * (a^2 %93)) % 93

etc.

Bij RSA-encryptie wordt meestal met zulke grote getallen gewerkt dat het getal voordat je uberhaubt gaat machtsverheffen al niet te representeren is in een normale integer, dus bigint is wel degelijk nodig.

[Zoijar]

Dat moet volgens mij ook een vermenigvuldiging zijn. x^6 != x^2+x^4, maar x^2*x^4

[.oisyn]

Volgens mij kon modulo-machtsverheffen puur met bitbewerkingen en optellen, waarvoor je dus al helemaal geen bigint nodig hebt. Een optelling van getallen die groter zijn dan de primitives die je tot je beschikking hebt zijn namelijk vrij simpel te maken (zoals je het op de basisschool geleerd hebt: individuele digits optellen met onthouden, ipv digits gebruik je dan gewoon een int oid)

Ik zal het eens even opzoeken

[Verwijderd]

Misschien helpt dit:
http://www-math.mit.edu/18.310/secrect_coding2.html
(sectie 4)

[ Voor 7% gewijzigd door Verwijderd op 09-04-2004 13:56 ]

[Zoijar]

.oisyn schreef op 09 april 2004 @ 13:52:
Volgens mij kon modulo-machtsverheffen puur met bitbewerkingen en optellen, waarvoor je dus al helemaal geen bigint nodig hebt. Een optelling van getallen die groter zijn dan de primitives die je tot je beschikking hebt zijn namelijk vrij simpel te maken (zoals je het op de basisschool geleerd hebt: individuele digits optellen met onthouden, ipv digits gebruik je dan gewoon een int oid)

Ik zal het eens even opzoeken

Ja de meeste van die dingen zijn op de simpele manier in O(n) te doen, door gewoon een lijst van bits bij te houden. Maar volgens mij moet er ook veel te doen zijn in O(log n)...heb er verder niet zo hel veel ervaring mee. Vermenigvuldigen waar ik het net over had wordt alleen O(N²) op die manier, en met fft kan je dat terug brengen tot O(n log n)

[Verwijderd]

Psst officieel is dit een scriptrequest... dit lijkt me echter iets wat je toch ook wel zelf kunt schrijven?

Dit is idd een beetje een scriptrequest, maar het gaat mij niet alleen om de klasse te hebben. Zelf schrijven? Jah bepaalde stukken zijn idd heel gemakkelijk te doen, zeker met de info die ik reeds heb gevonden. De constructor, destructor, de printfuncties en bepaalde gemakkelijkere bewerkingen zoals 2e-machten, optellen en aftrekken zijn heel goed zelf te schrijven. Ook de conversies die ik nodig heb gaat nog.
Maar...

Efficiente "big-int" algoritmes zijn niet zo triviaal toch? Ik heb een keer een vermenigvuldiging moeten schrijven, en daar kwam van alles bij kijken, tot aan FFT transformaties. Wat ik me van algebra kan herinneren, was een efficiente 'modulo macht' ook niet zo triviaal...

Inderdaad niet zo triviaal, ik kan natuurlijk iets al snap ik niet wat FFT bij een vermenigvuldiging van een groot getal komt te doen. Ik heb de FFT ooit gebruikt om het frequentiespectrum van een beeld te bepalen en zo bepaalde informatie weg te laten maar ik zie het verband niet echt bij vermenigvuldigen van grote getallen. Daarvoor is mijn wiskunde toch nog wat te beperkt denk ik. Maar wat uitleg is altijd welkom, dat zijn dingen die me wel interesseren.

't probleem is het gaat mij nu vooral om het encrypteren van files, en nu zou ik java kunnen kiezen als taal om dat te doen maar dat wil ik niet want ik wil me verdiepen in C++ voor 't moment (C++ ken ik nog niet goed daarmee).

Maar blijkt dat de studie van grote getallen in C++ een zaak appart is. Misschien iemand die daarover interessante lectuur heeft?
Verder kan het toch niet dat die bibliotheken voor C++ niet voorhanden zijn, de klasse bigint is toch iets wat vaak gebruikt wordt in rekenprogramma's, encryptie enz...
Ik had ook eens uitleg gevraagd aan de assistent bij ons en die zei me dat dat idd niet standaard in C++ zat maar dat dat wel ergens beschikbaar moet zijn omdat dat toch iets courant is.

Volgens mij kon modulo-machtsverheffen puur met bitbewerkingen en optellen, waarvoor je dus al helemaal geen bigint nodig hebt.

Modulo gaat inderdaad met bitbewerkingen maar machtsverheffing ook?

[ Voor 7% gewijzigd door Verwijderd op 09-04-2004 14:05 ]

[Verwijderd]

Nog een methode om x^y mod z efficient te berekenen:
http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec4.pdf

[.oisyn]

.oisyn schreef op 09 april 2004 @ 13:52:
Volgens mij kon modulo-machtsverheffen puur met bitbewerkingen en optellen, waarvoor je dus al helemaal geen bigint nodig hebt. Een optelling van getallen die groter zijn dan de primitives die je tot je beschikking hebt zijn namelijk vrij simpel te maken (zoals je het op de basisschool geleerd hebt: individuele digits optellen met onthouden, ipv digits gebruik je dan gewoon een int oid)

Ik zal het eens even opzoeken

Toch niet helemaal

code:

modpow (a,m,n)   // a^m % n
{
    res = 1;
    conta = int(2log(m)); // #bits - 1    
    for (i = conta; i >= 0; i--)
    {
        res = (res * res) % n; 
        if (bi = 1) res = (res * a) % n;
    }                
    return res;
}

Je zit nog altijd met een vermenigvuldiging en een modulo
.edit: oh er zit denk ik nog een onduidelijkheid in, bi is volgens mij de i'de bit in m, oftewel, als de i'de bit in m geset is, dan moet je nog even (res * a) % n erbij optellen

(zie hier voor meer info )

[ Voor 15% gewijzigd door .oisyn op 09-04-2004 14:25 ]

[kris_112]

Misschien helpt dit:

Welcome to the GMP web pages! Here you can find information about the GNU Multiple Precision Arithmetic Library, the fastest bignum library on the planet!

http://www.swox.com/gmp

[Verwijderd]

code:

modpow (a,m,n)   // a^m % n
{
    res = 1;
    conta = int(2log(m)); // #bits - 1    
    for (i = conta; i >= 0; i--)
    {
        res = (res * res) % n; 
        if (bi = 1) res = (res * a) % n;
    }                
    return res;
}

Dit is echt interessant, met een interessante ppt-presentatie erbij! Al heb ik als ik de bitmethode gebruik een probleem met het bepalen van zo grote priemgetallen in hun binaire voorstelling, nuja daar moet ik me dan nog wat verder in verdiepen.

thaRealKris schreef op 09 april 2004 @ 14:09:
Misschien helpt dit:

[...]

http://www.swox.com/gmp

Die had ik zelf ook al gevonden en die is inderdaad goed maar ik vind die zo groot om mee te geven, er staat té veel in. Meer dan dat ik nodig heb en ik wou eigenlijk iets realiseren met juist datgene wat ik nodig had.

[ Voor 45% gewijzigd door Verwijderd op 09-04-2004 14:17 ]

[Zoijar]

Verwijderd schreef op 09 april 2004 @ 14:00:
Inderdaad niet zo triviaal, ik kan natuurlijk iets al snap ik niet wat FFT bij een vermenigvuldiging van een groot getal komt te doen. Ik heb de FFT ooit gebruikt om het frequentiespectrum van een beeld te bepalen en zo bepaalde informatie weg te laten maar ik zie het verband niet echt bij vermenigvuldigen van grote getallen. Daarvoor is mijn wiskunde toch nog wat te beperkt denk ik. Maar wat uitleg is altijd welkom, dat zijn dingen die me wel interesseren.

Fourier transformaties zijn veel krachtiger dan veel mensen denken Het is niet alleen nuttig voor signal processing. In feite is het een lineaire algebra "truckje" om naar een andere basis over te gaan.

Je neemt je getallen bv A="123" en B="567" als polynomen (3*10^0 + 2*10^1 + 1*10^2) En dan heb je plotseling twee "vectoren" in een lineaire ruimte. Die kan je dan op een slimme manier naar een andere basis transformeren met een fft, waar je makkelijker het product van de twee polynomen kan bepalen, C(x)=A(x)*B(x). Dat

edit:
C(x) bepalen door A en B te sampelen bedoel ik, en dan in een priem lichaam met elementen van bepaalde orde...

polynoom kan je dan sampelen (polynoom staat vast met 'hoogste-macht' punten gegeven) en interpoleren... Details moet je echt op google zoeken, want dat zouden wel eens wat paginas kunnen worden...

Op google vond ik snel dit, heb het niet gelezen, maar zal wel hetzelfde zijn.
http://numbers.computatio...tants/Algorithms/fft.html

[ Voor 7% gewijzigd door Zoijar op 09-04-2004 14:19 ]

[.oisyn]

Meer daarover in [rml][ c++] Fast Fourier Transform[/rml]

[Zoijar]

.oisyn schreef op 09 april 2004 @ 14:27:
Meer daarover in [rml][ c++] Fast Fourier Transform[/rml]

Ja, ik had al zo'n deja vu gevoel maar wist niet precies meer waarom...maar dat was het dus