Euler - cryptografie

hallo, we maken een werkstuk over cryptografie, een vraag daarbij is, bewijs de stelling van euler, we weten niet hoe dit moet, we hebben als aanwijzingen:
1) Maak een lijst van alle getallen tussen 1 en m die geen factor gemeen hebben met m (er zijn er f (m)). Dit is lijst A.
2) Vermenigvuldig al de getallen in lijst A met a. Dit geeft lijst B.
3) Observeer dat modulo m lijst B op de volgorde na hetzelfde is als lijst A.
4) Modulo m is dus het product van alle elementen in de eerste lijst gelijk aan dat van de tweede lijst.
5) Deel aan beide kanten dezelfde factoren weg.
6) Schrijf op wat je overhoudt. Dat is precies wat bewezen moest worden.
kunnen jullie ons helpen, alvast bedankt Pieter en joris.

joris
Leerling bovenbouw havo-vwo - dinsdag 20 januari 2004

Antwoord

Hoi,

De stelling van Euler is een uitbreiding van de kleine stelling van Fermat. De Euler-functie f(m) geeft het aantal getallen dat kleiner is dan en onderling ondeelbaar met m. Je kan die f(m) makkelijk berekenen als je de priemdelers van m kent... (op WisFAQ zal je die formule zonder twijfel vinden... zoek maar eens )

Ik begrijp dat je voor je opdracht een willekeurige m moet kiezen en die stappen dan moet doorlopen. Als je m priem neemt, zeur je een beetje. Neem dus m=2.3³.7=378 bijvoorbeeld. Je zou in A en B 108 elementen moeten vinden. Om 4 te snappen moet je bedenken dat B 108 verschillende elementen bevat die onderling ondeelbaar zijn met m en omdat er zo maar 108 bestaan dus alle elementen van A. Het product van alle elementen in A noem je p. Het product van alle elementen in B is dan a^f(m).p, maar dat is precies gelijk aan het product van alle elementen van A. Daarom is a^f(m).p=p (mod m). Als je nu nog een goede reden vindt om die p te mogen wegdelen, dan heb je ook stap 5 gedaan. Het resultaat van al dit is dus: a^f(m)=1 (mod m).

Wat we hierboven deden voor een concrete m, kan je veralgemenen, zodat het voor alle m geldt. Ik weet niet zeker of dat de bedoeling van je opdracht was...

Zoek jij eens verder wat dit toch wonderlijke resultaat met cryptografie te maken heeft?

Groetjes,
Johan

andros
dinsdag 20 januari 2004

©2001-2024 WisFaq