Modulo rekenen

[tommie2]

Hallo,

ik zit met een probleem bij het oplossen van volgende oefening:

Een groot aantal rekruten meldt zich aan in een opleidingscentrum van het leger. De commandant van het opleidingscentrum slaagt er maar niet in zijn rekruten in een rechthoekige formatie op te delen. Als hij ze in rijen van 7 man achter elkaar plaatst blijven er 2 over. Plaatst hij ze in rijen van 9 dan blijven er 5 over en plaatst hij ze in rijen van 11 dan blijven er 10 over.
Kan je hem helpen om zijn rekruten in een mooie rechthoekige formatie op te stellen? (Het aantal rekruten kan niet meer dan 1000 bedragen)



En dit is dan de oplossing:

n = aantal rekruten
n = 2 mod 7 (1)
n = 5 mod 9 (2)
n = 10 mod 11 (3)

(1) n = 7k + 2
invullen in (2):
7k + 2 = 5 mod 9
7k = 3 mod 9
k = 12 mod 9 (Hier doet men dus x4, maar waarom en hoe is het mogelijk dat die 7 uit het linkerlid dan verdwijnt???)
k = 3 mod 9
dus k = 9l + 3 en n = 7(9l + 3) + 2 = 63l + 23

invullen in (3):
63l + 23 = 10 mod 11
63l = -13 mod 11
63l = -2 mod 11
8l = -2 mod 11 (Hier verandert 63 naar 8, maar waarom???)
l = -14 mod 11 (Hier verdwijnt dan de 8 in het linkerlid en wordt er vermenigvuldigt met 7, opnieuw waarom???)
l = 8 mod 11 (Vanwaar plots die 8???)
dus l = 11m + 8 en n = 63(11m + 8) + 23 = 693m + 527

n < 1000 dus n = 527 want 527 + 1x693 > 1000
527 = 17 x 31 rekruten


Kan iemand mij helpen bij de vragen die in het vet staan??
bedankt op voorhand in ieder geval

[mathfreak]

tommie2 schreef op 24-05-2007 @ 13:47 :
Hallo,

ik zit met een probleem bij het oplossen van volgende oefening:

Een groot aantal rekruten meldt zich aan in een opleidingscentrum van het leger. De commandant van het opleidingscentrum slaagt er maar niet in zijn rekruten in een rechthoekige formatie op te delen. Als hij ze in rijen van 7 man achter elkaar plaatst blijven er 2 over. Plaatst hij ze in rijen van 9 dan blijven er 5 over en plaatst hij ze in rijen van 11 dan blijven er 10 over.
Kan je hem helpen om zijn rekruten in een mooie rechthoekige formatie op te stellen? (Het aantal rekruten kan niet meer dan 1000 bedragen)



En dit is dan de oplossing:

n = aantal rekruten
n = 2 mod 7 (1)
n = 5 mod 9 (2)
n = 10 mod 11 (3)

(1) n = 7k + 2
invullen in (2):
7k + 2 = 5 mod 9
7k = 3 mod 9
k = 12 mod 9 (Hier doet men dus x4, maar waarom en hoe is het mogelijk dat die 7 uit het linkerlid dan verdwijnt???)
k = 3 mod 9
dus k = 9l + 3 en n = 7(9l + 3) + 2 = 63l + 23

invullen in (3):
63l + 23 = 10 mod 11
63l = -13 mod 11
63l = -2 mod 11
8l = -2 mod 11 (Hier verandert 63 naar 8, maar waarom???)
l = -14 mod 11 (Hier verdwijnt dan de 8 in het linkerlid en wordt er vermenigvuldigd met 7, opnieuw waarom???)
l = 8 mod 11 (Vanwaar plots die 8???)
dus l = 11m + 8 en n = 63(11m + 8) + 23 = 693m + 527

n < 1000 dus n = 527 want 527 + 1x693 > 1000
527 = 17 x 31 rekruten


Kan iemand mij helpen bij de vragen die in het vet staan??
bedankt op voorhand in ieder geval

Eerst maar de vergelijking 7*k=3 mod 9. Als je links en rechts met 4 vermenigvuldigt krijg je: 28*k=12 mod 9. Nu geldt: 28=1 mod 9, dus 28*k mod 9=(1*k) mod 9 = k mod 9, dus 28*k=12 mod 9 is modulo 9 te herleiden tot k=12 mod 9.
Dan nu de vergelijking 63*l=-2 mod 11. Er geldt: 63=8 mod 11, dus 63*l mod 11=8*l mod 11, dus 63*l=-2 mod 11 is modulo 11 te herleiden tot 8*l=-2 mod 11. Als je links en rechts met 7 vermenigvuldigt krijg je: 56*l=-14 mod 11. Nu geldt: 56=1 mod 11, dus 56*l mod 11=(1*l) mod 11=l mod 11, dus 56*l=-14 mod 11 is modulo 11 te herleiden tot l=-14 mod 11. Er geldt: -22=-=0 mod 11 en -14=-22+8, dus -14 mod 11=(-22+8) mod 11=-22 mod 11+8 mod 11=0 mod 11+8 mod 11=(0+8) mod 11=8 mod 11, dus l=-14 mod 11 is modulo 11 te herleiden tot l=8 mod 11.

