Lineaire combinatie en greatest common divisor
Door Ruud Verbij, 20 jaar geleden, 3.968x bekeken
Voor het gebruiken van RSA heb je de modulo inverse van een bepaald getal nodig in een bepaalde modulo!
Daar kon ik niet heel snel een scriptje voor vinden, dus heb ik het zelf maar gemaakt. Het maakt gebruik van het algoritme van Euclides en het uitgebreide algoritme van Euclides ('weer naar boven gaan').
Voorbeeld: http://www.ruudverbij.nl/testmap/lincomb.php
Gesponsorde koppelingen
PHP script bestanden
Er zijn 9 reacties op 'Lineaire combinatie en greatest common divisor'
0 
-0 
-0
Stel, je hebt getallen A en B.
En je wilt weten het hun grootste gemene deler (ggd) is (dat wil zeggen, je kan niet beide getallen delen door een groter getal dan de ggd).
Dan voer je ze in, en zoek je de ggd (in het engels gcd).
Ook kun je dan kijken, hoe je de getallen A en B kunt schrijven zodat:
ggd = x*A + y*B. Dit kan interessant zijn als je je bezig houdt met bijvoorbeeld RSA.
Een voorbeeldje:
A = 19 en B = 5, dan geldt:
De grootste gemene deler: 1 (ze zijn 'relatief priem')
Nu blijkt dat:
1 = -1 * 19 + 4 * 5, dit is de lineaire combinatie van 19 en 5.
De modulo inverse van 5, modulo 19 gezien, is 4!
Ik hoop dat je er iets aan hebt!
En je wilt weten het hun grootste gemene deler (ggd) is (dat wil zeggen, je kan niet beide getallen delen door een groter getal dan de ggd).
Dan voer je ze in, en zoek je de ggd (in het engels gcd).
Ook kun je dan kijken, hoe je de getallen A en B kunt schrijven zodat:
ggd = x*A + y*B. Dit kan interessant zijn als je je bezig houdt met bijvoorbeeld RSA.
Een voorbeeldje:
A = 19 en B = 5, dan geldt:
De grootste gemene deler: 1 (ze zijn 'relatief priem')
Nu blijkt dat:
1 = -1 * 19 + 4 * 5, dit is de lineaire combinatie van 19 en 5.
De modulo inverse van 5, modulo 19 gezien, is 4!
Ik hoop dat je er iets aan hebt!
0 -0
-0
Je weet dat het Engelse woord voor deler divider is en niet dealer wat handelaar betekend?
Verder zegt het wiskundige deel hiervan mij niks maar denk dat is denk ik gewoon een gebrek aan wiskundige kennis.
Verder zegt het wiskundige deel hiervan mij niks maar denk dat is denk ik gewoon een gebrek aan wiskundige kennis.
0 -0
-0
Kun je even de tutorial aanpassen, nu staat er PHP versie 3 terwijl dit 5 moet zijn:P, overigens is PHP3 niet eens OOP :)
0 -0
-0
@Gijs: woeps! inderdaad, het is vernaderd
@Jurgen: done, dankjewel, weet ook niet hoe daar een 3 was beland!
@Jurgen: done, dankjewel, weet ook niet hoe daar een 3 was beland!
0 -0
-0
Ik snap d'r de ballen niet van... Maar dat zal wel aan mijn wiskundekennis liggen. Wat wil zo'n lineaire combinatie nou eigenlijk zeggen?
0 -0
-0
@Djemo
BRON: Wikipedia:
Bij het vereenvoudigen van een breuk is het handig om de ggd te bepalen. Het getal boven en onder de breuk kan dan door de g.g.d worden gedeeld en zo verkrijgt men direct de grootst mogelijke vereenvoudiging. De breuk 24/102 wordt aldus vereenvoudigd tot 4/17. Een breuk van twee relatief prieme getallen kan niet vereenvoudigd worden.
Deze wiki
Deze wiki
0 -0
-0
Oooh, dus het is gewoon snel vereenvoudigen van breuken? Zeg dat dan :-P.
0 -0
-0
Dat is niet het oorspronkelijke doel van het script; maar dat kan er zeker ook mee gedaan worden!
Om te reageren heb je een account nodig en je moet ingelogd zijn.
PHP hulp
0 seconden vanaf nu