Fungsi Totient Euler: Kunci Teori Bilangan dan Kriptografi

Rumus:-phi(n)-=-n-*-(1---1/p1)-*-(1---1/p2)-*-...-*-(1---1/pk)

Memahami-Fungsi-Totien-Euler

Fungsi-Totien-Euler,-dilambangkan-sebagai-φ(n)-atau-phi(n),-adalah-konsep-penting-dalam-teori-bilangan-yang-berpengaruh-dalam-berbagai-analisis-matematika-dan-algoritma-kriptografi-seperti-RSA.-Fungsi-ini-didefinisikan-sebagai-jumlah-bilangan-hingga-n-yang-koprim-(tidak-memiliki-pembagi-bersama-selain-1)-dengan-n.-Bilangan-koprim-dengan-n-adalah-bilangan-kurang-dari-n-yang-hanya-memiliki-bilangan-1-sebagai-faktor-bersama.

Rumus-Fungsi-Totien-Euler

Fungsi-ini-dihitung-dengan-rumus:

φ(n)-=-n-*-(1---1/p1)-*-(1---1/p2)-*-...-*-(1---1/pk)

di-mana-p1,-p2,-...,-pk-adalah-faktor-prima-berbeda-dari-n.-Rumus-produk-ini-berasal-dari-prinsip-inklusi-eksklusi.

Faktorisasi-Prima

Untuk-menghitung-φ(n),-menemukan-faktor-prima-yang-berbeda-sangat-penting.-Misalnya,-jika-n-adalah-12,-faktor-primanya-adalah-2-dan-3.-Ini-diterjemahkan-ke-dalam:

φ(12)-=-12-*-(1---1/2)-*-(1---1/3)
φ(12)-=-12-*-1/2-*-2/3-=-4

Ini-berarti-ada-empat-bilangan-(1,-5,-7,-dan-11)-kurang-dari-12-yang-koprim-dengan-12.

Contoh-Ilustrasi

Untuk-lebih-memahami,-mari-kita-hitung-φ-untuk-bilangan-lain,-katakanlah-30.

Faktor-prima-dari-30:-2,-3,-dan-5
φ(30)-=-30-*-(1---1/2)-*-(1---1/3)-*-(1---1/5)
φ(30)-=-30-*-1/2-*-2/3-*-4/5-=-8

Jadi,-delapan-bilangan-(1,-7,-11,-13,-17,-19,-23,-dan-29)-adalah-koprim-dengan-30.

Aplikasi-di-Dunia-Nyata

Fungsi-Totien-Euler-secara-khusus-mendasari-enkripsi-RSA,-sebuah-batu-penjuru-keamanan-digital-modern.-Dalam-algoritma-ini,-pemilihan-kunci-publik-dan-pribadi-melibatkan-perhitungan-totien.-Mengetahui-jumlah-bilangan-yang-bisa-dijadikan-kunci-untuk-enkripsi-meningkatkan-kekuatan-kriptografi.

Penggunaan-Umum

Beberapa-penggunaan-φ(n)-termasuk-kriptografi,-menyelesaikan-persamaan-Diophantine,-dan-memahami-struktur-berbagai-sistem-aljabar.-Fungsi-ini-memainkan-peran-fundamental-dalam-mempelajari-distribusi-bilangan-bulat.

Menghitung-φ(n)-dalam-JavaScript

Berikut-adalah-kode-JavaScript-untuk-ini:

const-gcd-=-(a,-b)-=>-b-===-0-?-a-:-gcd(b,-a-%-b);const-isCoprime-=-(a,-b)-=>-gcd(a,-b)-===-1;const-phi-=-(n)-=>-{--if-(n-<=-0)-return-'Input-must-be-a-positive-integer.';--let-result-=-1;--for-(let-i-=-2;-i-<-n;-i++)-{----if-(isCoprime(i,-n))-result++;--}--return-result;};

Uji-Coba-Contoh

Uji-fungsi-dengan-nilai-berikut:

Input	Hasil-yang-Diharapkan
1	1
2	1
3	2
4	2
5	4
30	8

Validasi-Data

Fungsi-memastikan-input-adalah-bilangan-bulat-positif,-mengembalikan-pesan-kesalahan-jika-tidak.

Pertanyaan-yang-Sering-Diajukan

Q:Apa-itu-bilangan-koprim-atau-bilangan-relatif-prima?
A:Dua-bilangan-adalah-koprim-jika-pembagi-terbesar-mereka-(GCD)-adalah-1,-yang-berarti-mereka-tidak-memiliki-faktor-pembagi-positif-bersama-selain-1.
Q:Bisakah-φ(n)-dihitung-untuk-bilangan-prima?
A:Ya,-untuk-bilangan-prima-p,-φ(p)-=-p---1,-karena-semua-bilangan-kurang-dari-p-adalah-koprim-dengan-p-kecuali-p-itu-sendiri.
Q:Mengapa-fungsi-totien-penting-dalam-enkripsi-RSA?
A:Fungsi-ini-membantu-menentukan-kunci-enkripsi-dan-dekripsi,-memastikan-keamanan-pesan.

Ringkasan

Fungsi-Totien-Euler-adalah-konsep-dasar-dalam-teori-bilangan,-yang-sangat-penting-untuk kriptografi modern dan teori bilangan bulat. Memahami dan menghitung φ(n) membuka pintu untuk aplikasi matematika lanjutan dan dunia nyata, mulai dari komunikasi internet yang aman hingga penelitian teoretis.

Tags: Nomor Teori, kriptografi, Matematika