[tommie2]

bedankt voor uw reactie, ik denk dat ik het begrijp nu
Dit zal me goed helpen op het examen van dinsdag

[mathfreak]

tommie2 schreef op 25-05-2007 @ 14:13 :
bedankt voor uw reactie, ik denk dat ik het begrijp nu

Graag gedaan.

tommie2 schreef op 25-05-2007 @ 14:13 :
Dit zal me goed helpen op het examen van dinsdag

Bij deze alvast veel succes toegewenst aanstaande dinsdag.

[tommie2]

Ik heb een nieuwe vraag omtrent modulorekenen...

Het is de bedoeling dat ik dit bereken:

D = 1740^18825 mod 100141

Kan iemand me hierbij helpen? Ik weet wel hoe je dit moet oplossen met kleinere getallen, maar met zo'n grote getallen geraak ik er maar niet aan uit

Met vriendelijke groeten

[mathfreak]

tommie2 schreef op 26-05-2007 @ 14:46 :
Ik heb een nieuwe vraag omtrent modulorekenen...

Het is de bedoeling dat ik dit bereken:

D = 1740^18825 mod 100141

Kan iemand me hierbij helpen? Ik weet wel hoe je dit moet oplossen met kleinere getallen, maar met zo'n grote getallen geraak ik er maar niet aan uit

Met vriendelijke groeten

Bepaal eerst p=1740²⁵ mod 100141, dan geldt: D=1740^25*753 mod 100141=p⁷⁵³ mod 100141=(p⁷⁰⁰*p⁵⁰*p³) mod 100141.

[tommie2]

pff het lukt me maar niet
Het gaat over RSA-codering...

We coderen hetvolgende bericht: "Deze tekst is beveiligd met RSA." met publieke sleutel 100141 en 12345. We kunnen als bloklengte 5 nemen want elk blokje van 5 cijfers vormt een getal dat kleiner is dan 100141.

1) We zetten het bericht om naar een zeer groot getal:
B = 04052605002005111920000919000205220509120907040013052000181901

2) We delen B op in blokjes van lengte 5 van achteraan te beginnen:
B = 04 05260 50020 05111 92000 09190 00205 22050 91209 07040 01305 20001 81901

3) We vervangen elk blokje B van lengte 5 door C = B^12345 mod 100141:
C = 94029 86153 ......

Hier zie je dus de eerste twee blokjes. Ik heb de oplossing maar weet echt niet hoe ik eraan moet komen. Ik heb al voortdurend geprobeerd en het neemt erg veel tijd in beslag zonder dat ik het juiste resultaat bekom
De oefening op RSA gaat nog verder, maar die typ ik hier niet helemaal over omdat ik denk dat dit niet echt nodig is voor mijn probleem.

Met vriendelijke groeten....

[mathfreak]

tommie2 schreef op 28-05-2007 @ 19:38 :
pff het lukt me maar niet
Het gaat over RSA-codering...

We coderen hetvolgende bericht: "Deze tekst is beveiligd met RSA." met publieke sleutel 100141 en 12345. We kunnen als bloklengte 5 nemen want elk blokje van 5 cijfers vormt een getal dat kleiner is dan 100141.

1) We zetten het bericht om naar een zeer groot getal:
B = 04052605002005111920000919000205220509120907040013052000181901

2) We delen B op in blokjes van lengte 5 van achteraan te beginnen:
B = 04 05260 50020 05111 92000 09190 00205 22050 91209 07040 01305 20001 81901

3) We vervangen elk blokje B van lengte 5 door C = B^12345 mod 100141:
C = 94029 86153 ......

Hier zie je dus de eerste twee blokjes. Ik heb de oplossing maar weet echt niet hoe ik eraan moet komen. Ik heb al voortdurend geprobeerd en het neemt erg veel tijd in beslag zonder dat ik het juiste resultaat bekom
De oefening op RSA gaat nog verder, maar die typ ik hier niet helemaal over omdat ik denk dat dit niet echt nodig is voor mijn probleem.

Met vriendelijke groeten....

Zie voor een beschrijving van de berekeningsmethode http://nl.wikipedia.org/wiki/RSA_%28Cryptografie%29