WisFaq!

Congruentierekenen

Beste,

tijdens het studeren van wiskunde kwam ik een opgave zoals deze: 14x³³⁷=1 mod 87 tegen mits gebruik van de kleine stelling van fermat kon ik deze vereenvoudigen tot:
14x⁷⁹ = 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: 36x⁸¹ = 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 x⁷⁹=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·x⁸¹ is altijd even mod 100, dus nooit 1.

kphart
22-1-2008