Innhold
Beregning av primitive røtter er en nyttig ferdighet i kryptografi og tallteori. Et tall "g" er en primitiv rot for et gitt hovednummer "p" dersom g mod p har ordremodul p-1. Dette betyr at listen over "g1 mod p", "g2 mod p" til "g (p-1) mod p" inneholder alle heltall fra 1 til (p-1). Det er ingen kjent algoritme for å beregne primitive røtter effektivt. Den enkleste metoden er å prøve hvert mulig tall fra 2 til (p-1).
retninger
-
Velg et primærtall, "p", som fem. Et primaltall har ingen divisors utover seg selv og en. For eksempel er fire ikke et primaltall fordi "4/2 = 2", den har 2 som en av sine divisors.
-
Beregn "2 ^ n mod p" for hvert heltall "n" fra 1 til (p-1). Ved hjelp av eksemplet er "p" 5, og deretter beregner "2 ^ n mod 5" for "n" fra 1 til 4. Dette gir listen:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Pass på at talllisten inneholder alle mulige spor av fem. Liste 2, 4, 3 og 1 kvalifiserer, så 2 er en primitiv rot med rest 5. Hvis listen i stedet var 2,1,4 og 1, som er listen for 4, ville 4 ikke være en primitiv rot fordi nummer 3 mangler fra listen.
-
Gjenta forrige trinn for alle heltall mindre enn fem. Nummer tre er også en primitiv rot av resten fem, men fire er ikke; så er to og fem de primitive røttene for fem.