Sisu
Primitiivsete juurte arvutamine on kasulikud oskused krüptograafias ja numbriteoorias. Arv "g" on antud prime numbri "p" primitiivne juur, kui g mod p on järjestusmoodul p-1. See tähendab, et "g1 mod p", "g2 mod p" kuni "g (p-1) mod p" loend sisaldab kõiki täisarvusid vahemikus 1 kuni (p-1). Tuntud algoritmi ei ole primitiivsete juurte tõhusaks arvutamiseks olemas. Kõige lihtsam on proovida iga võimalikku numbrit vahemikus 2 kuni (p-1).
Juhised
-
Valige esmane number, p, nagu viis. Esialgsel numbril ei ole jagajaid väljaspool ennast ja ühte. Näiteks neli ei ole esmane number, sest "4/2 = 2", sellel on 2 jagajana.
-
Arvutage "2 ^ n mod p" iga täisarvu "n" jaoks 1 kuni (p-1). Näite abil on "p" 5, seejärel arvuta "2 ^ n mod 5" väärtuseks "n" 1 kuni 4. See loob loendi:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Veenduge, et numbrite loend sisaldab kõiki võimalikke viie jälgi. Nimekiri 2, 4, 3 ja 1 kvalifitseerub, nii et 2 on primitiivne juur koos ülejäänud 5-ga. Kui selle asemel oli nimekiri 2,1,4 ja 1, mis on 4-ndate nimekiri, siis 4 ei oleks primitiivne juur, sest loendist puudub number 3.
-
Korrake eelmist sammu kõigi täisarvude puhul, mis on väiksemad kui viis. Kolmas number on ka ülejäänud viie primitiivne juur, kuid neli ei ole; siis kaks ja viis on primitiivsed juured viieks.