Kalkulator Akar Primitif

Selamat datang di Kalkulator Akar Primitif, alat online gratis yang hebat untuk menemukan semua akar primitif modulo bilangan bulat positif apa pun n. Kalkulator ini menyediakan verifikasi langkah demi langkah, tabel pangkat, dan animasi visualisasi grup siklik untuk membantu Anda memahami bagaimana akar primitif menghasilkan grup multiplikatif. Baik Anda sedang mempelajari teori bilangan, mempersiapkan ujian kriptografi, atau bekerja dengan aritmatika modular dalam pemrograman kompetitif, alat ini memberikan hasil yang instan dan akurat dengan wawasan edukatif.

Apa itu Akar Primitif?

Sebuah akar primitif modulo n adalah bilangan bulat g yang pangkatnya menghasilkan semua bilangan bulat yang koprima terhadap n. Secara formal, g adalah akar primitif mod n jika orde multiplikatif dari g modulo n sama dengan totient Euler \(\varphi(n)\). Ini berarti himpunan

berisi tepat semua \(\varphi(n)\) bilangan bulat dari 1 hingga n-1 yang koprima terhadap n. Akar primitif pada dasarnya adalah generator dari grup siklik \((\mathbb{Z}/n\mathbb{Z})^*\).

Contoh Cepat

Pertimbangkan n = 7. Karena 7 adalah prima, \(\varphi(7) = 6\). Mari kita periksa apakah g = 3 adalah akar primitif:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Pangkat-pangkat tersebut menghasilkan {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, yang merupakan semua bilangan bulat koprima terhadap 7. Jadi 3 adalah akar primitif modulo 7.

Kapan Akar Primitif Ada?

Akar primitif modulo n ada jika dan hanya jika n adalah salah satu dari bentuk berikut:

• n = 1, 2, atau 4
• n = p^k di mana p adalah bilangan prima ganjil dan k ≥ 1
• n = 2p^k di mana p adalah bilangan prima ganjil dan k ≥ 1

Sebagai contoh, akar primitif ada untuk 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, tetapi tidak untuk 8, 12, 15, 16, 20, 21, 24.

Cara Menemukan Akar Primitif

1. Masukkan modulus: Ketik bilangan bulat positif n (dari 2 hingga 100.000) ke dalam bidang input.
2. Hitung: Klik "Temukan Akar Primitif" atau tekan Enter.
3. Lihat semua akar: Lihat daftar lengkap akar primitif, beserta totient Euler dan statistiknya.
4. Pelajari tabel pangkat: Periksa bagaimana akar primitif terkecil menghasilkan semua residu koprima.
5. Visualisasikan grup siklik: Untuk moduli kecil, lihat animasi roda yang menunjukkan struktur siklik.

Berapa Banyak Akar Primitif yang Dimiliki n?

Jika akar primitif ada modulo n, jumlahnya sama dengan:

Misalnya, untuk n = 13: \(\varphi(13) = 12\) dan \(\varphi(12) = 4\), jadi ada tepat 4 akar primitif modulo 13 (yaitu 2, 6, 7, 11).

Algoritma Verifikasi

Untuk memeriksa apakah g adalah akar primitif modulo n secara efisien:

1. Hitung \(\varphi(n)\) menggunakan faktorisasi prima dari n
2. Temukan semua faktor prima yang berbeda \(p_1, p_2, \ldots, p_k\) dari \(\varphi(n)\)
3. Untuk setiap faktor prima \(p_i\), periksa: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Jika SEMUA pemeriksaan lulus, maka g adalah akar primitif

Metode ini jauh lebih cepat daripada menghitung semua pangkat dari g, karena kita hanya perlu menguji \(k\) eksponensiasi, bukan \(\varphi(n)\) eksponensiasi.

Akar Primitif dalam Kriptografi

Pertukaran Kunci Diffie-Hellman

Protokol Diffie-Hellman menggunakan bilangan prima besar p dan akar primitif g modulo p. Alice memilih rahasia a, mengirim \(g^a \bmod p\). Bob memilih rahasia b, mengirim \(g^b \bmod p\). Keduanya menghitung rahasia bersama \(g^{ab} \bmod p\). Keamanannya bergantung pada masalah logaritma diskret yang sulit secara komputasi.

Enkripsi ElGamal

ElGamal juga menggunakan akar primitif sebagai generator. Kunci publiknya adalah \((p, g, g^x \bmod p)\) di mana x bersifat pribadi. Fakta bahwa g menghasilkan semua elemen memastikan bahwa setiap pesan dapat dienkripsi.

Tanda Tangan Digital

DSA (Digital Signature Algorithm) dan skema terkait menggunakan akar primitif dalam subgrup dari \((\mathbb{Z}/p\mathbb{Z})^*\) untuk membuat dan memverifikasi tanda tangan digital.

Tabel Referensi: Akar Primitif Terkecil

Pertanyaan yang Sering Diajukan

Apa itu akar primitif modulo n?

Akar primitif modulo n adalah bilangan bulat g sedemikian rupa sehingga pangkat \(g^1, g^2, \ldots, g^{\varphi(n)}\) menghasilkan semua bilangan bulat koprima terhadap n jika diambil modulo n. Dengan kata lain, g menghasilkan seluruh grup multiplikatif \((\mathbb{Z}/n\mathbb{Z})^*\). Orde multiplikatif dari g modulo n sama dengan totient Euler \(\varphi(n)\).

Untuk nilai n berapa saja akar primitif ada?

Akar primitif ada modulo n jika dan hanya jika n adalah 1, 2, 4, p^k, atau 2p^k, di mana p adalah bilangan prima ganjil dan k ≥ 1. Sebagai contoh, akar primitif ada untuk n = 7 (prima), n = 9 (3²), n = 14 (2×7), tetapi TIDAK untuk n = 8, 12, 15, atau 16.

Berapa banyak akar primitif yang dimiliki n?

Jika akar primitif ada modulo n, jumlah akar primitif sama dengan \(\varphi(\varphi(n))\), di mana \(\varphi\) adalah fungsi totient Euler. Sebagai contoh, untuk n = 13 (prima), \(\varphi(13) = 12\) dan \(\varphi(12) = 4\), jadi ada tepat 4 akar primitif modulo 13.

Mengapa akar primitif penting dalam kriptografi?

Akar primitif sangat mendasar bagi protokol pertukaran kunci Diffie-Hellman dan sistem enkripsi ElGamal. Dalam protokol kriptografi ini, akar primitif g modulo bilangan prima besar p digunakan sebagai generator. Keamanannya bergantung pada kesulitan masalah logaritma diskret: diberikan \(g^x \bmod p\), secara komputasi sulit untuk menemukan x.

Bagaimana cara memverifikasi bahwa g adalah akar primitif modulo n?

Untuk memverifikasi g adalah akar primitif mod n: (1) Hitung \(\varphi(n)\). (2) Temukan semua faktor prima \(p_1, p_2, \ldots, p_k\) dari \(\varphi(n)\). (3) Periksa apakah \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) untuk setiap faktor prima \(p_i\). Jika semua pemeriksaan lulus, g adalah akar primitif. Ini jauh lebih cepat daripada menghitung semua pangkat dari g.

Alat Terkait