Kalkulator Ring dan Lapangan

Tentang Kalkulator Ring dan Lapangan

Kalkulator Ring dan Lapangan melakukan aritmetika eksak di dalam dua keluarga struktur aljabar hingga yang paling penting: ring modular Z_n dan lapangan hingga Galois GF(p^k). Alat ini menangani penjumlahan, pengurangan, perkalian, pembagian, pangkat, invers multiplikatif, dan orde elemen, serta memperkaya setiap hasil dengan analisis struktural — unit, pembagi nol, nilpoten, idempoten, akar primitif, dan tabel Cayley lengkap dengan kode warna.

Z_n — Ring Modular

Untuk bilangan bulat positif n, ring Z_n = {0, 1, 2, …, n − 1} membawa operasi penjumlahan dan perkalian yang direduksi modulo n. Sebuah elemen a adalah unit dari Z_n (artinya memiliki invers multiplikatif) jika dan hanya jika gcd(a, n) = 1, sehingga grup multiplikatif Z_n* memiliki orde φ(n), fungsi totient Euler.

Ketika n adalah bilangan komposit, elemen a dengan gcd(a, n) > 1 adalah pembagi nol: terdapat b ≠ 0 sedemikian hingga a · b ≡ 0 (mod n). Kalkulator secara otomatis mengklasifikasikan setiap elemen ke dalam peran strukturalnya.

Mencari Invers — Algoritma Euclidean Diperluas

Jika gcd(a, n) = 1, algoritma Euclidean diperluas menghasilkan bilangan bulat x, y dengan a · x + n · y = 1, sehingga diperoleh a⁻¹ ≡ x (mod n). Alat ini menunjukkan identitas Bézout yang dihasilkan setiap kali Anda meminta invers.

Orde Multiplikatif

Untuk suatu unit a, orde multiplikatif ord(a) adalah k ≥ 1 terkecil dengan a^k ≡ 1 (mod n). Berdasarkan teorema Lagrange, ord(a) membagi φ(n). Elemen dengan ord(a) = φ(n) disebut akar primitif dan menghasilkan seluruh grup unit. Akar primitif ada tepat ketika n adalah salah satu dari 1, 2, 4, p^k, atau 2p^k untuk bilangan prima ganjil p.

GF(p^k) — Lapangan Hingga (Galois)

Untuk setiap bilangan prima p dan bilangan bulat positif k, terdapat satu lapangan yang unik (hingga isomorfisme) dengan p^k elemen: lapangan Galois GF(p^k) = 𝔽_p^k. Elemen-elemennya direpresentasikan sebagai polinomial derajat < k dengan koefisien dalam GF(p) = Z_p, dan aritmetika dilakukan modulo polinomial iredusibel f(x) derajat k.

Kalkulator menyarankan polinomial iredusibel standar untuk pasangan umum (p, k), misalnya x² + x + 1 untuk GF(4), x³ + x + 1 for GF(8), x⁴ + x + 1 untuk GF(16), dan x² + 1 untuk GF(9). Anda dapat menggantinya dengan milik Anda sendiri; alat ini memverifikasi iredusibilitas melalui uji gcd gaya Rabin.

Mengapa f(x) Harus Iredusibel?

Jika f(x) difaktorkan menjadi g(x)·h(x) dengan deg g, deg h ≥ 1, maka bayangan g(x) dan h(x) dalam hasil bagi tersebut akan menjadi pembagi nol bukan nol — hasil bagi tersebut hanya akan menjadi ring, bukan lapangan. Iredusibilitas adalah syarat tepat agar GF(p)[x] / ⟨f(x)⟩ menjadi lapangan.

Aritmetika Polinomial dan Invers

Penjumlahan dilakukan per koefisien mod p. Perkalian adalah perkalian polinomial biasa yang diikuti oleh reduksi: diberikan a(x)·b(x), bagi dengan f(x) dan ambil sisanya r(x), dengan deg r < k. Invers multiplikatif berasal dari algoritma Euclidean diperluas di atas ring polinomial GF(p)[x]: temukan u(x) dan v(x) dengan u(x)·a(x) + v(x)·f(x) = 1.

Ring vs Lapangan Sekilas

Cara Menggunakan Kalkulator

1. Pilih struktur — Z_n untuk bilangan bulat modular, atau GF(p^k) untuk lapangan perluasan. Formulir akan menyesuaikan untuk hanya menampilkan bidang yang relevan.
2. Masukkan parameter — modulus n, atau bilangan prima p dan derajat k. Untuk GF(p^k) Anda dapat mengosongkan polinomial iredusibel dan kalkulator akan mengisinya dengan yang standar.
3. Pilih operasi — tujuh pilihan mencakup semua tugas umum: tambah, kurang, kali, bagi, angkat ke pangkat, hitung invers, atau cari orde multiplikatif.
4. Berikan operan — bilangan bulat untuk Z_n, atau polinomial seperti x^2 + x + 1 untuk GF(p^k). Bentuk daftar koefisien (1,1,1) juga berfungsi.
5. Klik Hitung. Anda akan melihat hasilnya bersama dengan pengerjaan langkah demi langkah, klasifikasi setiap elemen, dan tabel Cayley jika struktur cukup kecil untuk ditampilkan.

