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 generator subgrup berorde prima besar q, dengan q membagi p−1, 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 subgrup siklik besar diyakini sulit. Demikian pula, enkripsi ElGamal dan Algoritma Tanda Tangan Digital (DSA) bergantung pada kesulitan masalah logaritma diskrit dalam subgrup tersebut.

FAQ

Operasi matematika tingkat lanjut:

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