NIM : 17.01.071.034
MATA KULIAH: KRIPTOGRAFI
RANGKUMAN
Algoritma untuk Anjak piutang dan Komputasi Logaritma Diskrit
(Algorithms for Factoring and Computing Discrete Logarithms)
Metode kalkulus indeks memecahkan masalah logaritma diskrit di
kelompok siklik Z∗ hal (untuk p prime) dalam waktu yang panjangnya sub-eksponensial
dari hal. Pembaca yang cerdik mungkin memperhatikan bahwa algoritme seperti yang akan kami gambarkan beruang beberapa kemiripan dengan algoritma anjak piutang kuadrat diperkenalkan
dalam Bagian 8.1.3. Seperti dalam kasus algoritma itu, kita akan membahas utama
ide yang digunakan oleh metode kalkulus indeks tetapi meninggalkan detail di luar ruang lingkup perawatan kami. Juga, beberapa perubahan kecil dibuat untuk menyederhanakan presentasi. Metode kalkulus indeks menggunakan proses dua tahap. Yang penting, yang pertama Tahap hanya membutuhkan pengetahuan tentang modulus p dan dasar g dan sehingga bias dijalankan sebagai 'langkah pra-pemrosesan' sebelum Anda diketahui. Untuk alasan yang sama, itucukup untuk menjalankan tahap pertama hanya sekali untuk menyelesaikan beberapa contoh
masalah logaritma diskrit (selama semua instance ini berbagi hal yang sama p dan g).
Langkah 1. Misalkan q = p - 1, urutan Z∗ hal. Perbaiki satu set B = {p1,. . . , pk} dari
bilangan prima kecil. Pada tahap ini, kami menemukan `≥ k nilai-nilai yang berbeda dan tidak nol x1,. . . , x` ∈ Zq untuk yang mana gi def = g xi mod p adalah "kecil", sehingga gi dapat diperhitungkan atas bilangan bulat (menggunakan, mis., pembagian percobaan) dan sedemikian rupa sehingga semua faktor prima dari gi terletak di B. Kami tidak membahas bagaimana {xi} ini ditemukan. Mengikuti langkah ini, kami memiliki `persamaan bentuk:
gx1 = Yk
i=1 pe1;i i mod p
gx` = Yk i=1 pe`;i i mod p:
Dengan mengambil logaritma diskrit, kita dapat mengubahnya menjadi persamaan linear:
x1 = Xk
i=1 e1;i _ logg pi mod (p 1)
x` =Xk
i=1 e`;i _ logg pi mod (p 1):
Perhatikan bahwa {xi} dan {ei, j} diketahui, sedangkan {logg pi} tidak diketahui.
Langkah 2. Sekarang kita diberi elemen y dan ingin menghitung log y. Sini kami menemukan nilai x ∗ ∈ Zq untuk yang g∗ def = gx ∗· Y mod p adalah "kecil", sehingga g dapat diperhitungkan atas bilangan bulat dan sedemikian rupa sehingga semua faktor utama g∗ berbohong di B. Kami tidak membahas bagaimana x∗ ditemukan. Mengatakan
_ y = Yk
i=1pe_i
i mod p ) x_ + logg y = Xk i=1 e_ logg pi mod (p 1);
dimana x ∗ dan {e ∗ saya} diketahui. Dikombinasikan dengan Persamaan (8.5), kita miliki `+ 1 ≥ k + 1 persamaan linear dalam k + 1 tidak diketahui {logg pi} k i = 1 dan masuk y. Menggunakan metode linear algebraic6 (dan mengasumsikan sistem persamaan tidak di bawah-didefinisikan), kita dapat memecahkan untuk masing-masing yang tidak diketahui dan khususnya memecahkan untuk logg solusi yang diinginkan y.
Contoh 8.9
Misalkan p = 101, g = 3, dan y = 87. Kita punya 3 10 = 65 mod 101, dan 65 = 5 · 13 (lebih dari bilangan bulat). Demikian pula, 3 12 = 80 = 2 4 · 5 mod 101 dan 3 14 = 13 mod 101. Itu adalah;
10 = log3 5 + log3 13 mod 100
12 = 4 _ log3 2 + log3 5 mod 100
14 = log3 13 mod 100:
Kami juga punya 35 _ 87 = 32 = 25 mod 101, or
5 + log3 87 = 5 _ log3 2 mod 100
Menggunakan manipulasi aljabar sederhana, pertama-tama kita menurunkan 4 · log3 2 = 16 mod 100. Ini tidak menentukan log3 2 secara unik, tetapi ia memberi tahu kami bahwa log3 2 = 4, 29, 54, atau 79 (lih. Latihan 8.3). Mencoba semua kemungkinan menunjukkan bahwa log3 2 = 29. Memasukkan ini ke Persamaan (8.6) memberikan log3 87 = 40.
Durasi. Dapat ditunjukkan bahwa dengan optimasi yang sesuai algoritma kalkulus indeks berjalan dalam waktu 2 HAI( √ n · log n) untuk menghitung log diskrit aritme dalam Z ∗ hal untuk p a prime of length n. Poin pentingnya adalah ini adalah sub-eksponensial dalam kpk. Perhatikan bahwa ekspresi untuk waktu berjalan adalah identik dengan itu untuk metode ayakan kuadratik.
