0Pricing
Cryptology Academy · Pelajaran

GCD, Totien Euler, dan Pengantar Teori Bilangan

Terapkan GCD dan fungsi totien Euler pada masalah kriptografi nyata.

GCD, Totien Euler, dan Pengantar Teori Bilangan adalah pelajaran Cryptology Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Cryptology Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Cryptology Academy mencakup 4 pelajaran total.

Selamat Datang

GCD dan fungsi totien Euler adalah alat penting dalam RSA dan banyak sistem kunci publik lainnya. Mari kuasai keduanya melalui contoh-contoh.

Pembagi Persekutuan Terbesar (GCD)

GCD(a, b) adalah bilangan bulat terbesar yang membagi a dan b tanpa sisa. GCD(12, 8) = 4. Jika GCD(a, m) = 1, kita mengatakan bahwa a dan m saling prima atau relatif prima.

Algoritme Euclidean

GCD(a, b) = GCD(b, a mod b), dengan kasus dasar GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Algoritme Euclidean Diperluas

Versi yang diperluas menemukan bilangan bulat x, y sedemikian rupa sehingga ax + by = GCD(a,b). Ketika GCD(a,m)=1, x adalah invers modular dari a modulo m. Beginilah RSA menghitung kunci privat.

Fungsi Totien Euler φ(n)

φ(n) menghitung banyaknya bilangan bulat dari 1 hingga n yang relatif prima terhadap n. φ(10) = 4 karena {1, 3, 7, 9} relatif prima terhadap 10. φ(p) = p-1 untuk setiap bilangan prima p.

Totien dari Hasil Kali

Untuk RSA: n = p×q (p,q bilangan prima). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Contoh: p=5, q=11: φ(55) = 4×10 = 40. Inilah alasan pemfaktoran n dapat memecahkan RSA — pemfaktoran tersebut mengungkap φ(n).

Teorema Euler

Jika GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Ini adalah dasar matematika dekripsi RSA: M = C^d mod n karena e×d ≡ 1 (mod φ(n)).

Menghitung d dalam RSA

Pilih e = 65537 (eksponen publik RSA yang umum). Hitung d = e^(-1) mod φ(n) menggunakan algoritme Euclidean diperluas. Verifikasi e×d mod φ(n) == 1.

Totien dalam Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Lambda Carmichael

RSA modern menggunakan fungsi lambda Carmichael λ(n) = lcm(p-1, q-1), bukan φ(n). Fungsi ini memberikan modulus yang lebih kecil dan setara. PKCS#1 v2 dan NIST merekomendasikan λ(n).

Ringkasan Penerapan Praktis

GCD: memverifikasi bahwa e relatif prima terhadap φ(n). Euclidean diperluas: menghitung kunci privat d. Totien: menentukan kelompok eksponen untuk perpangkatan modular. Ketiganya digunakan dalam setiap pembuatan kunci RSA.

Pemeriksaan Singkat

Untuk RSA dengan p=7 dan q=11, berapakah φ(n)?

Rangkuman

Sangat baik! GCD, algoritme Euclidean, dan totien Euler kini menjadi bagian dari perangkat Anda. Selanjutnya, kita mempelajari XOR dan operasi bitwise — blok pembangun sandi simetris.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “GCD, Totien Euler, dan Pengantar Teori Bilangan” gratis?

Ya — teks lengkap “GCD, Totien Euler, dan Pengantar Teori Bilangan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Cryptology Academy, upgrade ke CoddyKit PRO. Kursus Cryptology Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “GCD, Totien Euler, dan Pengantar Teori Bilangan”?

Terapkan GCD dan fungsi totien Euler pada masalah kriptografi nyata. Kamu berlatih Cryptology Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Cryptology Academy?

Tidak diperlukan pengalaman sebelumnya. Cryptology Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “GCD, Totien Euler, dan Pengantar Teori Bilangan” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Cryptology Academy ini?

Ya. Setiap pelajaran Cryptology Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Dasar-dasar Biner dan Heksadesimal
  2. Dasar-dasar Aritmetika Modular
  3. Bilangan Prima dan Faktorisasi
  4. GCD, Totien Euler, dan Pengantar Teori Bilangan
← Kembali ke Cryptology Academy