Kalkulator Akar Primitif

Tentang Kalkulator Akar Primitif

Kalkulator Akar Primitif menemukan semua akar primitif dari modulus n yang diberikan — bilangan bulat g yang pangkatnya \(g^1, g^2, \ldots, g^{\varphi(n)}\) menghasilkan setiap elemen dari grup multiplikatif \((\mathbb{Z}/n\mathbb{Z})^*\). Masukkan bilangan bulat positif apa pun untuk melihat semua akar primitif secara instan, totient Euler \(\varphi(n)\), visualisasi grup siklik interaktif, tabel pangkat, dan verifikasi langkah demi langkah dari akar primitif terkecil.

Aplikasi Akar Primitif

Konsep dan Rumus Utama

Memahami Akar Primitif

Sebuah akar primitif modulo n adalah bilangan bulat g sedemikian rupa sehingga \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) sama dengan himpunan semua bilangan bulat dari 1 hingga n−1 yang koprim dengan n. Dalam istilah teori grup, g adalah generator dari grup multiplikatif siklik \((\mathbb{Z}/n\mathbb{Z})^*\). Sebagai contoh, 3 adalah akar primitif mod 7 karena pangkat 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) menghasilkan setiap elemen dari {1, 2, 3, 4, 5, 6}.

Kapan Akar Primitif Ada?

Hasil klasik dalam teori bilangan (dibuktikan oleh Gauss) menyatakan bahwa akar primitif modulo n ada jika dan hanya jika n adalah salah satu dari: 1, 2, 4, p^k, atau 2p^k, di mana p adalah bilangan prima ganjil dan k ≥ 1. Untuk nilai n lainnya, grup \((\mathbb{Z}/n\mathbb{Z})^*\) tidak siklik — grup ini terurai sebagai produk langsung dari grup siklik berdasarkan Teorema Sisa Tiongkok — sehingga tidak ada elemen tunggal yang dapat menghasilkan seluruh grup. Misalnya, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) tidak memiliki akar primitif.

Cara Menemukan Akar Primitif Secara Efisien

Algoritma standar bekerja dalam dua fase. Fase 1: temukan akar primitif terkecil dengan percobaan. Untuk setiap kandidat g mulai dari 2, hitung \(g^{\varphi(n)/p} \bmod n\) untuk setiap faktor prima p dari \(\varphi(n)\). Jika tidak ada yang sama dengan 1, maka g adalah akar primitif. Dalam praktiknya, akar primitif terkecil biasanya bernilai kecil — diperkirakan sebesar \(O(n^\epsilon)\) untuk setiap \(\epsilon > 0\). Fase 2: setelah satu akar primitif g diketahui, semua akar primitif lainnya adalah \(g^k \bmod n\) di mana \(\gcd(k, \varphi(n)) = 1\), memberikan tepat \(\varphi(\varphi(n))\) akar primitif secara total.

Cara Menggunakan Kalkulator Akar Primitif

1. Masukkan modulus n: Ketik bilangan bulat positif di bidang input, atau klik salah satu tombol contoh cepat untuk mengisi nilai secara otomatis.
2. Klik Cari Akar Primitif: Tekan tombol untuk menghitung semua akar primitif modulo n.
3. Tinjau hasilnya: Lihat jumlah, daftar lengkap akar primitif, totient Euler, orde grup, dan apakah akar primitif ada untuk n Anda.
4. Jelajahi visualisasi: Untuk n ≤ 100, roda grup siklik interaktif menunjukkan bagaimana setiap akar primitif menghasilkan seluruh grup melalui pangkat-pangkatnya. Klik pada chip akar mana pun untuk melihat siklusnya dianimasikan pada roda.
5. Pelajari tabel pangkat: Kisi menunjukkan g^k mod n untuk k = 1, 2, …, φ(n), dengan akar primitif dan elemen identitas disorot dalam warna yang berbeda.

Akar Primitif dalam Kriptografi

