[C++] Modulo rekenen

[gyarnoc]

Hoi Allemaal,

Ik was bezig met RSA werkstuk voor wiskunde, en nou wilde ik een programaatje maken die de RSA formule kan uitvoeren:

getal ^ sleutel (mod N)

Dit lukt, maarrrr, met grote getallen met de exponent, duurt het ontzettend lang. Nu heb ik uitgevonden dat je ipv in 1 keer iets tot de macht te doen, en dan modulo, je ook (als je 2^4 hebt en mod is 3), 2x2 (mod 3), dat weer maal 2 (mod 3) en dat weer maal 2 (mod 3).

Dus krijg ik dit in C++:

C++:

#include <iostream.h>
int main()
{
    unsigned int getal, macht, modulo, uitkomst;
    int i;
    cout << "Getal?  ";
    cin >> getal;
    cout << "tot de macht?  ";
    cin >> macht;
    cout << "Modulo?  ";
    cin >> modulo;

    uitkomst = getal;

    for (i = 1; i < macht; i++){
        uitkomst = uitkomst * getal;
        uitkomst %= modulo;
    }

    cout << "Uiktomst: " << uitkomst << "\n\n";
    cin >> i;


    return 0;
}

Werkt allemaal goed, maar als ik dus grote getallen in voer, word dit te groot. Maak er dan een double van hoor ik iedereen zegge, jah, maar als ik dat doe:

F:\Program Files\Microsoft Visual Studio\MyProjects\expo2\expo.cpp(17) : error C2296: '%=' : illegal, left operand has type 'long double'
F:\Program Files\Microsoft Visual Studio\MyProjects\expo2\expo.cpp(17) : error C2297: '%=' : illegal, right operand has type 'long double'

Dus sinds waarom kan % niet met double ? Ik heb geprobeerd mijn eigen % functie te schrijven, maar zonder resultaat, het werkte gewoon niet en was ook nog eens veels te langzaam.

Google heeft ook geen resultaat, wel een mod() functie gevonden, maar die werkte niet?? Heeft iemand anders een idee of oplossing?

[NMe]

Probeer eens dit:

C++:

uitkomst = (int)uitkomst % modulo;

Op dit manier zeg je expliciet dat je een integer gebruikt. Ik kan me voorstellen dat een modulo niets betekent voor reeële getallen.

Edit:
Overigens is het schrijven van een eigen modulo functie zo moeilijk toch niet?

C++:

unsigned int mod(int getal, modulo) {
  while (getal > modulo) {
    getal -= modulo;
  }
  return getal;
}

Efficiënt is het niet, maar erg langzaam lijkt het me ook niet.

[ Voor 42% gewijzigd door NMe op 03-03-2005 19:01 ]

[gyarnoc]

-NMe- schreef op donderdag 03 maart 2005 @ 18:58:
Probeer eens dit:

C++:

uitkomst = (int)uitkomst % modulo;

Op dit manier zeg je expliciet dat je een integer gebruikt. Ik kan me voorstellen dat een modulo niets betekent voor reeële getallen.

Hoe bedoel je precies reeele getallen? Als ik dit doe krijg ik nog steeds een error dat rechts van de % een double staat:

F:\Program Files\Microsoft Visual Studio\MyProjects\expo2\expo.cpp(17) : error C2297: '%' : illegal, right operand has type 'long double'

[Anoniem: 106076]

Zelf heb ik hier ook een werkstuk over geschreven in het laatste jaar van de middelbareschool, als het je interesseert kun je hier m'n essay vandaan halen: http://home.student.utwen...ography_Mark_Klaassen.doc

suc6 ermee.

[ Voor 4% gewijzigd door Anoniem: 106076 op 03-03-2005 19:07 ]

[Michali]

dan doe je toch:

C++:

uitkomst = (int)uitkomst % (int)modulo;

edit:

lama, niet goed gelezen

[ Voor 24% gewijzigd door Michali op 03-03-2005 19:09 ]

[gyarnoc]

-NMe- schreef op donderdag 03 maart 2005 @ 18:58:


Edit:
Overigens is het schrijven van een eigen modulo functie zo moeilijk toch niet?

C++:

unsigned int mod(int getal, modulo) {
  while (getal > modulo) {
    getal -= modulo;
  }
  return getal;
}

Efficiënt is het niet, maar erg langzaam lijkt het me ook niet.

Getal? 111222333
tot de macht? 24888081
Modulo? 9991163911

