WisFaq!

\require{AMSmath} geprint op donderdag 28 maart 2024

Congruentierekenen

Beste,

tijdens het studeren van wiskunde kwam ik een opgave zoals deze: 14x337=1 mod 87 tegen mits gebruik van de kleine stelling van fermat kon ik deze vereenvoudigen tot:
14x79 = 1 mod 87.

Hier zit ik echter vast, hoe kan ik de x-waarde bepalen?

een vergelijkbare opgave waar ik op hetzelfde probleem stuit is deze: 36x81 = 1 mod (100)

Kan iemand een zet in de goede richting geven?

Alvast bedankt,

Koen

koen
21-1-2008

Antwoord

In het algemeen is dit moeilijk, daarom is er ook een cryptosysteem op gebaseerd. In dit geval kun je het probleem omwerken tot x79=a, waarbij a·14=1 (mod 87). Vervolgens kun je er nog, wegens de kleine Fermat, nog x-8=a van maken.
De tweede vergelijking lijkt me onoplosbaar: 36·x81 is altijd even mod 100, dus nooit 1.

kphart
22-1-2008


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#54028 - Cryptografie - Student Hoger Onderwijs België