WisFaq!

Kleinste primitieve wortel modulo

Ik ben bezig met het bestuderen van de Diffie-Hellman sleuteluitwisseling. Hier kom je de term primitieve wortel tegen. Nou heb ik twee voorbeelden waarbij de kleinste primitieve wortel wordt gevraagd namelijk:

• wat is de kleinste pimitieve wortel van de vergelijking
  9^m = 1 mod 11.
• En hoe laat je zijn dat bijv. 5 een primitieve wortel is van modulo 23.

Ik zou heel graag willen weten hoe je dit moet bepalen.

Mike
20-1-2003

Antwoord

Beste Mike,

Je eerste vraag is me niet helemaal duidelijk. Ik denk dat je wilt weten wat de orde van 9 is modulo 11.
Je wilt dan weten wat de kleinste waarde van m is waarvoor:
g^mº1 mod 11

Als je alle machten van 9 tot en met de macht 10 uitrekent modulo 11 zul je vinden dat:
9¹ º 9 mod 11
9² º 4 mod 11
9³ º 3 mod 11
9⁴ º 5 mod 11
9⁵ º 1 mod 11
9⁶ º 9 mod 11
9⁷ º 4 mod 11
9⁸ º 3 mod 11
9⁹ º 5 mod 11
9¹⁰ º 1 mod 11

Dus de kleinste waarde van m = 5, en dus is 9 geen primitieve wortel modulo 11,

In je tweede vraag denk ik dat je het beste zo'n zelfde rijtje kunt maken voor de machten van 5 modulo 23. Dan zal de kleinste macht waarvoor het º1 is, 22 moeten zijn omdat f(23)=22

Veel succes!

gm
27-1-2003