PricingLoginStart free
Cryptology Academy · Pelajaran

Bilangan Prima dan Faktorisasi

Pelajari alasan bilangan prima menjadi tulang punggung kriptografi kunci publik.

Pelajaran 3 dari 413 langkah

Bilangan Prima dan Faktorisasi adalah pelajaran Cryptology Academy gratis di CoddyKit. Ini adalah pelajaran 3 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

Bilangan prima hanya dapat dibagi oleh 1 dan dirinya sendiri. Bilangan ini adalah atom-atom perkalian — sekaligus dasar RSA, Diffie-Hellman, dan banyak sistem kriptografi lainnya.

Definisi & Contoh

Bilangan prima: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Suatu bilangan adalah prima jika pembagi positifnya hanya 1 dan dirinya sendiri. 1 bukan bilangan prima berdasarkan kesepakatan.

Teorema Dasar Aritmetika

Setiap bilangan bulat > 1 dapat difaktorkan menjadi bilangan-bilangan prima dengan tepat satu cara (hingga urutannya). 60 = 2² × 3 × 5. Keunikan inilah yang membuat kriptografi berbasis pemfaktoran dapat berfungsi.

Pembagian Percobaan

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Hanya perlu memeriksa hingga √n — jika tidak ada faktor yang ditemukan di bawah √n, n adalah bilangan prima.

Saringan Eratosthenes

Untuk menemukan semua bilangan prima hingga N: mulai dengan daftar bilangan 2..N. Coret kelipatan 2, lalu 3, kemudian 5, dan seterusnya. Bilangan yang tersisa adalah bilangan prima. Berjalan dalam O(N log log N).

Pengujian Keprimaan: Miller-Rabin

Untuk bilangan besar (2048 bit), pembagian percobaan terlalu lambat. Miller-Rabin adalah uji probabilistik: jalankan 40 kali dan probabilitas kesalahannya adalah < 4^(-40).

Pemfaktoran Bilangan Bulat

Diberikan n = p × q, menemukan p dan q adalah masalah pemfaktoran bilangan bulat. Jika n berukuran 2048 bit, algoritme terbaik yang diketahui memerlukan 2^112 operasi — saat ini tidak layak dilakukan.

Mengapa RSA Menggunakan Dua Bilangan Prima Besar

Modulus RSA n = p × q. Mengetahui n tetapi tidak mengetahui p,q membuat penghitungan kunci privat menjadi sulit. Keamanan ini sepenuhnya bergantung pada sulitnya memfaktorkan n.

Membangkitkan Bilangan Prima Besar

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: buat bilangan ganjil acak, uji dengan Miller-Rabin, ulangi hingga mendapatkan bilangan prima.

Bilangan Prima Aman & Bilangan Prima Kuat

Bilangan prima aman p = 2q+1, dengan q juga merupakan bilangan prima. Bilangan prima aman menahan serangan tertentu terhadap DH. RSA terkadang menggunakan bilangan prima kuat untuk mencegah serangan Pollard p-1.

Jarak Bilangan Prima & Ketakhinggaan

Euclid membuktikan bahwa ada tak terhingga banyak bilangan prima pada 300 BCE. Konjektur bilangan prima kembar (bilangan prima p, p+2 ada tak terhingga banyak) masih belum terbukti. Kita tidak akan kehabisan bilangan prima untuk kriptografi.

Pemeriksaan Singkat

Mengapa RSA menggunakan bilangan prima besar?
Jawab di pelajaran interaktif

Rangkuman

Anda telah memahami bilangan prima dan pemfaktoran. Selanjutnya, kita menerapkan fungsi totien Euler dan GCD — alat matematika terakhir yang diperlukan sebelum RSA.
Gratis untuk memulai

Belajar Cryptology Academy dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus
67
Pelajaran
261
Mulai belajar gratisLihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Bilangan Prima dan Faktorisasi” gratis?

Ya — teks lengkap “Bilangan Prima dan Faktorisasi” 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 “Bilangan Prima dan Faktorisasi”?

Pelajari alasan bilangan prima menjadi tulang punggung kriptografi kunci publik. 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 3 dari 4.

Berapa lama pelajaran “Bilangan Prima dan Faktorisasi” 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