Nu al een 2 minuten bezig, nog steeds niks.. Met de normale modulo krijg ik (weliswaar het foute antwoord, omdat de int te klein is voor 111222333 * 111222333) het antwoord in 3 seconden...

Dit word gebruikt voor RSA, en daar duurt het versleutelen ook niet lang.. mijn vraag is dus: Hoe zoiets te doen met de modulo van C++ ??

[gyarnoc]

Michali schreef op donderdag 03 maart 2005 @ 19:08:
dan doe je toch:

C++:

uitkomst = (int)uitkomst % (int)modulo;

edit:

lama, niet goed gelezen

Maar gaat er dan geen data verloren??

[Anoniem: 20174]

gyarnoc schreef op donderdag 03 maart 2005 @ 19:10:
[...]


Maar gaat er dan geen data verloren??

Ik denk dat je je eerst eens moet verdiepen in de begrippen modulo en double. Heel logisch dat de compiler gaat bitchen over deze combinatie.

Verder heb ik niet zo 1-2-3 parate C++ specifieke kennis, maar heb je al gekeken naar iets van int/unsigned int/long of wat er ook maar beschikbaar is?


Dat had je dus al gedaan zie ik nu in de code

[ Voor 7% gewijzigd door Anoniem: 20174 op 03-03-2005 19:24 ]

[gyarnoc]

Anoniem: 20174 schreef op donderdag 03 maart 2005 @ 19:18:
[...]


Ik denk dat je je eerst eens moet verdiepen in de begrippen modulo en double. Heel logisch dat de compiler gaat bitchen over deze combinatie.

Verder heb ik niet zo 1-2-3 parate C++ specifieke kennis, maar heb je al gekeken naar iets van int/unsigned int/long of wat er ook maar beschikbaar is?

Ik heb me inderdaad verdiept in modulo, maar double nog niet zo erg. Ik ben niet zo'n geweldige C++ programmeur, en vond het raar dat hij niet modulo kan uitvoeren met doubles.

Ik heb eigenlijk alle variabelen types geprobeert, en ik zie dat de unsigned long int maar maximaal 4.294.967.295 groot kan zijn, wat simpelweg niet genoeg is

[Zoijar]

Je hebt een 'bigint' nodig, dat is een string representatie van een getal, waar je mee kan rekenen. De algoritmes hiervoor zijn niet zo simpel (als je het snel wilt houden) maar je kan wel een library vinden denk ik. Meestal moeten dingen namelijk lineair in de string lengte van het getal zijn, of maximaal iets van n log n, zoals bij vermenigvuldiging (met FFT). Naief vermenigvuldigen resulteert in n^2. Optellen etc zijn simpel lineair te doen. Deling en modulo zal je ook iets op moeten verzinnen, anders gaat het te traag. Meestal kan je wel iets doen met grootst gemenedeler algoritmes...maar ik zou maar een library opzoeken

[NMe]

gyarnoc schreef op donderdag 03 maart 2005 @ 19:09:
Getal? 111222333
tot de macht? 24888081
Modulo? 9991163911

Die getallen zijn dan ook veel groter dan je mag gebruiken in een normale 16-bits integer. Als je zo'n grote getallen wil gebruiken heb je al minimaal een long long nodig, en zelfs dat zal al te klein zijn. Zoals Zoijar al zegt blijft een bigint over als een van de weinige opties die je hebt.

[gyarnoc]

Ho ho, niet te snel Hier snap ik niet veel van.. sorry.. Ik denk dat het niet erg is als het niet helemaal werkt voor dit Middelbaar onderwijs werkstukje.. Met kleinere getallen doet hij het, en daar ben ik allang blij om, hij moet morgen toch ingeleverd worden, maar ik ga zeker de Bigint verder uitzoeken, bedankt voor je antwoord!

[Janoz]

Dat een mod op een double niet werkt is heel logisch. Zodra de exponent groter wordt dan de significatie is het eerste getal voor de komma niet meer zeker. Het resultaat van een modulus operatie is dan niet meer bekend. Je kunt het plat gezegd zien als een getal met x cijfers samen met een exponent van 10 (ik neem decimaal voor het begrip. doubles en floats zitten natuurlijk in het tweetallig stelsel en hebben dus eigenlijk een exponent van 2). Heb je als getal dan 1234567890 en neem je als exponent 11 dan is de daadwerkelijke waarde groter of gelijk aan 12345678900, maar kleiner dan 12345678910. Het laatste getal kan dus alles zijn.


