Kandungan
Mengira akar primitif adalah kemahiran yang berguna dalam kriptografi dan teori nombor. Nombor "g" adalah akar primitif untuk nombor perdana yang diberikan "p" jika mod g mempunyai modulus pesanan p-1. Ini bermakna senarai mod "g1 mod p", "mod mod g" kepada "g (p-1) mod p" mengandungi semua bilangan bulat dari 1 hingga (p-1). Tiada algoritma yang diketahui untuk mengira akar primitif dengan cekap. Kaedah yang paling mudah adalah untuk mencuba setiap nombor yang mungkin dari 2 hingga (p-1).
Arahan
-
Pilih nombor perdana, "p", seperti lima. Nombor perdana tidak mempunyai pembahagi di luar sendiri dan satu. Sebagai contoh, empat bukan nombor perdana kerana "4/2 = 2", ia mempunyai 2 sebagai salah satu pembahaginya.
-
Kira "2 ^ n mod p" untuk setiap integer "n" dari 1 hingga (p-1). Dengan menggunakan contohnya, "p" ialah 5, kemudian hitung "2 ^ n mod 5" untuk "n" dari 1 hingga 4. Ini menghasilkan senarai:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Pastikan senarai nombor mengandungi semua jejak yang mungkin lima. Senarai 2, 4, 3 dan 1 layak, jadi 2 adalah akar primitif dengan baki 5. Jika, sebaliknya, senarai adalah 2,1,4 dan 1, yang merupakan senarai untuk 4, maka 4 tidak akan akar primitif kerana nombor 3 hilang dari senarai.
-
Ulangi langkah sebelumnya untuk semua bulat kurang daripada lima. Nombor tiga juga merupakan akar primitif rehat lima, tetapi empat tidak; maka dua dan lima adalah akar primitif untuk lima.