Contoh Pengerjaan — GF(8) = GF(2³)

Ambil f(x) = x³ + x + 1 (iredusibel di atas GF(2)). Kalikan a(x) = x + 1 dengan b(x) = x²:

Grup multiplikatif GF(8)* adalah siklik dengan orde 7, dan elemen x adalah elemen primitif karena x^k melewati setiap elemen bukan nol saat k = 1, 2, …, 7.

Mengapa Ini Penting

• Kriptografi — AES menggunakan aritmetika dalam GF(2⁸) dengan f(x) = x⁸ + x⁴ + x³ + x + 1. Kriptografi kurva eliptik dan masalah logaritma diskrit berada di dalam GF(p) dan GF(p^k).
• Kode koreksi kesalahan — Kode Reed-Solomon dan BCH (digunakan dalam CD, kode QR, DVB-T, wahana antariksa Voyager) dibangun dari polinomial di atas GF(2⁸) atau GF(2^m).
• Desain kombinatorial — lapangan hingga membangun matriks Hadamard, bidang proyektif, dan bujur sangkar Latin yang digunakan dalam eksperimen statistik.
• Aljabar komputer — algoritma faktorisasi dan reduksi modular (Berlekamp, Cantor-Zassenhaus) dirumuskan di atas lapangan hingga.
• Pedagogi teori bilangan — Z_n, akar primitif, dan residu kuadrat adalah pintu gerbang menuju aritmetika modular, RSA, dan Diffie-Hellman.

Pertanyaan yang Sering Diajukan

Kapan Z_n menjadi lapangan?

Ring modular Z_n adalah lapangan jika dan hanya jika n adalah bilangan prima. Dalam hal ini setiap elemen bukan nol adalah unit karena gcd(a, n) = 1 untuk setiap 0 < a < n. Ketika n adalah bilangan komposit, Z_n memiliki pembagi nol dan hanya merupakan ring, bukan domain.

Apa itu GF(p^k)?

GF(p^k), juga disebut lapangan Galois orde p^k, adalah lapangan hingga yang unik dengan p^k elemen. Elemen-elemennya direpresentasikan sebagai polinomial derajat kurang dari k di atas GF(p), dengan aritmetika dilakukan modulo polinomial iredusibel f(x) derajat k. Untuk setiap prima p dan bilangan bulat positif k, tepat ada satu lapangan seperti itu hingga isomorfisme.

Apa itu polinomial iredusibel dan mengapa itu diperlukan?

Polinomial iredusibel di atas GF(p) adalah polinomial yang tidak dapat difaktorkan menjadi polinomial berderajat lebih rendah dengan koefisien di GF(p). Reduksi modulo polinomial iredusibel derajat k menghasilkan ring hasil bagi yang merupakan lapangan. Tanpa iredusibilitas, hasil bagi tersebut memiliki pembagi nol dan bukan merupakan lapangan.

Apa itu pembagi nol?

Elemen bukan nol a dalam suatu ring disebut pembagi nol jika terdapat elemen bukan nol b sedemikian hingga a · b = 0. Dalam Z_n, pembagi nol adalah tepat elemen-elemen a dengan gcd(a, n) lebih besar dari 1. Lapangan tidak memiliki pembagi nol, itulah sebabnya Z_n adalah lapangan tepat ketika n adalah bilangan prima.

Apa itu orde multiplikatif suatu elemen?

Orde multiplikatif dari suatu unit a adalah bilangan bulat positif terkecil k sedemikian hingga a^k sama dengan 1 dalam ring tersebut. Berdasarkan teorema Lagrange, orde ini membagi ukuran grup multiplikatif: φ(n) untuk Z_n, atau p^k − 1 untuk GF(p^k). Elemen yang ordenya sama dengan ukuran grup penuh disebut akar primitif atau generator.

Apa fungsi elemen primitif dari GF(p^k)?

Elemen primitif adalah generator dari grup multiplikatif GF(p^k)*, yang berbentuk siklik dengan orde p^k − 1. Setiap elemen lapangan yang bukan nol dapat ditulis sebagai pangkat dari elemen primitif, yang memungkinkan logaritma diskrit, kode BCH, dan koreksi kesalahan Reed-Solomon mungkin dilakukan.

Bacaan Lebih Lanjut

• Aritmetika modular — Wikipedia
• Lapangan hingga — Wikipedia
• Akar primitif modulo n — Wikipedia
• Fungsi totient Euler — Wikipedia
• Polinomial iredusibel — Wikipedia