Daarnaast is d = a^b mod n ook ook te berekenen zonder dat je a^b hoeft uit te rekenen. Hiervoor moet je even op modular exponentiation of repeated squaring zoeken bij google.

[gyarnoc]

Janoz schreef op donderdag 03 maart 2005 @ 20:12:
Dat een mod op een double niet werkt is heel logisch. Zodra de exponent groter wordt dan de significatie is het eerste getal voor de komma niet meer zeker. Het resultaat van een modulus operatie is dan niet meer bekend. Je kunt het plat gezegd zien als een getal met x cijfers samen met een exponent van 10 (ik neem decimaal voor het begrip. doubles en floats zitten natuurlijk in het tweetallig stelsel en hebben dus eigenlijk een exponent van 2). Heb je als getal dan 1234567890 en neem je als exponent 11 dan is de daadwerkelijke waarde groter of gelijk aan 12345678900, maar kleiner dan 12345678910. Het laatste getal kan dus alles zijn.


Daarnaast is d = a^b mod n ook ook te berekenen zonder dat je a^b hoeft uit te rekenen. Hiervoor moet je even op modular exponentiation of repeated squaring zoeken bij google.

Thanks, ik zal kijke of ik het er nog snel in krijg, dit is echt geweldig

[Soultaker]

Je moet helemaal geen doubles willen gebruiken, maar grotere integers. Aangezien je modulo N rekent hoeft er nauwelijks meer dan N in te passen (maar pas op voor tussentijdse 'overflow'). Misschien voldoet voor jouw doel een 64-bits integer ('long long int') of anders een eigengemaakte 'grote' integer van 8 of 16 bytes ofzo. Arbitrary precision arithmetic is hiervoor echt overkill en maakt de boel niet efficiënter.

Verder moet je als je een exponent hebt van een miljard niet een miljard keer gaan vermenigvuldigen; dat is veel te traag. Maar je weet gelukkig dat b^Xb^Y = b^X+Y. Als je dus b^N wil uitrekenen en N is even, dan hoef je alleen maar M=N/2 te kiezen en als je dan b^M kwadrateert (met zichzelf vermenigvuldigt) dan heb je het gewenste getal gevonden; oftewel: b^N=b^Mb^M. Oneven getallen werken op dezelfde manier, behalve dat je dan bij de deling afrond omlaag en nog een keer extra moet vermenigvuldigen: b^N=b^Mb^Mb.

Nu kun je een algoritme schrijven dat een logaritmisch aantal vermenigvuldigingen uitvoert in plaats van een lineair aantal:

C++:

int exp(int b, int e, int m)
{
    if(e==0) return 1;
    if(e==1) return b%m;
    int x = exp(b, e/2, m), r = (x*x)%m;
    if(e%2==1) r = (r*b)%m;
    return r;
}

Hieruit blijkt dus dat in je integer tenminste m² moet passen om problemen met overflows te voorkomen. Als je hiervervolgens je eigen voldoende grote integer-klasse in stopt ben je in principe klaar.

[ Voor 4% gewijzigd door Soultaker op 03-03-2005 20:25 ]

[MSalters]

Yep. Unlimited-length integer classes zijn tricky, maar 4 of 8 ints combineren tot een grotere is best wel simpel. En dan is O(N*N) vermenigvuldigen best te overzien, net zoals een eigen operator%.

[MrBucket]

Anders moet je eens BC (Binary Calculator) uitproberen. Het is een arbitrary precision math-tooltje dat vanaf de commandline werkt. Bovendien ondersteunt het ook een soort van C scripttaaltje, wat ik destijds wel erg prettig vond werken (ik heb het zelf ook voor school moeten gebruiken voor cryptologie).

Het is een GNU-project, maar er bestaat ook een Win32 port van:
http://gnuwin32.sourceforge.net/packages/bc.htm

--edit: wat specifiekere links---
Handleiding staat hier: http://www.gnu.org/software/bc/manual/html_mono/bc.html
Download hier (in roze, de bovenste zip): http://sourceforge.net/pr...id=23617&release_id=50828

Start het maar eens op ("bin/bc.exe"), en typ bijv. in:

code:

(7365 ^ 548) % 287

Het resultaat staat binnen een seconde op je scherm: 64

[ Voor 35% gewijzigd door MrBucket op 03-03-2005 20:53 ]

[Soultaker]

