PricingLoginStart free
Cryptology Academy · Pelajaran

GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor

Gunakan GCD dan fungsi totien Euler dalam masalah kripto sebenar.

Pelajaran 4 daripada 413 langkah

GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor ialah pelajaran Cryptology Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Cryptology Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Cryptology Academy merangkumi sejumlah 4 pelajaran.

Selamat Datang

GCD dan fungsi totien Euler ialah alat penting dalam RSA serta banyak sistem kunci awam yang lain. Mari kita kuasainya melalui contoh.

Pembahagi Sepunya Terbesar (GCD)

GCD(a, b) ialah integer terbesar yang membahagi kedua-dua a dan b tanpa baki. GCD(12, 8) = 4. Jika GCD(a, m) = 1, kita mengatakan bahawa a dan m adalah saling perdana atau relatif perdana.

Algoritma Euclid

GCD(a, b) = GCD(b, a mod b), dengan kes asas 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

Algoritma Euclid Lanjutan

Versi lanjutan mencari integer x, y sedemikian sehingga ax + by = GCD(a,b). Apabila GCD(a,m)=1, x ialah songsangan modular bagi a mod m. Inilah cara RSA mengira kunci persendirian.

Fungsi Totien Euler φ(n)

φ(n) mengira integer dari 1 hingga n yang saling perdana dengan n. φ(10) = 4 kerana {1, 3, 7, 9} saling perdana dengan 10. φ(p) = p-1 bagi mana-mana nombor perdana p.

Totien Hasil Darab

Bagi RSA: n = p×q (p,q perdana). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Contoh: p=5, q=11: φ(55) = 4×10 = 40. Inilah sebab pemfaktoran n memecahkan RSA — ia mendedahkan φ(n).

Teorem Euler

Jika GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Inilah asas matematik bagi penyahsulitan RSA: M = C^d mod n kerana e×d ≡ 1 (mod φ(n)).

Mengira d dalam RSA

Pilih e = 65537 (eksponen awam RSA yang biasa). Kira d = e^(-1) mod φ(n) menggunakan Euclid lanjutan. Sahkan 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 moden menggunakan fungsi lambda Carmichael λ(n) = lcm(p-1, q-1) dan bukannya φ(n). Fungsi ini memberikan modulus yang lebih kecil tetapi setara. PKCS#1 v2 dan NIST mengesyorkan λ(n).

Ringkasan Aplikasi Praktikal

GCD: sahkan bahawa e saling perdana dengan φ(n). Euclid lanjutan: kira kunci persendirian d. Totien: tentukan kumpulan eksponen untuk pendaraban modular. Ketiga-tiganya digunakan dalam setiap penjanaan kunci RSA.

Semakan Ringkas

Bagi RSA dengan p=7 dan q=11, apakah nilai φ(n)?
Jawab dalam pelajaran interaktif

Ulang Kaji

Syabas! GCD, algoritma Euclid dan totien Euler kini menjadi sebahagian daripada alatan anda. Seterusnya, kita mengkaji XOR dan operasi bit — asas kepada sifir simetri.
Percuma untuk bermula

Pelajari Cryptology Academy dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
67
Pelajaran
261
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor” percuma?

Ya — teks penuh “GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Cryptology Academy, tingkat taraf kepada CoddyKit PRO. Kursus Cryptology Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor”?

Gunakan GCD dan fungsi totien Euler dalam masalah kripto sebenar. Anda berlatih Cryptology Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Cryptology Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Cryptology Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Cryptology Academy ini?

Ya. Setiap pelajaran Cryptology Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Asas Perduaan dan Perenambelasan
  2. Asas Aritmetik Modular
  3. Nombor Perdana dan Pemfaktoran
  4. GCD, Fungsi Totien Euler dan Pengenalan Teori Nombor
← Kembali ke Cryptology Academy