Kalkulator Akar Primitif

Temukan semua akar primitif dari modulus n - generator grup perkalian. Masukkan bilangan bulat positif apa pun untuk akar primitifnya, totient Euler, visualisasi grup siklik, dan pemeriksaan langkah demi langkah dengan tabel pangkat.

Gratis digunakanTidak perlu mendaftarHasil instan

Kalkulator Akar PrimitifCoba sekarang — gratis ▼

Embed Kalkulator Akar Primitif Widget

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

🔐

Diffie-Hellman

Protokol pertukaran kunci menggunakan akar primitif sebagai generator

🔏

Enkripsi ElGamal

Kriptosistem kunci publik berdasarkan logaritma diskrit

✍

Tanda Tangan Digital

Tanda tangan DSA dan Schnorr bergantung pada generator grup siklik

🎲

Angka Acak Semu

Generator kongruensial linier menggunakan properti akar primitif

📡

Kode Koreksi Kesalahan

Kode Reed-Solomon dan BCH menggunakan generator medan hingga

🧮

Teori Bilangan

Kalkulus indeks, residu kuadratik, dan masalah logaritma diskrit

Konsep dan Rumus Utama

Konsep	Rumus / Definisi	Deskripsi
Akar Primitif	\(\text{ord}_n(g) = \varphi(n)\)	Bilangan bulat g yang ordenya mod n sama dengan totient Euler
Totient Euler	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Jumlah bilangan bulat dalam [1, n] yang koprim dengan n
Kriteria Keberadaan	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Akar primitif hanya ada untuk bentuk-bentuk ini (p prima ganjil)
Jumlah Akar	\(\varphi(\varphi(n))\)	Jumlah akar primitif saat mereka ada
Uji Akar Primitif	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) untuk semua prima \(p \| \varphi(n)\)	Kondisi cukup: periksa hanya untuk faktor prima dari φ(n)
Menghasilkan Semua Akar	\(g^k \bmod n\) di mana \(\gcd(k, \varphi(n)) = 1\)	Setelah satu akar g ditemukan, semua akar lainnya mengikuti

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

Masukkan modulus n: Ketik bilangan bulat positif di bidang input, atau klik salah satu tombol contoh cepat untuk mengisi nilai secara otomatis.
Klik Cari Akar Primitif: Tekan tombol untuk menghitung semua akar primitif modulo n.
Tinjau hasilnya: Lihat jumlah, daftar lengkap akar primitif, totient Euler, orde grup, dan apakah akar primitif ada untuk n Anda.
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.
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

Apa itu akar primitif modulo n?

Akar primitif modulo n adalah bilangan bulat g sedemikian rupa sehingga pangkat g¹, g², …, g^φ(n) modulo n menghasilkan setiap bilangan bulat yang koprim dengan n tepat satu kali. Secara ekuivalen, g memiliki orde multiplikatif yang sama dengan φ(n), yang berarti g menghasilkan seluruh grup multiplikatif (Z/nZ)*.

Untuk nilai n berapa akar primitif ada?

Akar primitif ada jika dan hanya jika n adalah 1, 2, 4, p^k, atau 2p^k, di mana p adalah bilangan prima ganjil dan k adalah bilangan bulat positif. Sebagai contoh, n = 7 (prima), n = 9 (3²), dan n = 14 (2 × 7) semuanya memiliki akar primitif, tetapi n = 8, n = 12, dan n = 15 tidak.

Berapa banyak akar primitif yang dimiliki n?

Jika n memiliki akar primitif, maka jumlah akar primitif modulo n sama dengan φ(φ(n)), di mana φ adalah fungsi totient Euler. Sebagai contoh, n = 7 memiliki φ(φ(7)) = φ(6) = 2 akar primitif, yaitu 3 dan 5.

Bagaimana cara menemukan akar primitif?

Untuk menemukan akar primitif dari n: pertama hitung φ(n) dan faktorkan nilainya. Kemudian untuk setiap kandidat g yang koprim dengan n, periksa apakah g^(φ(n)/p) tidak kongruen dengan 1 mod n untuk setiap faktor prima p dari φ(n). Jika semua pemeriksaan lulus, g adalah akar primitif. Semua akar lainnya dapat ditemukan sebagai g^k mod n di mana fpb(k, φ(n)) = 1.

Mengapa akar primitif penting dalam kriptografi?

Akar primitif sangat mendasar bagi pertukaran kunci Diffie-Hellman, enkripsi ElGamal, dan algoritma tanda tangan digital. Mereka memastikan bahwa masalah logaritma diskrit menjadi sulit, yang merupakan dasar keamanan bagi protokol kriptografi ini. Akar primitif menghasilkan semua elemen grup, memaksimalkan ruang pencarian bagi penyerang.

Kutip konten, halaman, atau alat ini sebagai:

"Kalkulator Akar Primitif" di https://MiniWebtool.com/id/kalkulator-akar-primitif/ dari MiniWebtool, https://MiniWebtool.com/

oleh tim MiniWebtool. Diperbarui: 2026-04-16

API developer tersedia: Jalankan alat ini dari aplikasi, otomatisasi, atau agen Anda dengan satu permintaan HTTP JSON. Lihat dokumentasi API

Anda juga dapat mencoba Penyelesai Matematika AI GPT kami untuk menyelesaikan masalah matematika Anda melalui pertanyaan dan jawaban dalam bahasa alami.