Sterker nog: in de C++ standaard zit zelfs een power() functie die efficiënt aan machtsverheffen doet volgens een algoritme zoals ik beschreef! Dat hoef je dus alvast zelf niet te schrijven, maar dan moet je wel zelf je grote-integer-modulo-N-klasse implementeren.

[Soultaker]

MrBucket schreef op donderdag 03 maart 2005 @ 20:37:
Anders moet je eens BC (Binary Calculator) uitproberen. Het is een arbitrary precision math-tooltje dat vanaf de commandline werkt. Bovendien ondersteunt het ook een soort van C scripttaaltje, wat ik destijds wel erg prettig vond werken (ik heb het zelf ook voor school moeten gebruiken voor cryptologie).
[..]
Start het maar eens op ("bin/bc.exe"), en typ bijv. in:

code:

(7365 ^ 548) % 287

Het resultaat staat binnen een seconde op je scherm: 64

Dat is niet echt hetzelfde, want bc evalueert de expressie in het geheel: hij gaat eerst 7365⁵⁴⁸ uitrekenen en dan de rest bij deling berekenen. Als je met grote getallen werkt is dat ondoenlijk en dan wil je dus een algoritme gebruiken dat slim genoeg is om die modulo-operator te gebruiken om de vereiste opslagruimte binnen de perken te houden.

Als je bijvoorbeeld in BC (999999^999999)%10 intypt, kun je je een ongeluk wachten terwijl het antwoord met een geschikt algoritme in een fractie van een seconde te berekenen is.

[MrBucket]

Ow, en nog een paar handige linkjes:
http://math.usask.ca/encryption/lessons/lesson08/page1.html
http://math.usask.ca/encryption/lessons/lesson08/page2.html
http://math.usask.ca/encryption/lessons/lesson08/page3.html <-- met name deze

--edit--
Mocht iemand het na willen rekenen, er staat een typfout onder de zin "Finally, we multiply the last expression factor by factor, reducing modulo 789 as we go...". De eerste reeks getallen moet zijn "(243)(207)(162)(588)(429)(456) mod 789" (dus 207 ipv 27)

[ Voor 37% gewijzigd door MrBucket op 03-03-2005 21:22 ]

[MrBucket]

Soultaker schreef op donderdag 03 maart 2005 @ 21:12:
[...]
Als je bijvoorbeeld in BC (999999^999999)%10 intypt, kun je je een ongeluk wachten terwijl het antwoord met een geschikt algoritme in een fractie van een seconde te berekenen is.

Klopt, dat heb ik net nog ff uitgeprobeerd

Wij hebben destijds een "powermod" functie uit moeten programmeren in BC, zodat het antwoord wel op een slimme manier wordt berekend - volgens mij ong. dezelfde aanpak als op de laatste link die ik net heb gepost. Ik heb net die powermod-implementatie nog ff uitgeprobeerd, en het werkt als een speer.

bijv.:
powermod(5436753099143653478, 132358487321373457, 178346538) //Resp. getal, macht, en modulo)
geeft 155694890, binnen een fractie van een seconde. Is toch netjes

[ Voor 4% gewijzigd door MrBucket op 03-03-2005 21:26 ]

[MrBucket]

Blijkbaar leunt de "snelle" manier van macht- en modulo rekenen op de volgende regel:

code:

(x * x) mod y = ((x mod y) * (x mod y)) mod y

Ik weet dat het klopt, ik zie alleen zo snel niet meer waarom. Wie ziet 'm wel?

[Zoijar]

(x+n*y)*(x+m*y) + k*y = x*x + x*m*y + x*n*y + n*m*y*y + k*y = x*x + (x*m+x*n+n*m*y+k)*y = x*x + 'p'*y = x*x mod y

[Soultaker]

Even voor de volledigheid; die regel is nog algemener:
(x*y) mod z = ((x mod z)*(y mod z)) mod z
(y=x is daar een speciaal geval van; ook in de algemene vorm kun je 'm vrij makkelijk bewijzen.)

De 'snelheid' zit 'm in twee dingen; ten eerste dus deze regel die ervoor zorgt dat de hoeveelheid ruimte die tussenberekeningen innemen beperkt blijft, maar net zo belangrijk is dat je het machtsverheffen op een slimme manier aanpakt (dus niet in lineaire tijd zoals in de topic start).

[ Voor 68% gewijzigd door Soultaker op 04-03-2005 01:50 ]