Akar primitif memainkan peran sentral dalam kriptografi modern. Dalam pertukaran kunci Diffie-Hellman, dua pihak menyepakati bilangan prima besar p dan akar primitif g mod p, lalu bertukar kunci publik g^a mod p dan g^b mod p. Rahasia bersama g^ab mod p secara komputasi tidak layak untuk ditentukan oleh penguping, karena menghitung logaritma diskrit dalam grup siklik besar diyakini sulit. Demikian pula, enkripsi ElGamal dan Algoritma Tanda Tangan Digital (DSA) keduanya bergantung pada kesulitan masalah logaritma diskrit dalam grup yang dihasilkan oleh akar primitif.

FAQ

Alat terkait lainnya:

Operasi matematika tingkat lanjut:

• Kalkulator Antilog
• Kalkulator Fungsi Beta
• Kalkulator Koefisien Binomial
• Kalkulator Distribusi Binomial
• Kalkulator Bitwise
• Kalkulator Teorema Limit Tengah
• Kalkulator Kombinasi
• Kalkulator Fungsi Kesalahan Pelengkap
• Kalkulator Bilangan Kompleks Unggulan
• Kalkulator Entropi
• Kalkulator fungsi kesalahan
• Kalkulator Peluruhan Eksponensial
• Kalkulator Pertumbuhan Eksponensial Presisi Tinggi
• Kalkulator Integral Eksponensial
• kalkulator-eksponen-presisi-tinggi
• Kalkulator Faktorial
• Kalkulator Fungsi Gamma
• Kalkulator Rasio Emas
• Kalkulator Setengah Hidup
• Kalkulator Pertumbuhan Persentase
• Kalkulator Permutasi
• Kalkulator Distribusi Poisson
• Kalkulator Akar Polinomial dengan Langkah-Langkah Terperinci
• Kalkulator Probabilitas
• Kalkulator Distribusi Probabilitas
• Kalkulator Proporsi
• Kalkulator Rumus Kuadrat
• Kalkulator Ilmiah
• Kalkulator Notasi Ilmiah Unggulan
• Kalkulator Angka Penting Baru
• Kalkulator Jumlah Kubik
• Kalkulator Jumlah Angka Berurutan
• Kalkulator Jumlah Kuadrat
• Generator Tabel Kebenaran
• Kalkulator Teori Himpunan
• Generator Diagram Venn (3 Himpunan)
• Kalkulator Teorema Sisa Cina
• Kalkulator Fungsi Totien Euler
• Kalkulator Algoritma Euklides Diperluas
• Kalkulator Invers Multiplikatif Modular
• Kalkulator Pecahan Lanjutan
• Kalkulator Jalur Terpendek Dijkstra
• Kalkulator Pohon Rentang Minimum
• Validator Urutan Derajat Graf
• Kalkulator Derangement Subfaktorial
• Kalkulator Bilangan Stirling
• Kalkulator Prinsip Sarang Merpati
• Kalkulator Distribusi Stasioner Rantai Markov
• Kalkulator Pembulatan Baru
• Kalkulator Distribusi Binomial Negatif Baru
• Kalkulator Permutasi dengan Pengulangan Baru
• Kalkulator Eksponensial Modular Baru
• Kalkulator Akar Primitif
• Penyederhana Aljabar Boolean Baru
• Pemecah Peta Karnaugh (K-Map) Baru
• Kalkulator Pewarnaan Graf Baru
• Kalkulator Pengurutan Topologi Baru
• Kalkulator Matriks Ketetanggaan Baru
• Kalkulator Inklusi-Eksklusi Baru
• Pemecah Pemrograman Linear Baru
• Pemecah Masalah Penjual Keliling (TSP) Baru
• Pemeriksa Jalur Hamilton Baru
• Pemeriksa Grafik Planar Baru
• Kalkulator Aliran Jaringan (Aliran Maksimum) Baru
• Pemecah Masalah Pernikahan Stabil Baru
• Kalkulator Orde Teori Grup Baru
• Kalkulator Ring dan Lapangan Baru