4 HASIL DAN PEMBAHASAN

7

4 HASIL DAN PEMBAHASAN Studi Pendahuluan Salah satu bahasan dalam aljabar linier yang merupakan kunci penting dalam latis adalah proses ortogonalisasi Gram-Schmidt. Proses ini akan menjadi ide utama dalam pembentukan algoritme LLL. Berikut ini definisi proses ortogonalisasi Gram-Schmidt. Ortogonalisasi Gram-Schmidt Misalkan ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } adalah himpunan n vektor bebas linier dalam ruang vektor ℝ𝑚 . Maka dapat dikonstruksi barisan bagian dari 𝑛 vektor yang saling ortogonal ℬ ∗ = {𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 } dimana 𝐛1∗ = 𝐛1 , 𝑗−1

𝐛𝑗∗ = 𝐛𝑗 − ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 𝑖=1

dengan 𝑗 = 2, 3, … , 𝑛 dan

𝐛𝑗 . 𝐛∗𝑖 . 𝐛∗𝑖 . 𝐛∗𝑖 Jika himpunan ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } adalah bebas linier, maka ℬ merupakan basis untuk 〈ℬ〉 = {∑𝑛𝑗=1 𝑥𝑗 𝐛𝑗 /𝑥𝑗 ∈ ℝ} , dan jika ℬ ∗ = {𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 } adalah hasil ortogonalisasi Gram-Schmidt dari ℬ, maka ℬ ∗ juga merupakan basis untuk 〈ℬ〉. Namun hal ini tidak berlaku secara umum dalam latis, jika ℬ adalah basis untuk latis yang dibangkitkan oleh ℬ, tidak harus ℬ ∗ merupakan basis untuk latis tersebut. 𝜇𝑗,𝑖 =

Kompleksitas Gram-Schmidt Dalam ortogonalisasi Gram-Schmidt terlihat bahwa banyaknya operasi aritmetik yang dilibatkan dalam proses tersebut adalah 𝑂(𝑛3 ). Namun, belum dapat disimpulkan bahwa waktu eksekusi (running time) pada ortogonalisasi Gram-Schmidt adalah polinomial. Diasumsikan bahwa matriks B yang digunakan adalah matriks bilangan bulat. Perhatikan bahwa langkah ke-j dari ortogonalisasi Gram-Schmidt dapat dirumuskan ulang sebagai 𝑗−1

𝐛𝑗∗

= 𝐛𝑗 + ∑ 𝜐𝑗𝑖 𝐛𝑖 𝑖=1

(1)

untuk suatu 𝜐𝑗𝑖 ∈ ℝ. Karena 𝐛𝑗∗ ortogonal ke 𝐛𝑡 untuk setiap 𝑡 < 𝑗 maka diperoleh 𝑗−1

𝐛𝑡 . 𝐛𝑗∗ = ( 𝐛𝑡 . 𝐛𝑗 ) + 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 𝑗−1

𝑖=1

⇔ 𝟎 = ( 𝐛𝑡 . 𝐛𝑗 ) + 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 𝑖=1

8 𝑗−1

⇔ 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 = −( 𝐛𝑡 . 𝐛𝑗 ).

(2)

𝑖=1

Untuk 𝑡 = 1, 2, … , 𝑗 − 1 , persamaan tersebut dapat dituliskan dalam bentuk matriks 𝑗−1 𝐛1 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 𝐛1 . 𝐛𝑗 𝑗−1 𝐛2 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 = − 𝐛2 . 𝐛𝑗 . ⋮ ⋮ 𝑗−1 (𝐛𝑗−1 . 𝐛𝑗 ) (𝐛𝑗−1 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 ) Jika didefinisikan matriks 𝐁𝑗−1 = (𝐛1

𝐛2

…

𝐛𝑗−1 )

dan matriks

𝜐𝑗1 𝜐𝑗2 𝐮𝑗 = ( ⋮ ), 𝜐𝑗,𝑗−1 maka persamaan (2) dapat ditulis sebagai 𝐛1 . (𝐁𝑗−1 𝐮𝑗 ) 𝐛1 . 𝐛𝑗 𝐛2 . (𝐁𝑗−1 𝐮𝑗 ) = − 𝐛2 . 𝐛𝑗 ⋮ ⋮ 𝐛 ( 𝑗−1 . 𝐛𝑗 ) (𝐛𝑗−1 . (𝐁𝑗−1 𝐮𝑗 )) 𝑇 𝑇 ⇔ 𝐁𝑗−1 (𝐁𝑗−1 𝐮𝑗 ) = −𝐁𝑗−1 𝐛𝑗 𝑇 𝑇 ⇔ (𝐁𝑗−1 𝐁𝑗−1 )𝐮𝑗 = −𝐁𝑗−1 𝐛𝑗 . (3) 𝑇 Persamaan (3) merupakan SPL dengan matriks koefisien 𝐁𝑗−1 𝐁𝑗−1 dan 𝑇 vektor −𝐁𝑗−1 𝐛𝑗 adalah bilangan bulat. Dengan demikian, untuk 𝑠 = 1, 2, … , 𝑗 − 1 berdasarkan aturan Cramer diperoleh ℤ ℤ 𝜐𝑗𝑠 ∈ = . 𝑇 det(𝐁𝑗−1 𝐁𝑗−1 ) det (ℒ(ℬ ))2 𝑗−1 Hasil ini digunakan untuk memberi batas pada koefisien pada koefisien 𝜇𝑗𝑖 . 𝑇 Misalkan 𝐷𝑗−1 = det(𝐁𝑗−1 𝐁𝑗−1 ) dan dikalikan nilainya dengan kedua ruas dari persamaan (1) maka diperoleh 𝑗−1

𝐷𝑗−1 𝐛𝑗∗

= 𝐷𝑗−1 𝐛𝑗 + ∑(𝐷𝑗−1 𝜐𝑗𝑖 ) 𝐛𝑖 𝑖=1

merupakan persamaan yang semua koefisien vektornya adalah bilangan bulat. Ini berarti semua penyebut dari bilangan dalam vektor 𝐛𝑗∗ adalah faktor 𝐷𝑗−1 . Kemudian 𝐛𝑗 . 𝐛∗𝑖 𝜇𝑗,𝑖 = ∗ ∗ 𝐛𝑖 . 𝐛𝑖 𝐷𝑖−1 (𝐛𝑗 . 𝐛∗𝑖 ) = 𝐷𝑖−1 (𝐛∗𝑖 . 𝐛∗𝑖 )

9 =

𝐛𝑗 (𝐷𝑖−1 . 𝐛∗𝑖 ) ∗ 𝟐 ∗ 𝟐 (∏𝑖−1 𝑠=1‖𝐛𝑠 ‖ )‖𝐛𝑖 ‖

∈

ℤ . 𝐷𝑖

Hasil ini menunjukkan bahwa penyebut dari 𝜇𝑗𝑖 harus membagi 𝐷𝑖 . Uraian diatas membuktikan bahwa bilangan-bilangan yang ada di dalam vektor 𝐛∗𝑖 dan 𝜇𝑗𝑖 mempunyai penyebut paling banyak 𝑛

max 𝐷𝑘 ≤ ∏‖𝐛∗𝑘 ‖𝟐 . 𝑘

𝑖=𝑘

Akhirnya, besarnya bilangan polinomial karena ‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗 ‖. Dengan demikian, secara keseluruhan ortogonalisasi Gram-Schmidt mempunyai kompleksitas waktu polinomial. Hal ini bermanfaat untuk menganalisis algoritme LLL yang akan direkonstruksi, dimana cara kerja algoritme ini berdasarkan atas proses ortogonalisasi Gram-Schmidt. Rekonstruksi Algoritme LLL Seperti yang telah dijelaskan dalam pendahuluan bahwa latis merupakan obyek geometrik dalam ruang berdimensi-n yang dapat diilustrasikan sebagai himpunan titik-titik yang teratur dan periodik. Definisi latis secara formal adalah sebagai berikut. Definisi 4.1 Misalkan ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } adalah himpunan n vektor bebas linier dalam ruang vektor ℝ𝑚 . Latis yang dibangkitkan oleh ℬ adalah himpunan 𝑛

ℒ(ℬ) = {∑ 𝑥𝑗 𝐛𝑗 /𝑥𝑗 ∈ ℤ} 𝑗=1

yang beranggotakan semua kombinasi linier bilangan bulat dari ℬ. Dalam hal ini, ℬ merupakan basis untuk ℒ(ℬ). Notasi “/” dibaca sebagai “dengan”. Seperti dalam ruang vektor, basis ℬ untuk latis ℒ(ℬ) dapat direpresentasikan sebagai matriks 𝐁 berukuran 𝑚 × 𝑛 yang kolom-kolomnya merupakan vektor 𝐛𝑗 : 𝐁 = (𝐛1 𝐛2 … 𝐛𝑛 ), sehingga ℒ(ℬ) dapat dituliskan sebagai perkalian matriks ℒ(𝐁) = {𝐁𝑥/𝑥 ∈ ℤ𝑛 }. Dalam hal ini, 𝐁 merupakan bentuk matriks dari ℬ. Terdapat kemiripan antara pengertian latis yang dibangkitkan oleh ℬ dengan pengertian subruang vektor dalam ℝ𝑚 yang direntang oleh ℬ: 𝑛

〈ℬ〉 = {∑ 𝑥𝑗 𝐛𝑗 /𝑥𝑗 ∈ ℝ}. 𝑗=1

Perbedaannya hanya terdapat pada bilangan yang digunakan pada kombinasi linier. Pada latis ℒ(ℬ), kombinasi linier menggunakan koefisien dalam rentang bilangan bulat (ℤ ⊆ ℝ). Sedangkan pada 〈ℬ〉, koefisien pada kombinasi linier yang digunakan adalah rentang bilangan real (ℝ), sehingga dapat disimpulkan bahwa jika ℬ adalah basis untuk ℒ(ℬ), maka ℬ juga merupakan basis untuk 〈ℬ〉. Namun hal ini tidak berlaku sebaliknya, jika ℬ adalah basis untuk 〈ℬ〉, belum

10 tentu ℬ juga basis untuk ℒ(ℬ). Misalkan dipilih basis ℬ1 = {(1,0), (0,1)} yang merupakan basis baku untuk ℝ2 , maka ℒ(ℬ1 ) = {𝑥(1,0) + 𝑦(0,1)/𝑥, 𝑦 ∈ ℤ} = {(𝑥, 𝑦)/𝑥, 𝑦 ∈ ℤ} = ℤ2 . Latis ℤ2 beserta basis diilustrasikan pada Gambar 1. Seperti pada ruang vektor, basis suatu latis tidak tunggal. Pada Gambar 2, diilustrasikan bahwa ℤ2 dapat dibangkitkan oleh latis basis ℬ2 = {(2,1), (3,1)}. Sedangkan pada Gambar 3 merupakan contoh basis ℬ3 = {(1,2), (4,1)} yang bukan merupakan basis untuk ℤ2 walaupun mempunyai rank penuh dalam ℝ2 . Selanjutnya Gambar 4 merupakan sebuah contoh bahwa basis ℬ4 = {(1,1)} yang membentuk latis ℒ(ℬ4 ) walaupun ℬ4 tidak memiliki rank penuh di dalam ℝ2 .

Gambar 1 Latis dengan basis {(1,0),(0,1)}

Gambar 3 Latis dengan basis {(1,2),(4,1)}

Gambar 2 Latis dengan basis {(2,1),(3,1)}

Gambar 4 Latis dengan basis {(1,1)}

11 Definisi 4.2 Dua basis 𝒜 dan ℬ dikatakan ekivalen, dinotasikan dengan 𝒜 ~ ℬ, jika dan hanya jika 𝒜 dan ℬ membangkitkan latis yang sama, yaitu ℒ(𝒜) = ℒ(ℬ). Definisi 4.3 Matriks U berukuran 𝑛 × 𝑛 disebut unimodular jika 𝐔 ∈ ℤ𝑛×𝑛 dan det(𝐔) = ±1. 1 3 −7 Contoh matriks unimodular: 𝐔 = ( 0 −1 2 ) dengan det(𝐔) = −1. −1 0 2 Proposisi 4.1 Invers dari matriks unimodular juga merupakan matriks unimodular. Bukti: Misalkan 𝐔 = (𝑢𝑖𝑗 ) adalah matriks unimodular berukuran 𝑛 × 𝑛 dari asumsi diperoleh 𝑢𝑖𝑗 ∈ ℤ dan det(𝐔) = ±1. Berdasarkan rumus matriks invers, maka 1

𝑇

𝐔 −𝟏 = det(𝐔) (𝜇𝑖𝑗 ) ,

(4)

dimana 𝜇𝑖𝑗 adalah kofaktor dari 𝑢𝑖𝑗 . Karena 𝑢𝑖𝑗 ∈ ℤ, dari definisi kofaktor, jelas bahwa 𝜇𝑖𝑗 ∈ ℤ sehingga (𝜇𝑖𝑗 )𝑇 ∈ ℤ𝑛×𝑛 . Disamping itu, 𝐔−𝟏 𝐔 = 𝐈 ⇒ det(𝐔−𝟏 𝐔) = det(𝐈) ⇒ det(𝐔−𝟏 )det(𝐔) = det(𝐈) 1 ⇒ det(𝐔−𝟏 ) = . det(𝐔) Karena det(𝐔) = ±1, maka 1 det(𝐔−𝟏 ) = ±1 dan det(𝐔) ∈ ℤ. (5) Dari (4) dan (5) dapat disimpulkan bahwa matriks 𝐔 −𝟏 merupakan matriks unimodular. Bukti lengkap. ∎ Proposisi 4.2 Misalkan 𝒜 = {𝐚1 , 𝐚2 , … , 𝐚𝑛 } adalah basis untuk ℒ(𝒜) dan ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } adalah basis untuk ℒ(ℬ). Maka 𝒜 ~ ℬ jika dan hanya jika adalah matriks unimodular 𝐔 ∈ ℤ𝑛×𝑛 sehingga 𝐁 = 𝐀𝐔, dimana 𝐀 dan 𝐁 adalah bentuk matriks 𝐀 = (𝐚1 𝐚2 … 𝐚𝑛 ) dan 𝐁 = (𝐛1 𝐛2 … 𝐛𝑛 ). Bukti: (⇒) Misalkan ℒ(𝒜) = ℒ(ℬ) . Dari asumsi ini, berarti untuk setiap 𝑗 = 1, 2, … 𝑛 untuk 𝐛𝑗 ∈ ℒ(𝒜). Dari pengertian ℒ(𝒜) maka ada 𝐮𝑗 = (𝑢1𝑗 𝑢1𝑗 … 𝑢1𝑗 ) ∈ ℤ𝑛 sehingga 𝑛

𝐛𝑗 = ∑ 𝑢𝑖𝑗 𝐚𝑗 . 𝑖=1

(6)

12 Dengan demikian, dapat didefinisikan matriks 𝐔 ∈ ℤ𝑛×𝑛 yang kolom-kolomnya adalah vektor 𝐮𝑗 , yaitu 𝑢11 𝑢12 … 𝑢1𝑛 𝑢21 𝑢22 … 𝑢2𝑛 ). 𝐔 = (𝐮1 𝐮2 … 𝐮𝑛 ) = ( ⋮ ⋮ ⋱ ⋮ 𝑢𝑛1 𝑢𝑛2 … 𝑢𝑛𝑛 Dari persamaan (6) diperoleh persamaan matriks (𝐛1 𝐛2 … 𝐛𝑛 ) = (𝐚1 𝐚2 … 𝐚𝑛 )(𝐮1 𝐮2 … 𝐮𝑛 ) ⇔ 𝐁 = 𝐀𝐔. (7) Dengan langkah yang sama, dapat diperoleh matriks 𝐕 ∈ ℤ𝑛×𝑛 sehingga 𝐀 = 𝐁𝐕. (8) Dari persamaan (7) dan (8), 𝐀 = 𝐁𝐕 = 𝐀𝐔𝐕 ⇒ det(𝐀) = det(𝐀𝐔𝐕) ⇔ det(𝐔) det(𝐕) = 1. Disamping itu, karena 𝐔 dan 𝐕 adalah matriks bilangan bulat, maka determinannya juga bilangan bulat. Dengan demikian, dapat disimpulkan bahwa det(𝐔) = ±1. (⇐) Misalkan 𝐁 = 𝐀𝐔 dengan U unimodular. Dari asumsi ini, berarti untuk setiap 𝑗 = 1, 2, … , 𝑛 , 𝐛𝑗 ∈ ℒ(𝒜) , dengan kata lain, 𝐛𝑗 merupakan kombinasi linier bilangan bulat dari 𝒜. Selanjutnya bahwa karena setiap 𝐱 ∈ ℒ(ℬ) merupakan kombinasi linier dari {𝐛1 𝐛2 … 𝐛𝑛 } , maka dapat disimpulkan bahwa x juga merupakan kombinasi linier bilangan bulat dari 𝒜 (artinya 𝐱 ∈ ℒ(𝒜)). Dengan demikian, diperoleh ℒ(ℬ) ⊆ ℒ(𝒜). Sekarang tinggal ditunjukkan ℒ(𝒜) ⊆ ℒ(ℬ). Perhatikan bahwa, dari asumsi juga diperoleh 𝐀 = 𝐁𝐔−1 dengan 𝐔−1 adalah unimodular (Proposisi 4.1). Akhirnya dengan langkah yang sama dengan sebelumnya diperoleh ℒ(𝒜) ⊆ ℒ(ℬ). Bukti lengkap. ∎ Cara yang lebih praktis untuk menentukan dua basis yang ekivalen adalah dengan menerapkan operasi kolom integer (integer column operation). Definisi 4.4 Operasi Kolom Integer (OKI) pada matriks 𝐁 memiliki 3 jenis berikut: 1. 𝐾𝑗𝑘 (𝐁) menyatakan matriks hasil operasi yang menukar kolom ke-j dan kolom ke-k pada matriks 𝐁. 2. 𝐾𝑗(−1) (𝐁) menyatakan matriks hasil operasi yang mengalikan kolom ke-j dengan skalar -1 pada matriks 𝐁. 3. 𝐾𝑗𝑘(𝜆) (𝐁) menyatakan matriks hasil operasi yang menambahkan kolom ke-j dengan 𝜆 ∈ ℤ kali kolom ke-k pada matriks 𝐁. OKI hampir sama dengan Operasi Kolom Dasar (OKD) yang biasanya diterapkan pada ruang vektor. Hal yang membedakan hanya terdapat pada jenis kedua. Pada OKD, pengali yang digunakan adalah sembarang bilangan real taknol sedangkan pada OKI pengali yang digunakan adalah -1. Kemudian, misalkan I adalah matriks identitas dan K adalah serangkaian OKI yang diterapkan pada suatu matriks B dan menghasilkan matriks C, maka berlaku 𝐾(𝐁) = 𝐂 ⇔ 𝐁. 𝐾(𝐈) = 𝐂. Serangkaian OKI yang diterapkan pada I pasti akan menghasilkan matriks bilangan bulat, sehingga 𝐾(𝐈) merupakan matriks bilangan bulat. Disamping itu,

13 karena det(𝐈) = 1, OKI jenis pertama dan kedua bersifat mengubah tanda determinan, dan OKI jenis ketiga bersifat tidak mengubah nilai determinan, sehingga didapatkan det(𝐾(𝐈)) = ±1. Dengan demikian dapat disimpulkan bahwa 𝐾(𝐈) merupakan matriks unimodular, sehingga didapatkan proposisi berikut. Proposisi 4.3 Dua basis dikatakan ekivalen jika dan hanya jika yang satu merupakan hasil serangkaian OKI dari yang lain. Fungsi Proyeksi dan Determinan Latis Definisi 4.5 Untuk 𝑗 = 1, 2, … , 𝑛 fungsi proyeksi 𝜋𝑗 dari ruang vektor 𝑉 = 〈ℬ ∗ 〉 = 〈ℬ〉 ∗ ke subruang vektor 〈{𝐛𝑗∗ , 𝐛𝑗+1 , … , 𝐛∗𝑛 }〉 didefinisikan sebagai 𝑛

𝐯. 𝐛∗𝑖 𝜋𝑗 (𝐯) = ∑ ( ∗ ∗ ) 𝐛∗𝑖 . 𝐛 𝑖 . 𝐛𝑖 𝑖=𝑗

Jika diambil nilai 𝐯 = 𝐛𝑘 , 𝑘 = 1, 2, … , 𝑛 maka diperoleh 𝟎 𝑛 𝐛∗𝑘 𝐯. 𝐛∗𝑖 ∗ 𝑘−1 𝜋𝑗 (𝐛𝑘 ) = ∑ ( ∗ ∗ ) 𝐛𝑖 = 𝐛𝑖 . 𝐛𝑖 ∗ 𝐛𝑘 + ∑ 𝜇𝑘𝑖 𝐛∗𝑖 𝑖=𝑗 { 𝑖=𝑗 Selanjutnya perhatikan definisi berikut.

jika 𝑘 < 𝑗 jika 𝑘 = 𝑗 jika 𝑘 > 𝑗.

Definisi 4.6 Misalkan Λ = ℒ(ℬ) adalah latis yang dibangkitkan oleh basis ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 }, maka dapat didefinisikan himpunan 𝑛

𝒫(ℬ) = {∑ 𝑥𝑗 𝐛𝑗 /𝑥𝑗 ∈ ℝ, 0 ≤ 𝑥𝑗 < 1}, 𝑗=1

dimana 𝒫(ℬ) merupakan bangun geometrik yang disebut parallelepiped dasar atau daerah fundamental (fundamental region). Berikut ilustrasi dari 𝒫(ℬ).

Gambar 5 Parallelepiped dengan ℬ = {(2,3), (3,2)}

14 Dari Gambar 5 terlihat bahwa pada latis dalam ℝ2 , 𝒫(ℬ) digambarkan sebagai daerah arsir jajaran genjang. Hasil dari luas jajaran genjang pada Gambar 5 disebut 𝐯𝐨𝐥(𝒫(ℬ)). Pada sembarang latis Λ, dapat didefinisikan nilai mutlak dari determinan latis dari Λ, dinotasikan dengan |det(Λ)|, yang merupakan nilai dari 𝐯𝐨𝐥(𝒫(ℬ)). Dari ilustrasi Gambar 5, maka definisi tersebut dapat dinyatakan sebagai berikut. Definisi 4.7 Misalkan Λ = ℒ(ℬ) adalah latis yang dibangkitkan oleh basis ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } dan ℬ ∗ = {𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 } adalah hasil ortogonalisasi GramSchmidt dari ℬ. Determinan dari Λ didefinisikan sebagai 𝑛

det(Λ) = ∏‖𝐛∗𝑖 ‖. 𝑖=1

Cara menentukan determinan suatu latis tanpa menggunakan ortogonalisasi Gram-Schmidt akan dijelaskan oleh proposisi setelah lema berikut ini. Lema 4.1 Jika matriks

𝐁 ∗ = (𝐛1∗ 𝐛∗2 … 𝐛∗𝑛 ) adalah matriks hasil ortogonalisasi Gram-Schmidt dari matriks 𝐁 = (𝐛1 𝐛2 … 𝐛𝑛 ), maka ada matriks U dengan unsur diagonal adalah 1 sehingga 𝐁 = 𝐁 ∗ 𝐔. Bukti: Perhatikan bahwa rumus ortogonalisasi Gram-Schmidt dapat diubah menjadi 𝐛1 = 𝐛1∗ 𝐛2 = 𝐛∗2 + 𝜇21 𝐛1∗ 𝐛3 = 𝐛∗3 + (𝜇31 𝐛1∗ + 𝜇32 𝐛∗2 ) ⋮ 𝑛−1

𝐛𝑛 =

𝐛∗𝑛

+ ∑ 𝜇𝑛,𝑖 𝐛∗𝑖 . 𝑖=1

Hal ini menunjukkan bahwa transformasi balik dari ortogonalisasi Gram-Schmidt dari 𝐁 ∗ ke 𝐁 merupakan serangkaian OKD yang dilakukan pada matriks B, yaitu 𝐁 = 𝐾(𝐁 ∗ ) ⇔ 𝐁 = 𝐁 ∗ 𝐾(𝐈). Dengan demikian dapat didefinisikan suatu matriks 𝐔 = 𝐾(𝐈), dimana 1 𝜇21 … 𝜇𝑛1 0 1 … 𝜇𝑛2 𝐾(𝐈) = ( ⋮ ). ⋮ ⋮ ⋱ 1 0 0 1 Bukti lengkap. ∎ Proposisi 4.4 Jika Λ = ℒ(ℬ) adalah latis yang dibangkitkan {𝐛1 , 𝐛2 , … , 𝐛𝑛 }, maka det(Λ) = √det(𝐁 𝑇 𝐁), dimana B adalah bentuk matriks dari ℬ.

oleh

basis ℬ =

15 Bukti: Misalkan

𝐁 ∗ = (𝐛1∗ 𝐛∗2 … 𝐛∗𝑛 ) adalah matriks ortogonalisasi dari matriks 𝐁 = (𝐛1 𝐛2 … 𝐛𝑛 ). Menurut Lema 4.1, terdapat sebuah matriks U yang unsur diagonalnya adalah 1 sehingga 𝐁 = 𝐁 ∗ 𝐔. Dengan demikian diperoleh 𝐁 𝑇 𝐁 = (𝐁 ∗ 𝐔)𝑇 (𝐁 ∗ 𝐔) ⇔ 𝐁 𝑇 𝐁 = 𝐔𝑇 ((𝐁 ∗ )𝑇 𝐁 ∗ )𝐔 ⇒ det(𝐁 𝑇 𝐁) = det(𝐔 𝑇 ((𝐁 ∗ )𝑇 𝐁 ∗ )𝐔) ⇔ det(𝐁 𝑇 𝐁) = det((𝐁 ∗ )𝑇 𝐁 ∗ ) 𝑛

2

⇔ det(𝐁 𝑇 𝐁) = (∏‖𝐛∗𝑖 ‖) 𝑛

𝑖=1

⇔ ∏‖𝐛∗𝑖 ‖ = √det(𝐁 𝑇 𝐁) 𝑖=1

⇔ det(Λ) = √det(𝐁 𝑇 𝐁). Bukti lengkap. ∎ Berikut ini merupakan proposisi yang menjelaskan bahwa determinan suatu latis tidak bergantung pada suatu basis. Proposisi 4.5 Jika 𝒜 ~ ℬ, maka det(ℒ(𝒜)) = det(ℒ(ℬ)). Bukti: Misalkan 𝒜 ~ ℬ dengan A dan B adalah bentuk matriks dari 𝒜 dan ℬ . Berdasarkan Proposisi 4.2 terdapat sebuah matriks unimodular U sehingga 𝐀 = 𝐁𝐔. Dengan demikian, det(ℒ(𝒜)) = √det(𝐀𝑇 𝐀) = √det((𝐁𝐔)𝑇 (𝐁𝐔)) = √det(𝐔𝑇 (𝐁 𝑇 𝐁)𝐔) = √det(𝐁 𝑇 𝐁) = det(ℒ(ℬ)). Bukti lengkap. ∎

Permasalahan dalam Latis Berikut merupakan pengertian jarak minimum dan panjang vektor minimum dari suatu latis.

16 Definisi 4.8 Jarak minimum antara sebarang dua titik di dalam latis Λ , dinotasikan dengan 𝜆(Λ), didefinisikan sebagai 𝜆(Λ) = inf(‖𝐱 − 𝐲‖ ∕ 𝐱, 𝐲 ∈ 𝚲, 𝐱 ≠ 𝐲 ). Definisi 4.9 Panjang vektor minimum di antara titik-titik di dalam latis Λ, dinotasikan dengan 𝜋(Λ), didefinisikan sebagai 𝜋(Λ) = inf(‖𝐱‖ ∕ 𝐱 ∈ 𝚲, 𝐱 ≠ 𝟎 ). Dua pengertian diatas memiliki arti yang ekivalen. Hal tersebut dinyatakan dalam proposisi berikut. Proposisi 4.5 Untuk sembarang latis Λ, berlaku 𝜆(Λ) = 𝜋(Λ). Bukti: Karena Λ adalah grup, maka berlaku 𝜆(Λ) = inf(‖𝐱 − 𝐲‖⁄𝐱 , 𝐲 ∈ 𝚲, 𝐱 ≠ 𝐲 ) = inf(‖𝐳‖/𝐳 = 𝐱 − 𝐲 ∈ 𝚲, 𝐱 ≠ 𝐲) = inf(‖𝐳‖/𝐳 ∈ 𝚲, 𝐳 ≠ 𝟎) = 𝜋(Λ). Bukti lengkap. ∎ Berikut ini merupakan batas bawah dari 𝜆. Teorema 4.1 Jika Jika Λ = ℒ(ℬ) adalah latis yang dibangkitkan oleh basis ℬ = {𝐛1 , 𝐛2 , … , 𝐛𝑛 } dan ℬ ∗ = {𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 } adalah hasil ortogonalisasi dari ℬ maka min‖𝐛𝑗∗ ‖ ≤ 𝜆(Λ), 𝐼𝑛 = {1,2, … , 𝑛}. 𝑗∈𝐼𝑛

Bukti: Ambil sembarang 𝐯 ∈ ℒ(ℬ) dengan 𝐯 ≠ 𝟎, maka ada vektor 𝐱 ∈ ℤ𝑛 dengan 𝐱 ≠ 𝟎 sehingga 𝐯 = 𝐁𝐱 dengan B adalah matriks bilangan bulat dari ℬ. Misalkan 𝐱 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } dan 𝑘 adalah indeks terbesar dari komponen x sehingga 𝑥𝑘 ≠ 0, karena untuk setiap 𝑗 < 𝑘, 𝐛∗𝑘 ortogonal ke 𝐛𝑗 dan juga ortogonal ke 𝐛𝑗∗ , maka 𝐯. 𝐛∗𝑘 = (𝐁𝐱). 𝐛∗𝑘 𝑘

= (∑ 𝑥𝑗 𝐛𝑗 ) . 𝐛∗𝑘 𝑗=1

= 𝑥𝑘 (𝐛𝑘 . 𝐛∗𝑘 ) dan 𝑘−1

𝐛∗𝑘 . 𝐛∗𝑘 = (𝐛𝑘 − ∑ 𝜇𝑘𝑗 𝐛𝑗 ) . 𝐛∗𝑘 𝑗=1

= 𝐛𝑘 . 𝐛∗𝑘 . Dengan demikian diperoleh 𝐯. 𝐛∗𝑘 = 𝑥𝑘 (𝐛∗𝑘 . 𝐛∗𝑘 )

17 = 𝑥𝑘 ‖𝐛∗𝑘 ‖2 . Berdasarkan ketaksamaan Cauchy-Schwartz, maka diperoleh |𝐯. 𝐛∗𝑘 | ≤ ‖𝐯‖‖𝐛∗𝑘 ‖ ⇔ |𝑥𝑘 |‖𝐛∗𝑘 ‖2 ≤ ‖𝐯‖‖𝐛∗𝑘 ‖ ⇔ |𝑥𝑘 |‖𝐛∗𝑘 ‖2 ≤ ‖𝐯‖. Karena |𝑥𝑘 | ≥ 1, untuk 𝐼𝑛 = {1, 2, … , 𝑛} diperoleh min‖𝐛𝑗∗ ‖ ≤ 𝜆(Λ). 𝑗∈𝐼𝑛

Bukti lengkap. ∎ Selanjutnya didefinisikan masalah yang paling mendasar dalam latis, yaitu SVP (Shortest Vector Problem). Berikut merupakan varian dari SVP. Problem 4.1 (Pelacakan SVP) Diberikan sebuah latis dengan basis ℬ, bagaimana menentukan 𝐱 ∈ ℒ(ℬ) sehingga ‖𝐱‖ = 𝜆(ℒ(ℬ)). Problem 4.2 (Optimisasi SVP) Diberikan sebuah latis dengan basis ℬ, bagaimana menentukan 𝜆(ℒ(ℬ)). Problem 4.3 (Pelacakan SVP) Diberikan sebuah latis dengan basis ℬ dan bilangan rasional 𝑞 ∈ ℚ , bagaimana menentukan apakah 𝜆(ℒ(ℬ)) ≤ 𝑞 atau 𝜆(ℒ(ℬ)) > 𝑞. Problem 4.4 (Pelacakan SVP) Diberikan sebuah latis dengan basis ℬ dan 𝛾 ≥ 1, bagaimana menentukan 𝐱 ∈ ℒ(ℬ) dengan 𝐱 ≠ 𝟎 sehingga ‖𝐱‖ ≤ 𝛾𝜆(ℒ(ℬ)). Problem 4.5 (Pelacakan SVP) Diberikan sebuah latis dengan basis ℬ dan 𝛾 ≥ 1, bagaimana menentukan 𝑑 sehingga 𝑑 ≤ 𝜆(ℒ(ℬ)) ≤ 𝛾𝑑. Algoritme LLL Pengertian Basis Tereduksi Berikut ini merupakan definisi dari basis tereduksi 𝛿. Definisi 4.10 Suatu basis ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ℝ𝑚 disebut tereduksi LLL dengan parameter 𝛿 jika memenuhi 1 1. |𝜇𝑗𝑖 | ≤ 2, untuk setiap bilangan bulat 𝑖, 𝑗 dengan 1 ≤ 𝑖 < 𝑗 < 𝑛, 2

2

2. 𝛿‖𝜋𝑗 (𝐛𝑗 )‖ ≤ ‖𝜋𝑗 (𝐛𝑗+1 )‖ , untuk 𝑗 = 1, 2, … , 𝑛 − 1, 1

dimana 𝛿 merupakan parameter reduksi yang bernilai real dengan 4 < 𝛿 < 1. Syarat pertama dalam definisi di atas disebut dengan reduksi ukuran. Syarat pertama mengatakan bahwa basis tereduksi 𝛿 harus “hampir ortogonal” dan dalam

18 komputasinya syarat ini mudah dicapai dengan menggunakan ortogonalisasi Gram-Schmidt. Pembahasan mengenai syarat ini akan dibahas pada subbab berikutnya. Sedangkan pada syarat kedua dari definisi di atas disebut syarat pertukaran, atau disebut juga kondisi Lovasz, yang dapat ditulis ulang sebagai 2 2 ∗ 𝛿‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 + 𝜇𝑗+1,𝑗 𝐛𝑗∗ ‖ 2

∗ ∗ ⇔ 𝛿‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 + 𝜇𝑗+1,𝑗 𝐛𝑗∗ ‖ ‖𝐛𝑗+1 + 𝜇𝑗+1,𝑗 𝐛𝑗∗ ‖ 2

2

∗ ∗ ⇔ 𝛿‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 ‖ + 2𝜇𝑗+1,𝑗 ‖𝐛𝑗∗ . 𝐛𝑗+1 ‖+‖𝜇𝑗+1,𝑗 𝐛∗𝑗 ‖ 2

2

∗ ⇔ 𝛿‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 ‖ +𝜇𝑗+1,𝑗 ‖𝐛𝑗∗ ‖ 2

2

2

2

2 ∗ ⇔ (𝛿 − 𝜇𝑗+1,𝑗 )‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 ‖ . Ketaksamaan diatas menyatakan bahwa vektor-vektor Gram-Schmidt dari basis tereduksi LLL harus terurut turun dengan faktor penurunan sebesar 𝛿 − 2 ∗ 𝜇𝑗+1,𝑗 . Jika terdapat pasangan vektor (𝐛𝑗∗ , 𝐛𝑗+1 ) yang tidak memenuhi kondisi Lovasz, maka dapat dilakukan pertukaran antara vektor tersebut kemudian proses ortogonalisasi kembali dilakukan. Selanjutnya dengan menerapkan syarat-syarat yang terdapat pada Definisi 4.10, maka diperoleh batas atas untuk ‖𝐛1 ‖ dari basis tereduksi 𝛿.

Teorema 4.2 Jika ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ℝ𝑚 adalah basis tereduksi 𝛿, maka berlaku ‖𝐛1 ‖ ≤ 𝛼

𝑛−1 2

𝜆(Λ) dengan 𝛼 =

1 𝛿−

1 4

.

Bukti: Misalkan ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ℝ𝑚 adalah basis tereduksi 𝛿, menurut definisi diperoleh 2 2 ∗ 𝛿‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 + 𝜇𝑗+1,𝑗 𝐛𝑗∗ ‖ 2

2

2 ∗ ⇔ (𝛿 − 𝜇𝑗+1,𝑗 )‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 ‖ 1 2 2 ∗ ⇔ (𝛿 − ) ‖𝐛𝑗∗ ‖ ≤ ‖𝐛𝑗+1 ‖ 4 1 ∗ 2 2 ∗ ⇔ ‖𝐛𝑗 ‖ ≤ ‖𝐛𝑗+1 ‖ 𝛼 2 2 ∗ ⇔ ‖𝐛𝑗∗ ‖ ≤ 𝛼‖𝐛𝑗+1 ‖ . Dengan menerapkan pertidaksamaan (9) secara berulang diperoleh ‖𝐛1∗ ‖2 ≤ 𝛼‖𝐛∗2 ‖2 ‖𝐛∗2 ‖2 ≤ 𝛼‖𝐛∗3 ‖2 ‖𝐛∗3 ‖2 ≤ 𝛼‖𝐛∗4 ‖2 ⋮ ‖𝐛1∗ ‖2 ≤ 𝛼‖𝐛∗2 ‖2 ≤ 𝛼 2 ‖𝐛∗3 ‖2 ≤ ⋯ ≤ 𝛼 𝑛−1 ‖𝐛∗𝑛 ‖2 . Dengan kata lain, secara umum untuk setiap 𝑗 ∈ 𝐼𝑛 = {1,2, … , 𝑛}, maka 2

‖𝐛1∗ ‖2 ≤ 𝛼 𝑗−1 ‖𝐛𝑗∗ ‖ ⇒ ‖𝐛1∗ ‖ ≤ 𝛼 Karena berlaku untuk setiap 𝑗 ∈ 𝐼𝑛 , maka ‖𝐛1∗ ‖ ≤ (𝛼

𝑗−1 2

𝑗−1 2

‖𝐛𝑗∗ ‖ ⇔ ‖𝐛1∗ ‖ ≤ 𝛼

) (min‖𝐛𝑗∗ ‖). 𝑗∈𝐼𝑛

𝑗−1 2

(9)

‖𝐛𝑗∗ ‖. (10)

19 Misalkan ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ℝ𝑚 adalah basis tereduksi LLL untuk latis Λ = ℒ(ℬ), menurut Teorema 4.1 diperoleh min‖𝐛𝑗∗ ‖ ≤ 𝜆(Λ) 𝑗∈𝐼𝑛

dan ketaksamaan persamaan (10) menjadi ‖𝐛1∗ ‖ ≤ (𝛼

𝑗−1 2

) 𝜆(Λ).

Bukti lengkap. ∎ Teorema 4.2 menyatakan bahwa vektor pertama pada basis tereduksi 𝛿 merupakan jawaban dari Problem 4.4 dengan nilai 𝛾 = 𝛼

𝑗−1 2

.

Reduksi Ukuran Sebagaimana telah dinyatakan dalam subbab sebelumnya bahwa syarat 1 reduksi ukuran yaitu |𝜇𝑗,𝑖 | ≤ 2 mudah dicapai dengan menggunakan prosedur Gram-Schmidt. Pada subbab ini akan dibahas melalui interpretasi geometrik. Untuk itu perlu pengertian tentang daerah fundamental (parallelepiped) yang lain dari 𝒫(ℬ), yaitu daerah fundamental dasar terpusat yang didefinisikan sebagai berikut. Definisi 4.11 Misalkan Λ = ℒ(ℬ) adalah latis yang dibangkitkan oleh basis ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ruang vektor ℝ𝑚 . Daerah fundamental terpusat (centered fundamental region) dari Λ , dinotasikan dengan 𝒞(ℬ) , didefinisikan sebagai himpunan 𝑛

1 1 𝒞(ℬ) = {∑ 𝑥𝑗 𝐛𝑗 /𝑥𝑗 ∈ ℝ, − ≤ 𝑥𝑗 < }. 2 2 𝑗=1

𝒞(ℬ) juga disebut parallelepiped dasar terpusat (centered fundamental region). Proposisi 4.6 Jika Λ = ℒ(ℬ) adalah latis yang dibangkitkan oleh basis ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dalam ruang vektor ℝ𝑚 , maka untuk setiap vektor 𝐰 ∈ 〈ℬ〉, ada tepat satu vektor 𝐭 ∈ 𝒞(ℬ) sehingga dapat dituliskan 𝐰 = 𝐯 + 𝐭. Bukti: Karena ℬ merupakan basis untuk Λ, maka ℬ juga merupakan basis untuk ruang vektor 〈ℬ〉, dan karena 𝐰 ∈ 〈ℬ〉, berarti ada tepat satu (𝑤1 , 𝑤2 , … , 𝑤𝑛 ) ∈ ℝ𝑛 sehingga 𝑛

𝐰 = ∑ 𝑤𝑗 𝐛𝑗 . 𝑗=1

Kemudian, karena 𝑤𝑗 ∈ ℝ maka ada bilangan bulat ⌊𝑤𝑗 ⌉ ∈ ℤ (pembulatan ke bilangan bulat terdekat (round) dari 𝑤𝑗 sehingga 1

1

2

2

𝑤𝑗 = ⌊𝑤𝑗 ⌉ + 𝑡𝑗 dengan − ≤ 𝑡𝑗 < . Selanjutnya,

20 𝑛

𝐰 = ∑ 𝑤𝑗 𝐛𝑗 𝑗=1 𝑛

= ∑(⌊𝑤𝑗 ⌉ + 𝑡𝑗 )𝐛𝑗 𝑗=1 𝑛

𝑛

= ∑⌊𝑤𝑗 ⌉𝐛𝑗 + ∑ 𝑡𝑗 𝐛𝑗 𝑗=1

𝑗=1

= 𝐯 + 𝐭. Bukti lengkap. ∎ Lema 4.2 Misalkan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi GramSchmidt dari himpunan bebas linier ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dan diberikan sebarang 𝐰 ∈ 〈ℬ〉. Jika 𝐰 = ∑𝑛𝑗=1 𝑤𝑗 𝐛𝑗 , maka 𝐰. 𝐛∗𝑛 𝑤𝑛 = ∗ ∗ . 𝐛𝑛 . 𝐛𝑛 Bukti: Perhatikan bahwa 𝑛

𝐰. 𝐛∗𝑛

=

𝑛

(∑ 𝑤𝑗 𝐛𝑗 ) . 𝐛∗𝑛

=

𝑗=1

∑ 𝑤𝑗 (𝐛𝑗 . 𝐛∗𝑛 )

= 𝑤𝑛 (𝐛𝑛 . 𝐛∗𝑛 ) ⇔ 𝑤𝑛 =

𝑗=1

𝐰. 𝐛∗𝑛 . 𝐛𝑛∗ . 𝐛𝑛∗

Bukti selesai setelah ditunjukkan bahwa 𝐛𝑛 . 𝐛∗𝑛 = 𝐛∗𝑛 . 𝐛∗𝑛 sebagai berikut 𝑛−1

𝐛𝑛 . 𝐛∗𝑛

=

(𝐛∗𝑛

+ ∑ 𝜇𝑛,𝑖 𝐛∗𝑖 ) . 𝐛∗𝑛 𝑖=1 𝑛−1

= 𝐛∗𝑛 . 𝐛∗𝑛 + ∑ 𝜇𝑛,𝑖 (𝐛∗𝑖 . 𝐛∗𝑛 ) 𝑖=1 𝑛−1

= 𝐛∗𝑛 . 𝐛∗𝑛 + ∑ 𝜇𝑛,𝑖 (0) = 𝐛∗𝑛 . 𝐛∗𝑛 .

𝑖=1

Bukti lengkap. ∎ Proposisi 4.7 Jika ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi Gram-Schmidt dari himpunan bebas linier ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] , maka 𝒞(ℬ ∗ ) juga merupakan daerah fundamental untuk ℒ(ℬ). Artinya, untuk setiap 𝐰 ∈ 〈ℬ〉, ada tepat satu vektor latis 𝐰 ∈ ℒ(ℬ) dan ada tepat satu vektor 𝐭 ∈ 𝒞(ℬ ∗ ) sehingga dapat dituliskan 𝐰 = 𝐯 + 𝐭. Bukti: Demi kepentingan bagaimana menentukan 𝐯 dan 𝐭 secara algoritmik, proposisi ini akan dibuktikan secara instruktif. Kemudian, agar lebih mudah dibayangkan, tanpa mengurangi keumumannya, diambil untuk kasus 𝑛 = 3 sebagai berikut.

21 1. Definisikan 𝐰3 = 𝐰 , karena 𝐰3 ∈ 〈{𝐛1 , 𝐛2 , 𝐛3 }〉 , berarti ada tepat satu (𝑥1 , 𝑥2 , 𝑥3 ) ∈ ℝ3 sehingga 3

𝐰3 = ∑ 𝑥𝑗 𝐛𝑗 𝑗=1

dan berdasarkan Lema 4.2 dapat dituliskan 2

𝐰3 = ∑ 𝑥𝑗 𝐛𝑗 + 𝑗=1 2

𝐰𝟑 . 𝐛∗3 𝐛 𝐛∗3 . 𝐛∗3 3

𝐰3 . 𝐛∗3 = ∑ 𝑥𝑗 𝐛𝑗 + (⌊ ∗ ∗ ⌉ + 𝑡3 ) 𝐛3 𝐛3 . 𝐛3 𝑗=1 1

1

dan dalam hal ini, − 2 ≤ 𝑡3 < 2. Selanjutnya, 2

𝐰3 . 𝐛∗3 𝐰3 = ∑ 𝑥𝑗 𝐛𝑗 + ⌊ ∗ ∗ ⌉ 𝐛3 + 𝑡3 𝐛3 𝐛3 . 𝐛3 𝑗=1

2

2

𝐰𝟑 . 𝐛∗3 = ∑ 𝑥𝑗 𝐛𝑗 + ⌊ ∗ ∗ ⌉ 𝐛3 + 𝑡3 (𝐛∗3 + ∑ 𝜇3,𝑖 𝐛∗𝑖 ) ⇔ 𝐛3 . 𝐛3 𝑖=1

𝑗=1

𝐰3 −

𝐰𝟑 . 𝐛∗3 (⌊ ∗ ∗ ⌉ 𝐛3 𝐛3 . 𝐛3

2

2

+ 𝑡3 𝐛3 ) = ∑ 𝑥𝑗 𝐛𝑗 + ∑ 𝑡3 𝜇3,𝑖 𝐛∗𝑖 . 𝑗=1

(11)

𝑖=1

2. Definisikan 𝐰𝟑 . 𝐛∗3 𝐰2 = 𝐰3 − (⌊ ∗ ∗ ⌉ 𝐛3 + 𝑡3 𝐛∗3 ). 𝐛3 . 𝐛3 Dari persamaan (11) dan karena 〈{𝐛1 , 𝐛2 }〉 = 〈{𝐛1∗ , 𝐛∗2 }〉, maka 𝐰2 ∈ 〈{𝐛1 , 𝐛2 }〉 dengan tepat satu (𝑥1 , 𝑥2 ) ∈ ℝ2 sehingga 𝐰2 = 𝑥1 𝐛1 + 𝑥2 𝐛2 dan berdasarkan Lema 4.2, dapat dituliskan 𝐰𝟐 . 𝐛∗2 𝐰2 = 𝑥1 𝐛1 + ∗ ∗ 𝐛2 𝐛2 . 𝐛2 𝐰𝟐 . 𝐛∗2 = 𝑥1 𝐛1 + (⌊ ∗ ∗ ⌉ + 𝑡2 ) 𝐛2 𝐛 2 . 𝐛2 1 1 dan dalam hal ini, − 2 ≤ 𝑡2 < 2. Selanjutnya, 𝐰𝟐 . 𝐛∗2 𝐰2 = 𝑥1 𝐛1 + ⌊ ∗ ∗ ⌉ 𝐛2 + 𝑡2 𝐛2 𝐛2 . 𝐛 2 𝐰𝟐 . 𝐛∗2 = 𝑥1 𝐛1 + ⌊ ∗ ∗ ⌉ 𝐛2 + 𝑡2 (𝐛∗2 + 𝜇2,1 𝐛1∗ ) ⇔ 𝐛2 . 𝐛 2 ∗ 𝐰𝟐 . 𝐛2 𝐰2 − (⌊ ∗ ∗ ⌉ 𝐛2 + 𝑡2 𝐛∗2 ) = 𝑥1 𝐛1 + 𝑡2 𝜇2,1 𝐛1∗ . 𝐛2 . 𝐛2 3. Definisikan

(12)

22 𝐰𝟐 . 𝐛∗2 𝐰1 = 𝐰2 − (⌊ ∗ ∗ ⌉ 𝐛2 + 𝑡2 𝐛∗2 ). 𝐛2 . 𝐛2 Dari persamaan (12), maka 𝐰1 ∈ 〈{𝐛1 }〉 dan ada 𝑥1 ∈ ℝ sehingga 𝐰1 = 𝑥1 𝐛1. Berdasaran Lema 4.2 dapat dituliskan 𝐰𝟏 . 𝐛1∗ 𝐰𝟏 . 𝐛1∗ 𝐰1 = ⌊ ∗ ∗ ⌉ 𝐛1 = (⌊ ∗ ∗ ⌉ + 𝑡1 𝐛1∗ ) 𝐛1 . 𝐛1 𝐛1 . 𝐛1 1 1 dan dalam hal ini, − 2 ≤ 𝑡1 < 2. Maka 𝐰=𝐯+𝐭 dimana 𝐰𝟏 . 𝐛1∗ 𝐰𝟐 . 𝐛∗2 𝐰𝟑 . 𝐛∗3 𝐯 = ⌊ ∗ ∗ ⌉ 𝐛1 + ⌊ ∗ ∗ ⌉ 𝐛2 + ⌊ ∗ ∗ ⌉ 𝐛3 𝐛1 . 𝐛1 𝐛2 . 𝐛2 𝐛3 . 𝐛3 dan 𝐭 = 𝑡1 𝐛1∗ + 𝑡2 𝐛∗2 + 𝑡3 𝐛∗3 . Dengan mudah dilihat bahwa 𝐯 ∈ ℒ(ℬ) dan 𝐭 ∈ 𝒞(ℬ ∗ ). Bukti lengkap. ∎ Bukti dari proposisi sekaligus merupakan bukti kebenaran dari algoritme berikut. Algoritme 4.1 Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ) dan 𝐰 ∈ 〈ℬ〉. Output: Vektor latis 𝐯 ∈ ℒ(ℬ) dan 𝐭 ∈ 𝒞(ℬ ∗ ). 1. Dengan algoritme Gram-Schmidt, hitung [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] dengan menggunakan input ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ]. 2. Inisialisasi 𝐯 ≔ 𝟎 dan 𝐭 ≔ 𝟎. 3. Untuk 𝑖 = 𝑛, 𝑛 − 1, … ,1 hitung: 𝐰 .𝐛∗

a) 𝑥𝑖 ≔ 𝐛∗.𝐛𝑖∗ 𝑖

𝑖

b) 𝑣𝑖 ≔ ⌊𝑥𝑖 ⌉ c) 𝐯 ≔ 𝐯 + 𝑣𝑖 𝐛𝑖 d) 𝑡𝑖 ≔ 𝑥𝑖 − 𝑣𝑖 e) 𝐭 ≔ 𝒕 + 𝑡𝑖 𝐛∗𝑖 f) 𝑤 ≔ 𝑤 − (𝑣𝑖 𝐛𝑖 + 𝑡𝑖 𝐛∗𝑖 ) 4. return(𝐯 dan t). Algoritme 4.2 (Menentukan Vektor Terdekat) Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ) dan 𝐰 ∈ 〈ℬ〉. Output: Vektor latis 𝐯 ∈ ℒ(ℬ). 1. Dengan algoritme Gram-Schmidt, hitung [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] dengan menggunakan input ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ]. 2. Inisialisasi 𝐯 ≔ 𝟎. 3. Untuk 𝑖 = 𝑛, 𝑛 − 1, … ,1 hitung: 𝐰 .𝐛∗

a) 𝑥𝑖 ≔ 𝐛∗.𝐛𝑖∗ 𝑖

𝑖

b) 𝑣𝑖 ≔ ⌊𝑥𝑖 ⌉ c) 𝐯 ≔ 𝐯 + 𝑣𝑖 𝐛𝑖

23 d) 𝑡𝑖 ≔ 𝑥𝑖 − 𝑣𝑖 e) 𝑤 ≔ 𝑤 − (𝑣𝑖 𝐛𝑖 + 𝑡𝑖 𝐛∗𝑖 ) 4. return(𝐯). Akibat dari Proposisi 4.7 diberikan dalam teorema berikut ini. Teorema 4.3 Jika ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi Gram-Schmidt dari himpunan bebas linier ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] , maka ℬ dapat ditransformasikan menjadi ℬ ′ = [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ] yang juga merupakan basis untuk ℒ(ℬ) dan ℬ ∗ juga merupakan hasil ortogonalisasi Gram-Schmidt ℬ ′ . Dalam hal ini, 𝐛1∗ = 𝐛1′ 𝑗−1

𝐛𝑗∗

=

𝐛𝑗′

𝐛′𝑗 .𝐛∗𝑖

′ − ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 , 𝑖=1 1

′ ′ untuk 𝑗 = 2, 3, … , 𝑟 dengan 𝜇𝑗,𝑖 = 𝐛∗.𝐛∗ dan |𝜇𝑗,𝑖 | ≤ 2. 𝑖

𝑖

Bukti: Untuk memudahkan pemahaman, transformasi dari ℬ ke ℬ ′ dilakukan secara instruktif sebagai berikut 1. Definisikan 𝐛1′ = 𝐛1 . Dalam hal ini, didapatkan subruang vektor berdimensi satu, yaitu 𝒮1 = 〈{𝐛1 }〉 = 〈{𝐛1′ }〉 = 〈{𝐛1∗ }〉. 2. Dari proses ortogonalisasi dari 𝐛2 ke 𝐛∗2 berlaku hubungan 𝐛∗2 = 𝐛2 − 𝐩1 𝐛 .𝐛∗

dengan 𝐩1 = 𝜇2,1 𝐛1∗ = 𝐛2∗ .𝐛1∗ 𝐛1∗ adalah vektor proyeksi dari 𝐛2 pada 𝒮1 . Hal 1

1

ini berarti 𝐩1 ∈ 𝒮1 . Dengan demikian, berdasarkan Proposisi 4.7 bahwa ada vektor latis 𝐯1 ∈ ℒ〈{𝐛1 }〉 dan vektor 𝐭1 ∈ 𝒞({𝐛1∗ }), sehingga 𝐩1 = 𝐯1 + 𝐭1 dan akibatnya diperoleh 𝐛∗2 = 𝐛2 − (𝐯1 + 𝐭1 ) = (𝐛2 − 𝐯1 ) − 𝐭1 . Kemudian dari persamaan ini dapat didefinisikan 𝐛′2 = 𝐛2 − 𝐯1 sehingga jelas (karena latis adalah grup) bahwa 𝐛′2 ∈ ℒ(ℬ), dan diperoleh persamaan 𝐛∗2 = 𝐛′2 − 𝐭1 . Hasil ini menunjukkan bahwa ortogonalisasi {𝐛1′ , 𝐛′2 } juga menghasilkan {𝐛1∗ , 𝐛∗2 } dengan vektor proyeksi 𝐛′2 pada 𝒮1 adalah 𝐛′2 . 𝐛1∗ ′ 𝐭1 = 𝜇2,1 𝐛1∗ = ∗ ∗ 𝐛1∗ 𝐛1 . 𝐛1 1 ′ ′ dan dalam hali ini 𝜇2,1 = 𝜇2,1 − ⌊𝜇2,1 ⌉ sehingga |𝜇2,1 | ≤ 2. Selanjutnya untuk menghitung 𝐛′2 berarti cukup menghitung 𝐯1 dengan menggunakan Algoritme 4.2 dan 𝐛′3 = 𝐛2 − 𝐯1 .

24 Sebelum ke langkah berikutnya, dinotasikan dahulu subruang vektor berdimensi dua yaitu 𝒮1 = 〈{𝐛1 , 𝐛2 }〉 = 〈{𝐛1′ , 𝐛′2 }〉 = 〈{𝐛1∗ , 𝐛∗2 }〉. 3. Dari proses ortogonalisasi dari berlaku hubungan 𝐛∗3 = 𝐛3 − 𝐩2 𝐛 .𝐛∗

𝐛 .𝐛∗

dengan 𝐩2 = 𝜇3,1 𝐛1∗ + 𝜇3,2 𝐛∗2 = 𝐛3∗ .𝐛1∗ 𝐛1∗ + 𝐛3∗ .𝐛2∗ 𝐛∗2 adalah vektor proyeksi 1

1

2

2

dari 𝐛3 pada 𝒮2 . Hal ini berarti 𝐩2 ∈ 𝒮2 . Dengan demikian, berdasarkan Proposisi 4.7 bahwa ada vektor latis 𝐯2 ∈ ℒ〈{𝐛1 , 𝐛2 }〉 dan vektor 𝐭 2 ∈ 𝒞({𝐛1∗ , 𝐛∗2 }) sehingga 𝐩2 = 𝐯2 + 𝐭 2 dan akibatnya diperoleh 𝐛∗3 = 𝐛3 − (𝐯2 + 𝐭 2 ) = (𝐛3 − 𝐯2 ) − 𝐭 2 . Kemudian dari persamaan ini dapat didefinisikan 𝐛′3 = 𝐛3 − 𝐯2 sehingga jelas (karena latis adalah grup) bahwa 𝐛′3 ∈ ℒ(ℬ), dan diperoleh persamaan 𝐛∗3 = 𝐛′3 − 𝐭 2 . Hasil ini menunjukkan bahwa ortogonalisasi 𝐛′3 juga menghasilkan 𝐛∗3 dengan vektor proyeksi 𝐛′3 pada 𝒮2 adalah 𝐛′3 . 𝐛1∗ ∗ 𝐛′3 . 𝐛∗2 ∗ ′ ∗ ′ ∗ 𝐭 2 = 𝜇3,1 𝐛1 + 𝜇3,2 𝐛2 = ∗ ∗ 𝐛1 + ∗ ∗ 𝐛2 𝐛1 . 𝐛1 𝐛2 . 𝐛2 dan dalam hali ini untuk 𝑖 = 1, 2 berlaku 1 ′ ′ 𝜇3,𝑖 = 𝜇3,𝑖 − ⌊𝜇3,𝑖 ⌉ sehingga |𝜇3,1 | < 2. Selanjutnya untuk menghitung 𝐛′3 berarti cukup menghitung 𝐯2 dengan menggunakan Algoritme 4.2 dan 𝐛′3 = 𝐛3 − 𝐯2 . Demikian seterusnya, dari Langkah 3 tersebut secara rekursif bila dilanjutkan sampai ke Langkah ke-n untuk memperoleh basis ℬ ′ hasil transformasi dari basis latis ℬ. Bukti lengkap. ∎ Perhatikan bahwa makna geometrik dari transformasi ℬ ke ℬ ′ dalam Teorema 4.3 beserta buktinya adalah memperkecil panjang vektor basis yaitu 𝑗 = 1, 2, … , 𝑛 berlaku ‖𝐛𝑗 ‖ ≥ ‖𝐛𝑗′ ‖. Hal ini terlihat dari vektor proyeksi 𝐩𝑖−1 , hasil proyeksi dari 𝐛𝑖 ke subruang 𝒮𝑖−1 untuk 𝑖 = 1, 2, … , 𝑛 ditransformasikan ke vektor proyeksi 𝐭 𝑖−1 , hasil proyeksi dari 𝐛′𝑖 ke subruang 𝒮𝑖−1 . Jika 𝐩𝑖−1 ∈ ∗ }), maka 𝐛𝑖 = 𝐛′𝑖 tetapi jika 𝐩𝑖−1 ∉ 𝒞({𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑖−1 }), maka 𝒞({𝐛1∗ , 𝐛∗2 , … , 𝐛𝑖−1 𝐛𝑖 bias ditransformasikan 𝐛′𝑖 dengan vektor proyeksi pada 𝒮𝑖−1 adalah 𝐭 ∈ 𝒞({𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑖−1 }) sehingga ‖𝐛𝑖 ‖ ≥ ‖𝐛′𝑖 ‖ . Dengan demikian, Teorema 4.3 beserta buktinya merupakan landasan teori yang digunakan untuk menyusun algoritme reduksi ukuran dari algoritme LLL berikut ini. Algoritme 4.3 (Algoritme Reduksi Ukuran) Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ). Output: ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi GramSchmidt dari ℬ dan ℬ ′ = [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ] adalah hasil reduksi ukuran dari ℬ.

25 1. Inisialisasi 𝐛1∗ ≔ 𝐛1 dan 𝐛1′ = 𝐛1. 2. Untuk 𝑗 = 2, 3, … , 𝑛 hitung: a) 𝐩 ≔ 𝟎 b) Untuk 𝑗 = 1, 2, … , 𝑗 − 1 hitung 𝐛 .𝐛∗

i. 𝜇𝑗,𝑖 = 𝐛∗𝑗.𝐛∗𝑖 𝑖

𝑖

ii. 𝐩 ≔ 𝐩 + 𝜇𝑗,𝑖 𝐛𝑖 c) 𝐛𝑗∗ ≔ 𝐛𝑗 − 𝐩 d) Gunakan Algoritme 4.2 untuk menghitung vektor 𝐯 dengan ∗ ] serta 𝐩. input ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑗−1 ] dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛𝑗−1 ′ e) 𝐛𝑗 ≔ 𝐛𝑗 − 𝐯 3. return([𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] dan [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ]). Berikut ini langkah-langkah ilustratif penyusunan algoritme reduksi ukuran LLL yang sifatnya rekursif tanpa memanggil Algoritme 4.2. 1. Untuk 𝑗 = 1, definisikan langsung 𝐛1∗ = 𝐛1 dan 𝐛1′ = 𝐛1 . 2. Untuk 𝑗 = 2, perhatikan bahwa 𝐩1 = 𝜇2,1 𝐛1∗ , berdasarkan Algoritme 4.2 maka 𝐩 . 𝐛1∗ 𝐯1 = ⌊ ∗ ∗ ⌉ 𝐛1 = ⌊𝜇2,1 ⌉𝐛1 . 𝐛1 . 𝐛1 ∗ Jadi untuk menghitung 𝐛2 dan 𝐛′2 cukup menghitung dahulu 𝜇2,1 , kemudian 𝐛∗2 = 𝐛2 − 𝐩1 = 𝐛2 − 𝜇2,1 𝐛1∗ dan 𝐛′2 = 𝐛2 − 𝐯1 = 𝐛2 − ⌊𝜇2,1 ⌉𝐛1 . 3. Untuk 𝑗 = 3, perhatikan bahwa 𝐩2 = 𝜇3,1 𝐛1∗ + 𝜇3,2 𝐛∗2 , berdasarkan Algoritme 4.2 nyatakan 𝐯2 = 𝐯2,2 + 𝐯2,1 sehingga 𝐩2 . 𝐛∗2 𝐯2,2 = ⌊ ∗ ∗ ⌉ 𝐛2 = ⌊𝜇3,2 ⌉𝐛2 𝐛2 . 𝐛2 dan ′ (𝐩2 − ⌊𝜇3,2 ⌉𝐛2 − 𝜇3,2 𝐛∗2 )𝐛1∗ 𝐯2,1 = ⌊ ⌉ 𝐛1 𝐛1∗ . 𝐛1∗ = ⌊𝜇3,1 − ⌊𝜇3,2 ⌉(𝜇2,1 )⌉𝐛1 . Jadi untuk menghitung 𝐛∗3 dan 𝐛′3 dapat dilakukan secara rekursif sebagai berikut. a) Untuk 𝑖 = 2, hitung 𝜇3,2, kemudian 𝐛∗3 = 𝐛3 − 𝜇3,2 𝐛2 dan 𝐛′3 = 𝐛3 − 𝐯2,2 = 𝐛3 − ⌊𝜇3,2 ⌉𝐛2 b) Untuk 𝑖 = 1, hitung 𝜇3,1, kemudian 𝐛∗3 = 𝐛3 − 𝜇3,1 𝐛1 dan 𝐛′3 = 𝐛′3 − 𝐯2,1 = 𝐛′3 − ⌊𝜇3,1 − ⌊𝜇3,2 ⌉(𝜇2,1 )⌉𝐛1 .

26 4. Untuk 𝑗 = 4, perhatikan bahwa 𝐩3 = 𝜇4,1 𝐛1∗ + 𝜇4,2 𝐛∗2 + 𝜇4,3 𝐛∗3 berdasarkan Algoritme 4.2 nyatakan 𝐯3 = 𝐯3,3 + 𝐯3,2 + 𝐯3,1 sehingga (𝜇4,3 𝐛∗3 ). 𝐛∗3 𝐩3 . 𝐛∗3 𝐯3,3 = ⌊ ∗ ∗ ⌉ 𝐛3 = ⌊ ⌉ 𝐛3 = ⌊𝜇4,3 ⌉𝐛3 𝐛∗3 . 𝐛∗3 𝐛3 . 𝐛3 dan 𝐯3,2 = ⌊

′ (𝐩 − (⌊𝜇4,3 ⌉𝐛3 + 𝜇4,3 𝐛∗3 )) 𝐛∗2

𝐛∗2 . 𝐛∗2

⌉ 𝐛2

= ⌊𝜇4,2 − ⌊𝜇4,3 ⌉(𝜇3,2 )⌉𝐛2 𝐯3,1 = ⌊

′ ′ (𝐩 − (⌊𝜇4,3 ⌉𝐛3 + 𝜇4,3 𝐛∗3 ) − (⌊𝜇4,2 ⌉𝐛2 + 𝜇4,2 𝐛∗2 )) 𝐛1∗

𝐛1∗ . 𝐛1∗

⌉ 𝐛1

= ⌊𝜇4,1 − ⌊𝜇4,3 ⌉𝜇3,1 − ⌊𝜇4,2 ⌉𝜇2,1 ⌉𝐛1 . Jadi untuk menghitung 𝐛∗4 dan 𝐛′4 dapat dilakukan secara rekursif sebagai berikut. a) Untuk 𝑖 = 3, hitung 𝜇4,3, kemudian 𝐛∗4 = 𝐛4 − 𝜇4,3 𝐛∗3 dan 𝐛′4 = 𝐛4 − ⌊𝜇4,3 ⌉𝐛3 . b) Untuk 𝑖 = 2, hitung 𝜇4,2, kemudian 𝐛∗4 = 𝐛∗4 − 𝜇4,2 𝐛∗2 dan 𝐛′4 = 𝐛′4 − ⌊𝜇4,2 − ⌊𝜇4,3 ⌉(𝜇3,2 )⌉𝐛2 . c) Untuk 𝑖 = 1, hitung 𝜇4,1, kemudian 𝐛∗4 = 𝐛∗4 − 𝜇4,1 𝐛1∗ dan 𝐛′4 = 𝐛′4 − ⌊𝜇4,1 − ⌊𝜇4,3 ⌉𝜇3,1 − ⌊𝜇4,2 ⌉𝜇2,1 ⌉. Berdasarkan pola Langkah 4 tersebut, berikut ini diberikan algoritme reduksi ukuran yang sifatnya rekursif. Algoritme 4.4 (Reduksi Ukuran LLL) Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ). Output: ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi GramSchmidt dari ℬ dan ℬ ′ = [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ] adalah hasil reduksi ukuran dari ℬ. 1. 𝐛1∗ ≔ 𝐛1 2. 𝐛1′ = 𝐛1 𝐛 .𝐛∗ 3. 𝜇21 ≔ 𝐛2∗ .𝐛1∗ 1

1

4. 𝐛∗2 ≔ 𝐛1 − 𝜇21 𝐛1∗ 5. 𝐛′2 ≔ 𝐛2 − ⌊𝜇21 ⌉𝐛1 6. Untuk 𝑗 = 3,4, … , 𝑛 lakukan: a) 𝐛𝑗∗ ≔ 𝐛𝑗 b) 𝐛𝑗 ≔ 𝐛𝑗

27 𝐛 .𝐛∗𝑗−1

c) 𝜇𝑗,𝑗−1 ≔ 𝐛∗ 𝑗

∗ 𝑗−1 .𝐛𝑗−1

𝐛𝑗∗ 𝐛𝑗′

d) ≔ 𝐛𝑗 − 𝜇𝑗,𝑗−1 𝐛𝑗−1 e) ≔ 𝐛𝑗′ − 𝜇𝑗,𝑗−1 𝐛𝑗−1 f) Untuk 𝑖 = 𝑗 − 2, 𝑗 − 3, … , 1 lakukan: 𝐛 .𝐛∗

i. 𝜇𝑗,𝑖 = 𝐛∗𝑗.𝐛∗𝑖 𝑖

𝑖

ii. 𝐛𝑗∗ ≔ 𝐛𝑗 − 𝜇𝑗,𝑖 𝐛∗𝑖 iii. 𝑐 ≔ 𝜇𝑗,𝑖 iv. Untuk 𝑘 = 𝑖, 𝑖 + 1, … , 𝑗 − 2 lakukan: 𝑐 ≔ 𝑐 − ⌊𝜇𝑗,𝑘+1 ⌉𝜇𝑘+1,𝑖 ′ v. 𝐛𝑗 ≔ 𝐛𝑗′ − ⌊𝑐⌉𝐛𝑖 7. return([𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] dan [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ]). Berikut ini merupakan langkah-langkah ilustratif penyusunan algoritme reduksi ukuran LLL dengan menggunakan rumus rekursif yang lebih sederhana. 1. Untuk 𝑗 = 1 definisikan langsung 𝐛1∗ = 𝐛1 dan 𝐛1′ = 𝐛1 . 2. Untuk 𝑗 = 2, perhatikan bahwa 𝐩1 = 𝜇2,1 𝐛1∗ , berdasarkan Algoritme 4.2 maka 𝐩1 . 𝐛1∗ 𝐯1 = ⌊ ∗ ∗ ⌉ 𝐛1∗ = ⌊𝜇2,1 ⌉𝐛1∗ . 𝐛1 . 𝐛1 ∗ Jadi, untuk menghitung 𝐛2 dan 𝐛′2 , cukup menghitung dahulu 𝜇2,1 , kemudian 𝐛∗2 = 𝐛2 − 𝐩1 = 𝐛2 − 𝜇2,1 𝐛1∗ dan 𝐛′2 = 𝐛2 − 𝐯1 = 𝐛2 − ⌊𝜇2,1 ⌉𝐛1 . 3. Untuk 𝑗 = 3, dari uraian sebelumnya, 𝐛′3 = (𝐛3 − ⌊𝜇3,2 ⌉𝐛∗2 ) − ⌊𝜇3,1 − ⌊𝜇3,2 ⌉(𝜇2,1 )⌉𝐛1 (𝐛3 − ⌊𝜇3,2 ⌉𝐛2 ). 𝐛1∗ = (𝐛3 − ⌊𝜇3,2 ⌉𝐛∗2 ) − ⌊ ⌉ 𝐛1 𝐛1∗ . 𝐛1∗ =𝐱−𝐲 𝐱 = (𝐛3 − ⌊𝜇3,2 ⌉(𝐛′2 + ⌊𝜇2,1 ⌉𝐛1∗ )) (𝐛3 −⌊𝜇3,2 ⌉(𝐛′2 +⌊𝜇2,1 ⌉𝐛∗1 )).𝐛∗1

𝐲=⌊

𝐛∗1 .𝐛∗1

⌉ 𝐛1

𝐱 = 𝐛3 – ⌊𝜇3,2 ⌉𝐛′2 − ⌊𝜇3,2 ⌉⌊𝜇2,1 ⌉𝐛1∗ (𝐛3 – ⌊𝜇3,2 ⌉𝐛′2 − ⌊𝜇3,2 ⌉⌊𝜇2,1 ⌉𝐛1∗ ). 𝐛1∗ 𝐲=⌊ ⌉ 𝐛1 𝐛1∗ . 𝐛1∗ (𝐛3 – ⌊𝜇3,2 ⌉𝐛′2 . 𝐛1∗ ). 𝐛1∗ =⌊ − ⌊𝜇3,2 ⌉⌊𝜇2,1 ⌉⌉ 𝐛1 𝐛1∗ . 𝐛1∗ (𝐛3 – ⌊𝜇3,2 ⌉𝐛′2 . 𝐛1∗ ). 𝐛1∗ =⌊ 𝐛1 ⌉ − ⌊𝜇3,2 ⌉⌊𝜇2,1 ⌉𝐛1 . 𝐛1∗ . 𝐛1∗ Dengan demikian, diperoleh

28 (𝐛3 − ⌊𝜇3,2 ⌉𝐛2′ ). 𝐛1∗ ⌉ 𝐛1 . 𝐛1∗ . 𝐛1∗ Jadi untuk menghitung 𝐛∗3 dan 𝐛′3 , dapat dilakukan secara rekursif sebagai berikut. (a) Untuk 𝑖 = 2, hitung 𝜇3,2 kemudian 𝐛∗3 = 𝐛∗3 − 𝜇3,2 𝐛∗2 dan 𝐛′3 = 𝐛3 − ⌊𝜇3,2 ⌉𝐛′2 . (b) Untuk 𝑖 = 1, hitung 𝜇3,1 kemudian 𝐛∗3 = 𝐛∗3 − 𝜇3,1 𝐛1∗ dan 𝐛′3 . 𝐛1∗ 𝐛′3 = 𝐛′3 − ⌊ ∗ ∗ ⌉ 𝐛1′ . 𝐛1 . 𝐛1 Berdasarkan pola dari 3 langkah tersebut, berikut ini diberikan algoritme reduksi ukuran yang sifatnya rekursif. 𝐛′3 = (𝐛3 − ⌊𝜇3,2 ⌉𝐛′2 ) − ⌊

Algoritme 4.5 (Reduksi ukuran LLL) Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ). Output: ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi GramSchmidt dari ℬ dan ℬ ′ = [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ] adalah hasil reduksi ukuran dari ℬ. 1. 𝐛1∗ ≔ 𝐛1 2. 𝐛1′ = 𝐛1 3. Untuk 𝑗 = 2, 3, … , 𝑛 lakukan: a) Untuk 𝑖 = 𝑗 − 1, 𝑗 − 2, … ,1 lakukan: 𝐛 .𝐛∗

i. 𝜇𝑗,𝑖 ≔ 𝐛𝑗∗.𝐛𝑖∗ 𝑖

𝑖

ii. 𝐛𝑗∗ ≔ 𝐛𝑗∗ − 𝜇𝑗,𝑖 𝐛∗𝑖 𝐛′ .𝐛∗

′ iii. 𝜇𝑗,𝑖 ≔ 𝐛𝑗∗.𝐛𝑖∗ 𝑖

𝑖

′ iv. 𝐛𝑗′ ≔ 𝐛𝑗 − ⌊𝜇𝑗,𝑖 ⌉𝐛𝑖 ∗ ∗ ∗] 4. return([𝐛1 , 𝐛2 , … , 𝐛𝑛 dan [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ]).

Algoritme LLL dan Analisisnya Inti dari algoritme LLL adalah mentransformasikan basis latis ke basis latis ℬ yang tereduksi LLL sebagaimana dinyatakan dalam Definisi 4.11. Dengan demikian, hal pertama yang harus dilakukan adalah mereduksi ukuran dari ℬ dengan menggunakan algoritme reduksi ukuran. Kemudian, ketika ada indeks ke-𝑗 sehingga syarat kedua dari Definisi 4.11 tidak terpenuhi yaitu 2 2 2 2 2 ∗ ‖ , 𝛿‖𝜋𝑗 (𝐛𝑗 )‖ > ‖𝜋𝑗 (𝐛𝑗+1 )‖ ⟺ (𝛿 − (𝜇𝑗+1,𝑗 ) ) ‖𝐛𝑗∗ ‖ > ‖𝐛𝑗+1 maka urutan 𝐛𝑗 dan 𝐛𝑗+1 ditukar dan reduksi ukuran diulang. Jika ada beberapa pasang (𝐛𝑗 , 𝐛𝑗+1 ) yang tidak memenuhi syarat kedua tersebut, tidak ada masalah mana yang harus dipilih untuk ditukar. Bahkan, dapat dipilih beberapa pasang vektor yang saling bebas untuk ditukar bersamaan, ini mengarah pada varian algoritme LLL paralel. Algoritme LLL aslinya pasangan nilai yang dipilih adalah nilai 𝑗 terkecil. Berikut ini diberikan secara garis besar deskripsi algoritme LLL. ′

29 1. (Langkah Reduksi Ukuran) terapkan algoritme reduksi ukuran pada ℬ. 2. (Langkah Penukaran) jika ada 𝑗 ∈ {2, 3, … , 𝑛} sehingga 2 2 2 ∗ (𝛿 − (𝜇𝑗,𝑗−1 ) ) ‖𝐛𝑗−1 ‖ > ‖𝐛𝑗∗ ‖ maka tukar 𝐛𝑗−1 dan 𝐛𝑗 , kemudian kembali ke Langkah 1. 3. Jika tidak, algoritme selesai. Sedangkan bentuk praktis algoritme LLL diberikan berikut ini. Algoritme 4.6 1 Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ) dan < 𝛿 < 1. 4 Output: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] adalah adalah basis tereduksi LLL untuk ℒ(ℬ) dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi Gram-Schmidt dari ℬ. 1. 𝐛1∗ ≔ 𝐛1 2. 𝑗 ≔ 2 3. Reduksi Ukuran. Ketika 𝑗 ≤ 𝑛, lakukan: (a) 𝐛𝑗∗ ≔ 𝐛𝑗 (b) Untuk 𝑖 = 𝑗 − 1, 𝑗 − 2, … ,1 lakukan: 𝐛 .𝐛∗

i. 𝜇𝑗,𝑖 ≔ 𝐛𝑗∗.𝐛𝑖∗ 𝑖

𝑖

ii. 𝐛𝑗∗ ≔ 𝐛𝑗∗ − 𝜇𝑗,𝑖 𝐛∗𝑖 iii. 𝐛𝑗 ≔ 𝐛𝑗 − ⌊𝜇𝑗,𝑖 ⌉𝐛𝑖 2

2

2

∗ (c) Penukaran. Jika (𝛿 − (𝜇𝑗,𝑗−1 ) ) ‖𝐛𝑗−1 ‖ > ‖𝐛𝑗∗ ‖ maka i. Jika 𝑗 = 2, Tukar 𝐛1 dan 𝐛2 𝐛1∗ ≔ 𝐛2 ii. Jika 𝑗 > 2, Tukar 𝐛𝑗−1 dan 𝐛𝑗 𝑗 ≔𝑗−1 Selainnya, 𝑗 ≔ 𝑗 + 1 4. return([𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] dan [𝐛1′ , 𝐛′2 , … , 𝐛′𝑛 ]).

Membatasi banyaknya iterasi Diasumsikan dahulu bahwa basis latisnya adalah bilangan bulat, artinya ℬ ∈ ℤ𝑛 . Kemudian, dapat diamati bahwa algoritme LLL cepat selesai jika tidak terlalu banyak terjadinya iterasi yang diindikasikan di dalam langkah penukaran. Oleh karena itu, hal pertama yang perlu diperhatikan dalam menganalisis algoritme LLL adalah seberapa besar jumlah maksimum terjadinya penukaran. Dengan demikian, perlu didefinisikan suatu bilangan bulat positif yang terkait dengan matriks basis B berikut ini. Ingat kembali determinan latis sebagai berikut. 𝑗 det (ℒ([𝐛1 , 𝐛2 , … , 𝐛𝑗 ])) = ∏𝑖=1‖𝐛∗𝑖 ‖ ⇔ det (ℒ(ℬ𝑗 )) = √det(𝐁𝑗𝑇 𝐁𝑗 ),

dimana matriks 𝐁𝑗 = [𝐛1 𝐛2 … 𝐛𝑗 ].

30 Dari asumsi 𝐁𝑗 adalah matriks bilangan bulat, jelas bahwa 2

[det (ℒ(𝐁𝒋 ))] ∈ ℤ. Dengan demikian, dapat didefinisikan bilangan bulat positif 𝒟 yang terkait dengan matriks basis B yaitu 𝑛

2

𝑛

𝒟 = ∏ [det (ℒ([𝐛1 , 𝐛2 , … , 𝐛𝑗 ]))] = ∏ [det (ℒ(𝐁𝒋 ))] 𝑗=1

2

𝑗=1

dan berlaku sifat dalam proposisi berikut ini. Proposisi 4.8 Langkah reduksi ukuran tidak mengubah nilai 𝒟, tetapi setiap terjadi penukaran, mengakibatkan nilai 𝒟 menurun, dengan faktor 𝛿. Bukti: Berdasarkan Teorema 4.3, perhatikan dahulu bahwa langkah reduksi ukuran tidak dapat mengubah nilai 𝒟 . Dengan demikian, tinggal ditunjukkan bahwa setiap terjadi pertukaran, nilai 𝒟 menurun dengan faktor 𝛿 . Misalkan terjadi penukaran 𝐛𝑗 dan 𝐛𝑗+1 , misalkan pula bilangan bulat positif 𝒟 terkait dengan B sebelum terjadinya penukaran, dan 𝒟 ′ terkait dengan 𝐁 ′ setelah 𝐛𝑗 dan 𝐛𝑗+1 ditukar. Perhatikan bahwa, 𝑖 < 𝑗 maka basis [𝐛1 , 𝐛2 , … , 𝐛𝑖 ] tidak berubah oleh terjadinya penukaran sehingga jelas bahwa 2 2 [det(ℒ(𝐁𝒊 ))] = [det(ℒ(𝐁′𝒊 ))] . Ketika 𝑖 > 𝑗 maka basis [𝐛1 , 𝐛2 , … , 𝐛𝑖 ], vektor 𝐛𝑗 dan 𝐛𝑗+1 ditukar (menukar sepasang vektor kolom pada 𝐁1) sehingga 2 2 ℒ(𝐁𝑖 ) = ℒ(𝐁′𝑖 ) ⇒ [det(ℒ(𝐁𝒊 ))] = [det(ℒ(𝐁′𝒊 ))] . Di lain pihak, untuk 𝑖 = 𝑗 maka basis 𝐁𝑗 = [𝐛1 , 𝐛2 , … , 𝐛𝑗−1 , 𝐛𝑗 ] berubah menjadi 𝐁𝑗′ = [𝐛1 , 𝐛2 , … , 𝐛𝑗−1 , 𝐛𝑗+1 ] sehingga 𝑗

𝑗−1 2 ∗ 2 [det (ℒ(𝐁𝑗 ))] = ∏‖𝐛𝑖 ‖ = (∏‖𝐛∗𝑖 ‖2 ) (‖𝐛𝑗∗ ‖ ). 𝑖=1 𝑖=1 2 2 2 ∗ syarat pertukaran (𝛿 − (𝜇𝑗+1,𝑗 ) ) ‖𝐛𝑗∗ ‖ > ‖𝐛𝑗+1 ‖ maka berlaku 𝑗−1 2 1 2 ∗ [det (ℒ(𝐁𝑗 ))] > (∏‖𝐛∗𝑖 ‖2 ) ( 2 ) ‖𝐛𝑗+1 ‖ (𝛿 − (𝜇𝑗+1,𝑗 ) ) 𝑖=1 𝑗−1 1 2 ∗ ∗ 2 ‖ ) ‖𝐛𝑗+1 >( ‖ 2 ) (∏‖𝐛𝑖 (𝛿 − (𝜇𝑗+1,𝑗 ) ) 𝑖=1 2 [det (ℒ(𝐁 ′ 𝒋 ))] 2 1 > [det (ℒ(𝐁 ′ 𝒋 ))] ⇔ 2 < 𝛿. 𝛿 2

Karena

[det (ℒ(𝐁𝒋 ))]

Akhirnya,

31 2

2

𝑛 ′ [det (ℒ(𝐁 ′ 𝒋 ))] 𝐷′ ∏𝑗=1 [det (ℒ(𝐁 𝒋 ))] = 2 = 2 <𝛿 𝒟 ∏𝑛 [det (ℒ(𝐁𝒋 ))] 𝑗=1 [det (ℒ(𝐁 𝒋 ))] 1

1

𝒟 ′ < 𝛿. 𝒟 ⇔ 𝒟 > 𝛿 𝒟 ′ ⇒ 𝒟 ≥ 𝛿 𝒟 ′ . Berdasarkan proposisi tersebut, sekarang dimisalkan 𝑘 menyatakan iterasi dalam algoritme LLL dan 𝒟 (𝑗) 𝐷′ pada iterasi ke−𝑗 maka 𝒟 ≥ 𝛿 −1 𝒟 (1) ≥ 𝛿 −2 𝒟 (2) ≥ ⋯ ≥ 𝛿 −𝑘 𝒟 (𝑘) . Karena untuk setiap 𝑗 nilai 𝒟 (𝑗) adalah bilangan bulat positif, maka 1 𝑘 𝒟 (𝑘) ≥ 1 ⇒ 𝒟 ≥ 𝛿 −𝑘 ⇔ 𝒟 ≥ ( ) ⇔ 𝑘 ≤ log 1 𝒟. 𝛿 𝛿 Hal ini menunjukkan bahwa banyaknya iterasi terbatas ke atas pada fungsi yang nilainya bergantung pada nilai awal 𝒟. Karena menghitung 𝑛

𝒟=

𝑗

∏ (∏‖𝐛∗𝑖 ‖2 ) 𝑖=1 𝑗=1

𝑗

𝑛

≤ ∏ (∏‖𝐛𝑖 ‖2 ) 𝑖=1

𝑗=1

membutuhkan waktur polinomial, maka dapat disimpulkan banyaknya iterasi dalam algoritme LLL juga terbatas secara polinomial dalam ukuran input. Bukti lengkap. ∎ Membatasi besarnya bilangan yang terlibat Telah ditunjukkan bahwa banyaknya iterasi dalam algoritme LLL terbatas secara polinomial dalam ukuran input. Namun demikian, hal ini belum cukup untuk menyimpulkan bahwa algoritme LLL mempunyai running time polinomial. Masih perlu untuk memastikan bahwa ukuran bilangan yang dilibatkan dalam keseluruhan komputasi juga terbatas secara polinomial. Algoritme LLL menggunakan aritmatika bilangan rasional, sehingga perlu membatasi baik presisinya maupun besarannya. Perhatikan bahwa langkah ke-𝑗 dari proses Gram-Schmidt dapat dirumuskan ulang sebagai 𝑗−1

𝐛𝑗∗ = 𝐛𝑗 + ∑ 𝜐𝑗𝑖 𝐛𝑖

(13)

𝑖=1

untuk suatu 𝜐𝑗𝑖 ∈ ℝ. Karena 𝐛𝑗∗ ortogonal ke 𝐛𝑡 untuk setiap 𝑡 < 𝑗 maka diperoleh 𝑗−1

𝐛𝑡 . 𝐛𝑗∗ = ( 𝐛𝑡 . 𝐛𝑗 ) + 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 𝑗−1

𝑖=1

⇔ 𝟎 = ( 𝐛𝑡 . 𝐛𝑗 ) + 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 𝑗−1

𝑖=1

⇔ 𝐛𝑡 . ∑ 𝜐𝑗𝑖 𝐛𝑖 = −( 𝐛𝑡 . 𝐛𝑗 ).

(14)

𝑖=1

Untuk 𝑡 = 1, 2, … , 𝑗 − 1, persamaan tersebut dapat dituliskan dalam bentuk matriks

32 𝑗−1

𝐛1 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 𝑗−1

𝐛2 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 ⋮ 𝑗−1 (𝐛𝑗−1 . ∑𝑖=1 𝜐𝑗𝑖 𝐛𝑖 )

𝐛1 . 𝐛𝑗 𝐛2 . 𝐛𝑗 =− . ⋮ (𝐛𝑗−1 . 𝐛𝑗 )

Jika didefinisikan matriks 𝐛2

𝐁𝑗−1 = (𝐛1

…

𝐛𝑗−1 )

dan matriks

𝜐𝑗1 𝜐𝑗2 𝐮𝑗 = ( ⋮ ), 𝜐𝑗,𝑗−1 maka persamaan (14) dapat ditulis sebagai 𝐛1 . (𝐁𝑗−1 𝐮𝑗 ) 𝐛1 . 𝐛𝑗 𝐛2 . (𝐁𝑗−1 𝐮𝑗 ) = − 𝐛2 . 𝐛𝑗 ⋮ ⋮ (𝐛𝑗−1 . 𝐛𝑗 ) (𝐛𝑗−1 . (𝐁𝑗−1 𝐮𝑗 )) 𝑇 𝑇 ⇔ 𝐁𝑗−1 (𝐁𝑗−1 𝐮𝑗 ) = −𝐁𝑗−1 𝐛𝑗 𝑇 𝑇 ⇔ (𝐁𝑗−1 𝐁𝑗−1 )𝐮𝑗 = −𝐁𝑗−1 𝐛𝑗 . (15) 𝑇 Persamaan (15) merupakan SPL dengan matriks koefisien 𝐁𝑗−1 𝐁𝑗−1 dan 𝑇 vektor −𝐁𝑗−1 𝐛𝑗 adalah bilangan bulat. Dengan demikian, untuk 𝑠 = 1, 2, … , 𝑗 − 1, berdasarkan aturan Cramer diperoleh ℤ ℤ 𝜐𝑗𝑠 ∈ = . 𝑇 det(𝐁𝑗−1 𝐁𝑗−1 ) det (ℒ(ℬ ))2 𝑗−1 Hasil ini akan digunakan untuk memberi batas pada koefisien 𝜇𝑗,𝑖 . Perhatikan lagi definisi 𝒟 sebagai 𝑛

2

𝒟 = ∏ [det (ℒ(𝐁 𝒋 ))] 𝑗=1

𝑛

𝑛

∏(𝐁𝑗𝑇 𝐁𝑗 ) 𝑗=1

⇔ 𝒟 = ∏ 𝒟𝑗 𝑗=1

𝑇 dengan 𝒟𝑗 = det(𝐁𝑗𝑇 𝐁𝑗 ) . Kemudian, dihitung = det(𝐁𝑗−1 𝐁𝑗−1 ) dan dikalikan kedua ruas dari persamaan (13) maka diperoleh 𝑗−1

𝒟𝑗−1 𝐛∗𝑗

= 𝒟𝑗−1 𝐛𝑗 + ∑(𝒟𝑗−1 𝜐𝑗𝑖 ) 𝐛𝑖 𝑖=1

dan karena 𝒟𝑗−1 𝜐𝑗𝑖 ∈ ℤ maka 𝒟𝑗−1 𝐛∗𝑗 ∈ ℤ𝑛 . Ini berarti semua penyebut dari bilangan dalam vektor 𝐛𝑗∗ adalah faktor 𝒟𝑗−1 . Sekarang dihitung 𝐛𝑗 . 𝐛∗𝑖 𝒟𝑖−1 (𝐛𝑗 . 𝐛∗𝑖 ) 𝐛𝑗 (𝒟𝑖−1 . 𝐛∗𝑖 ) ℤ 𝜇𝑗𝑖 = ∗ ∗ = = ∈ . ∗ ∗ 𝟐 𝐛𝑖 . 𝐛𝑖 𝒟𝑖−1 (𝐛𝑖 . 𝐛𝑖 ) (∏𝑖−1 ‖𝐛 ∗ ‖𝟐 )‖𝐛∗ ‖ 𝒟𝑖 𝑠=1

𝑠

𝑖

Hasil ini menunjukkan bahwa penyebut dari 𝜇𝑗𝑖 harus membagi 𝒟𝑖 . Oleh karena itu, bilangan rasional yang ada didalam vektor 𝑗−1

𝐛𝑗∗ = 𝐛𝑗 − ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 𝑖=1

33 dan 𝜇𝑗,𝑖 dapat dituliskan dengan penyebut 𝒟 (ingat bahwa 𝒟 adalah kelipatan setiap 𝒟𝑖 ). 1 Karena |𝜇𝑗,𝑖 | ≤ 2 , maka ukuran bit yang digunakan terbatas pada log 𝒟 . Kemudian dari 𝑗

𝒟𝑗 = ∏‖𝐛∗𝑠 ‖𝟐 𝑠=1

diperoleh 𝟐

‖𝐛𝑗∗ ‖ =

𝒟𝑗 ≤ 𝒟𝑗 ≤ 𝒟 𝒟𝑗−1

akhirnya 𝑗−1

1 𝟐 2 + ∑ 𝜇𝑗,𝑖 ‖𝐛𝑗∗ ‖ ≤ 𝒟 + (𝑗 − 1) ( ) 𝒟 4 𝑖=1 𝑛 ≤ 𝒟 + ( ) 𝒟 ≤ 𝒟. 4 Dengan demikian semua pembilang dan penyebut dari bilangan rasional yang terjadi di dalam eksekusi algoritme LLL mempunyai ukuran bit yang terbatas secara polinomial dalam log 𝒟. 𝟐

‖𝐛𝑗 ‖ =

𝟐 ‖𝐛𝑗∗ ‖

Memperbaiki algoritme LLL Seperti terlihat pada analisis algoritmenya, kecepatan dan ketepatan hasil (output) algoritme LLL lebih dominan ditentukan oleh banyaknya langkah penukaran yang terjadi. Memberi nilai 𝛿 yang lebih besar, algoritme akan mengeluarkan hasil yang lebih baik, tetapi ini harus dibayar dengan meningkatnya banyaknya langkah penukaran (menurunnya kecepatan), demikian pula sebaliknya. Jadi, yang dimaksud dengan memperbaiki algoritme LLL umumnya adalah bagaimana meningkatkan kecepatan dengan keluaran yang lebih baik. Pada bagian ini akan dibahas varian yang pertama dari algoritme LLL yaitu metode penyisipan dalam (deep insertion). Algoritme LLL Penyisipan Dalam Jika di dalam algoritme LLL, uji terjadinya penukaran secara terurut langkah demi langkah (𝐛𝑗 dengan 𝐛𝑗−1 ) maka dengan metode penyisipan dalam (Deep Insertion), uji terjadinya penukaran bisa dilakukan langsung ke dalam (𝐛𝑗 dengan 𝐛𝑘 untuk 𝑘 = 1,2, … , 𝑗 − 1. Hal ini dijelaskan berikut ini. Misalkan pada suatu tahap komputasi diperoleh basis latis terurut seperti ini 𝐛1 , 𝐛2 , … , 𝐛𝑘−1 , 𝐛𝑘 , 𝐛𝑘+1 , … , 𝐛𝑗−1 , 𝐛𝑗 , 𝐛𝑗+1 , … , 𝐛𝑛 , maka prosedur ortogonalisasi Gram-Schmidt dirumuskan sebagai 𝑗−1

𝐛𝑗∗ = 𝐛𝑗 − ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 untuk 𝑗 = 1,2, … , 𝑛 𝑖=1 𝑗−1

⇔ 𝐛𝑗 = 𝐛𝑗∗ + ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 untuk 𝑗 = 1,2, … , 𝑛. 𝑖=1

34 Kemudian, karena 𝐛1∗ , 𝐛∗2 , … , 𝐛𝑗∗ ortogonal, diperoleh 𝑗−1 2

‖𝐛𝑗 ‖ =

2 ‖𝐛𝑗∗ ‖

2 ‖𝐛∗𝑖 ‖2 . + ∑ 𝜇𝑗,𝑖 𝑖=1

Jika disisipkan 𝐛𝑗 ke 𝐛𝑘 , maka basis latis terurut menjadi 𝐛1 , 𝐛2 , … , 𝐛𝑘−1 , 𝐛𝑗 , 𝐛𝑘 , 𝐛𝑘+1 , … , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 . Dengan vektor-vektor 𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑘−1 tetap, sedangkan ortogonalisasi Gram-Schmidt untuk 𝐛𝑘 diperbaharui yaitu 𝑘−1

̂ ∗𝑘 = 𝐛𝑗 − 𝐛

prosedur

𝑘−1

∑ 𝜇𝑗,𝑖 𝐛∗𝑖 𝑖=1

̂ ∗𝑘 + ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 , ⇔ 𝐛𝑗 = 𝐛 𝑖=1

kemudian 𝑘−1 2

‖𝐛𝑗 ‖ =

̂ ∗𝑘 ‖𝟐 ‖𝐛

+

𝑘−1

2 ∑ 𝜇𝑗,𝑖 𝑖=1

‖𝐛∗𝑖 ‖2

⇔

̂ ∗𝑘 ‖𝟐 ‖𝐛

2

2 ‖𝐛∗𝑖 ‖2 . = ‖𝐛𝑗 ‖ − ∑ 𝜇𝑗,𝑖

(16)

𝑖=1

Sekarang tinjau persamaan terakhir untuk kasus 𝑘 = 𝑗 − 1, maka 𝑗−2 𝟐 ∗ ̂ 𝑗−1 ‖𝐛 ‖

2

2 ‖𝐛∗𝑖 ‖2 = ‖𝐛𝑗 ‖ − ∑ 𝜇𝑗,𝑖 𝑖=1 𝑗−1

2

𝑗−2

2 ‖𝐛∗𝑖 ‖2 = ‖𝐛𝑗∗ − ∑ 𝜇𝑗,𝑖 𝐛∗𝑖 ‖ − ∑ 𝜇𝑗,𝑖 𝑖=1 𝑗−1

𝑖=1 𝑗−2

2

2 2 ‖𝐛∗𝑖 ‖2 − ∑ 𝜇𝑗,𝑖 ‖𝐛∗𝑖 ‖2 = ‖𝐛𝑗∗ ‖ ∑ 𝜇𝑗,𝑖 𝑖=1

𝑖=1

𝟐 2 𝟐 ∗ ∗ ̂ 𝑗−1 ‖𝐛 ‖ = ‖𝐛𝑗∗ ‖ + 𝜇𝑗,𝑗−1 ‖𝐛𝑗−1 ‖ . Hal ini menunjukkan bahwa untuk kasus 𝑘 = 𝑗 − 1 syarat penukaran metode penyisipan dalam sama dengan syarat penukaran algoritme LLL, yaitu jika 𝟐 𝟐 ∗ ∗ ̂ 𝑗−1 ‖𝐛 ‖ < 𝜹‖𝐛𝑗−1 ‖ , maka 𝐛𝑗 ditukar dengan 𝐛𝑗−1. Secara umum, ketika ditinjau

untuk nilai 𝑘 = 1,2,3, … , 𝑗 − 1 maka persamaan (16) diperoleh ̂ 1∗ ‖𝟐 = ‖𝐛𝑗 ‖𝟐 ‖𝐛 2 ̂ ∗2 ‖𝟐 = ‖𝐛𝑗 ‖𝟐 − 𝜇𝑗,1 ‖𝐛1∗ ‖𝟐 ‖𝐛 2 2 ̂ ∗3 ‖𝟐 = ‖𝐛𝑗 ‖𝟐 − 𝜇𝑗,1 ‖𝐛1∗ ‖𝟐 − 𝜇𝑗,2 ‖𝐛∗2 ‖𝟐 ‖𝐛 ⋮ 𝟐 𝟐 𝟐 2 2 2 ∗ ∗ ̂ 𝑗−1 ‖𝐛1∗ ‖𝟐 − 𝜇𝑗,2 ‖𝐛1∗ ‖𝟐 − ⋯ − 𝜇𝑗,𝑗−2 ‖𝐛 ‖ = ‖𝐛𝑗 ‖ − 𝜇𝑗,1 ‖𝐛𝑗−2 ‖ . Persamaan-persamaan tersebut dapat digunakan untuk menetapkan nilai 𝑘 ̂ ∗𝑘 ‖𝟐 < 𝜹‖𝐛∗𝑘 ‖𝟐 sehingga 𝐛𝑗 dapat disisipkan ke 𝐛𝑘 . Dalam hal ini terjadi ketika ‖𝐛 𝟐

∗ ̂ 𝑗−1 dan yang menguntungkan adalah bahwa ‖𝐛 ‖ dapat dihitung secara rekursif dengan penjelasan sebagai berikut. Didefinisikan inisial 𝐶 = ‖𝐛𝑗 ‖ dan 𝑘 = 1, secara rekursif hitung 2 ‖𝐛∗𝑘 ‖𝟐 dan 𝑘 ≔ 𝑘 + 1 𝐶 = 𝐶 − 𝜇𝑗,𝑘 dan proses berhenti ketika ̂ ∗𝑘 ‖𝟐 < 𝛿‖𝐛∗𝑘 ‖𝟐 . 𝐶 < 𝛿‖𝐛∗𝑘 ‖𝟐 ⇔ ‖𝐛

35 Bentuk praktis algoritme LLL penyisipan dalam diberikan berikut ini. Algoritme 4.7 (Algoritme LLL penyisipan dalam) 1 Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ) dan 4 < 𝛿 < 1. Output: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] adalah adalah basis tereduksi LLL untuk ℒ(ℬ) dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi Gram-Schmidt dari ℬ. 1. 𝐛1∗ ≔ 𝐛1 2. 𝑗 ≔ 2 3. Reduksi Ukuran. Sementara 𝑗 ≤ 𝑛 hitung: (a) 𝐛𝑗∗ ≔ 𝐛𝑗 (b) Untuk 𝑖 = 𝑗 − 1, 𝑗 − 2, … ,1 hitung: i. 𝑁𝑖 ≔ 𝐛∗𝑖 . 𝐛∗𝑖 ii. 𝜇𝑗,𝑖 ≔

𝐛𝑗 .𝐛∗𝑖 𝑁𝑖

iii. 𝐛𝑗 = 𝐛𝑗 − ⌊𝜇𝑗,𝑖 ⌉𝐛𝑖 ∗ iv. 𝜇𝑗,𝑖 ≔

𝐛∗𝑗 .𝐛∗𝑖 𝑁𝑖

∗ ∗ v. 𝐛𝑗∗ ≔ 𝐛𝑗∗ − 𝜇𝑗,𝑖 𝐛𝑖 (c) Penyisipan Dalam Hitung 𝐶 = 𝐛𝑗 . 𝐛𝑗 Definisikan 𝑘 ≔ 1 Sementara 𝑘 < 𝑗, hitung: i. ℎ ≔ 𝐛∗𝑘 . 𝐛∗𝑘 ii. Jika 𝐶 < 𝛿ℎ, maka Jika 𝑘 = 1, maka (Sisipkan 𝐛𝑗 ke posisi-1): 𝐛𝑗 , 𝐛1 , 𝐛2 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 ∗ 𝐛1 ≔ 𝐛𝑗 Jika tidak, maka (Sisipkan 𝐛𝑗 ke posisi-k): 𝐛1 , 𝐛2 , … , 𝐛𝑘−1 , 𝐛𝑗 , 𝐛𝑘+1 , … , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 (Hitung vektor ortogonal pada posisi ke-k): 𝐛∗𝑘 ≔ 𝐛𝑗 Untuk 𝑖 ≔ 𝑘 − 1, 𝑘 − 2, … ,1 hitung 𝑁𝑖 ≔ 𝐛∗𝑖 . 𝐛∗𝑖 ∗ 𝜇𝑘,𝑖 ≔

𝐛∗𝑘 .𝐛∗𝑖 𝑁𝑖

∗ 𝐛∗𝑘 ≔ 𝐛∗𝑘 − 𝜇𝑘,𝑖 𝐛∗𝑖 Break (Stop loop) iii. Jika tidak, maka 𝑧 ≔ 𝐛𝑗 . 𝐛∗𝑘 𝑧2 𝐶≔𝐶− ℎ 𝑘 ≔𝑘+1 (d) 𝑗 ≔ 𝑘 + 1

36 4. return(ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ]). Algoritme Greedy SVP LLL Ide dasar metode greedy adalah sebagai berikut. Jika vektor terkecil sudah di posisi pertama, maka penyisipan hanya akan terjadi di posisi kedua atau lebih; jika dua vektor terkecil sudah di posisi pertama dan kedua, maka penyisipan hanya akan terjadi di posisi ketiga atau lebih, demikian juga seterusnya. Kemudian, semakin cepat diperoleh vektor-vektor terkecil secara terurut, maka algoritme semakin cepat selesai. Dengan ide dasar ini, diharapkan bahwa vektorvektor terkecil tersebut bisa diperoleh secara greedy. Algoritme pencarian vektor terpendek secara greedy yang akan dikonstruksi disebut algoritme greedy SVP LLL. Pada algoritme ini syarat penukaran (penyisipan) tidak didasarkan perbandingan vektor proyeksi pada komplemen ortogonal [𝐛1 , 𝐛2 , … , 𝐛𝑘−1 ]⊥ setelah reduksi ke-j(metode penyisipan dalam), melainkan penyisipan dilakukan murni dengan membandingkan panjang vektor latis 𝐛𝑗 dengan panjang vektor latis 𝐛𝑖 untuk 𝑖 = 1, 2,3 … , 𝑗 − 1Disamping itu, penyisipannya dilakukan secara greedy. Berikut ini secara garis besar cara kerja algoritmenya. 1. Untuk [𝐛1 ], definisikan 𝐛1∗ = 𝐛1, cari vektor 𝐛𝑗 hasil reduksi [𝐛1 ] dan [𝐛1∗ ] terhadap [𝐛2 , 𝐛3 , … , 𝐛𝑛 ] dengan panjang terkecil. Jika ‖𝐛𝑗 ‖ < ‖𝐛1 ‖ , sisipkan 𝐛𝑗 , 𝐛1 , 𝐛2 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 diperoleh 𝐛1 = 𝐛𝑗 yang baru dan proses diulang lagi. Tetapi jika ‖𝐛1 ‖ ≤ ‖𝐛𝑗 ‖ maka disisipkan 𝐛1 , 𝐛𝑗 , 𝐛2 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 , [𝐛 sehingga diperoleh 1 , 𝐛2 ] baru yang terurut dengan ukuran terkecil dalam barisan tersebut. Kemudian, hitung 𝐛∗2 dari input 𝐛2 dan 𝐛1∗ sehingga diperoleh barisan [𝐛1∗ , 𝐛∗2 ] dan lanjut ke Langkah 2. 2. Dari [𝐛1 , 𝐛2 ] dan [𝐛1∗ , 𝐛∗2 ] , cari vektor 𝐛𝑗 hasil reduksi [𝐛1 , 𝐛2 ] terhadap [𝐛3 , 𝐛4 , … , 𝐛𝑛 ] dengan panjang terkecil. Jika ‖𝐛𝑗 ‖ < ‖𝐛1 ‖, sisipkan 𝐛𝑗 , 𝐛1 , 𝐛2 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 atau jika ‖𝐛1 ‖ ≤ ‖𝐛𝑗 ‖ < ‖𝐛2 ‖, sisipkan 𝐛1 , 𝐛𝑗 , 𝐛2 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 kemudian kembali ke Langkah 1. Tetapi jika ‖𝐛2 ‖ ≤ ‖𝐛𝑗 ‖ disisipkan 𝐛1 , 𝐛2 , 𝐛𝑗 , 𝐛3 , 𝐛𝑗−1 , 𝐛𝑗+1 , … , 𝐛𝑛 , sehingga diperoleh [𝐛1 , 𝐛2 , 𝐛3 ] baru yang terurut dengan ukuran terkecil dalam barisan tersebut. Kemudian hitung 𝐛∗3 dari input 𝐛3 dan [𝐛1∗ , 𝐛∗2 ] sehingga diperoleh barisan [𝐛1∗ , 𝐛∗2 , 𝐛∗3 ] dan lanjut ke Langkah 3. 3. Secara umum, langkah ke-k dari [𝐛1 , 𝐛2 , … , 𝐛𝑘 ] dan [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑘 ], cari vektor 𝐛𝑗 sebagai vektor hasil reduksi [𝐛1 , 𝐛2 , … , 𝐛𝑘 ] terhadap [𝐛𝑘+1 , 𝐛𝑘+2 , … , 𝐛𝑛 ] dengan panjang terkecil. Kemudian disisipkan 𝐛𝑗 ke [𝐛1 , 𝐛2 , … , 𝐛𝑛 ]. Jika formasi penyisipan 𝐛𝑗 , 𝐛1 , 𝐛2 , … , 𝐛𝑘 atau 𝐛1 , 𝐛𝑗 , 𝐛2 , … , 𝐛𝑘 , maka kembali ke Langkah 1, dan jika format penyisipan

37 𝐛1 , 𝐛2 , … , 𝐛𝑖−1 , 𝐛𝑗 , 𝐛𝑖 , … , 𝐛𝑘 diperoleh [𝐛1 , 𝐛2 , … , 𝐛𝑖 ] yang baru, kemudian dari 𝐛𝑖 dan [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑖−1 ] hitung 𝐛∗𝑖 untuk mendapatkan [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑖 ] baru, maka kembali ke langkah i. tetapi jika formasi penyisipan 𝐛1 , 𝐛2 , … , 𝐛𝑘 , 𝐛𝑗 , maka diperoleh [𝐛1 , 𝐛2 , … , 𝐛𝑘+1 ] baru yang terurut dengan ukuran terkecil dalam barisan tersebut. Kemudian, hitung 𝐛∗𝑘+1 dari input 𝐛𝑘+1 dan [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑘 ] sehingga diperoleh barisan [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑘+1 ] dan lanjut ke langkah-(k+1). 4. Demikian seterusnya, dan proses berakhir ketika 𝑘 = 𝑛. Bentuk praktis algoritme greedy SVP LLL diberikan berikut ini. Algoritme 4.8 Input: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] basis untuk ℒ(ℬ). Output: ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] adalah adalah basis tereduksi LLL untuk ℒ(ℬ) dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ] adalah hasil proses ortogonalisasi Gram-Schmidt dari ℬ. 1. 𝐛1∗ ≔ 𝐛1 2. 𝑘 ≔ 1 3. Sementara 𝑘 < 𝑛 lakukan: 4. Inisialisasi [𝐛1 , … , 𝐛𝑘 ] dan [𝐛𝑘+1 , … , 𝐛𝑛 ] Sementara 𝑛 − 𝑘 lakukan: 5. 6. 𝐛𝑦 ≔ 𝐛𝑘+1 7. Untuk 𝑙 = 𝑘, 𝑘 − 1, … ,1 lakukan 8. 9. 10. 11. 12. 13. 14. 15.

𝜇𝑦,𝑙 ≔

𝐛𝑦 .𝐛∗𝑙 𝐛∗𝑙 .𝐛∗𝑙

𝐛𝑦 ≔ 𝐛𝑦 − ⌊𝜇𝑦,𝑙 ⌉𝐛𝑙 Hitung ‖𝐛𝑦 ‖ Definisikan 𝑖 ≔ 1 Untuk 𝑗 = 2, 3, … , 𝑛 − 𝑘 lakukan: Definisikan 𝐛𝑗 Untuk 𝑙 = 𝑘, 𝑘 − 1, … 1 lakukan 𝐛 .𝐛∗

𝜇𝑗,𝑙 ≔ 𝐛∗𝑗.𝐛∗𝑙 𝑙

16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28.

𝑙

𝐛𝑗 ≔ 𝐛𝑗 − ⌊𝜇𝑗,𝑙 ⌉𝐛𝑙 Hitung ‖𝐛𝑗 ‖ Jika ‖𝐛𝑗 ‖ < ‖𝐛𝑦 ‖ maka 𝐛𝑦 ≔ 𝐛𝑗 ‖𝐛𝑦 ‖ ≔ ‖𝐛𝑗 ‖ 𝑖≔𝑗 Definisikan [𝐛𝑘+2 , … , 𝐛𝑛 ] Definisikan 𝑚 ≔ 𝑛 − 𝑘 − 1 Definisikan 𝑏 ≔ 𝑘 + 1 Untuk 𝑧 = 1, 2, … , 𝑘 lakukan Hitung ‖𝐛𝑧 ‖ Jika ‖𝐛𝑦 ‖ < ‖𝐛𝑧 ‖ maka 𝑏 ≔ 𝑧 (Posisi vektor 𝐛𝑦 ditukar dengan posisi vektor 𝐛𝑧 )

38 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47.

Break (Stop loop) Jika posisi 𝐛𝑦 ≤ 𝐛𝑘 maka Jika 𝑏 = 1 maka Definisikan 𝑘 ≔ 1 𝐛𝑦 , 𝐛1 , 𝐛2 , … , 𝐛𝑘 𝐛𝑦 ≔ 𝐛1∗ Jika tidak, maka 𝐛1 , … , 𝐛𝑧−1 , 𝐛𝑦 , 𝐛𝑧+1 , … , 𝐛𝑘 Definisikan 𝐛𝑦 Untuk 𝑙 = 𝑘, 𝑘 − 1, … ,1 𝜇𝑦,𝑙 ≔

𝐛𝑦 .𝐛∗𝑙

𝐛∗𝑙 .𝐛∗𝑙 ≔ 𝐛∗𝑦 − 𝜇𝑦,𝑙 𝐛∗𝑙 Perbarui 𝐛∗𝑦 , 𝐛∗𝑧+1 , … , 𝐛∗𝑘

𝐛∗𝑦

Definisikan 𝑘 ≔ 𝑏 Break (Stop loop) Perbarui [𝐛1 , 𝐛2 , … , 𝐛𝑘 , 𝐛𝑦 ] Definiskan 𝐛𝑦 Untuk 𝑙 = 𝑘, 𝑘 − 1, … ,1 lakukan 𝜇𝑦,𝑙 ≔

𝐛𝑦 .𝐛∗𝑙

𝐛∗𝑙 .𝐛∗𝑙 ≔ 𝐛∗𝑦 − 𝜇𝑦,𝑙 𝐛∗𝑙 𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑦 𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛

𝐛∗𝑦

48. 49. Perbarui 50. Perbarui 51. 𝑘 ≔ 𝑘 + 1 52. Perbarui [𝐛1 , … , 𝐛𝑘 , 𝐛𝑘+1 , … , 𝐛𝑛 ] 53. return(ℬ = [𝐛1 , 𝐛2 , … , 𝐛𝑛 ] dan ℬ ∗ = [𝐛1∗ , 𝐛∗2 , … , 𝐛∗𝑛 ]). Analisis Algoritme Greedy SVP LLL Analisis di sini adalah menghitung banyaknya operasi aritmetik dalam algoritme greedy SVP LLL yang telah dikonstruksi. Algoritme dimulai dengan inisialisasi vektor pertama sebagai vektor ortogonal, dilanjutkan dengan operasi assignment pada nilai 𝑘 ≔ 1. Kemudian, dilakukan inisialisasi pada 2 variabel untuk membagi vektor kolom yang ada di dalam matriks atas nilai assignment 𝑘. Proses inisialisasi pada Langkah 4 ini dimaksudkan untuk membandingkan satu persatu vektor yang ada di dalam 2 variabel. Kemudian, masuk dalam looping “while” yang akan diulangi sebanyak 𝑛 − 𝑘, dengan nilai 𝑛 adalah dimensi matriks input. Selanjutnya dalam algoritme akan dihitung banyaknya operasi yang terlibat dalam proses reduksi ukuran. Banyaknya operasi yang ada pada Langkah 6 hingga Langkah 9 (proses reduksi ukuran) yaitu sebagai berikut: 1) Sebuah operasi assignment sebagai statemen awal untuk vektor ke-y yang ingin di reduksi. 2) Ada sebuah blok statemen “for” yang diulang sebanyak k a) Ada 2 operasi assignment

39 b) Ada 3 operasi perkalian vektor, 1 operasi pengurangan, 1 operasi pembagian, dan 1 operasi pembulatan ke bilangan bulat terdekat. Setelah blok ini, dihitung norm dari vektor yang telah direduksi yang diberikan dalam variabel tertentu, kemudian diinisialisasi suatu variabel 𝑖. Pada Langkah 12 hingga Langkah 21, blok statemen di awali dengan looping reduksi ukuran vektor-vektor ke-𝑘 + 2 hingga vektor ke-𝑛. Banyaknya operasi yang terlibat dalam blok ini adalah: 1) Blok statemen proses reduksi ukuran yang menggunakan operasi yang sama dengan Langkah 6 hingga Langkah 9. 2) Menghitung setiap norm yang telah direduksi dengan vektor-vektor yang telah dinisialisasi dalam variabel 𝑘. Kemudian ada percabangan pada blok ini, dimana ada 1 tanda perbandingan untuk membandingkan panjang vektor yang yang telah direduksi pada Langkah 6, untuk mendapatkan yang vektor dengan norm terpendek. Dalam blok ini ada 3 inisialisasi, masing-masing untuk penukaran posisi vektor dengan norm terpendek. Pada Langkah 22 hingga Langkah 24, operasi assignment untuk vektor ke 𝑘 + 2 hingga 𝑛, dan variabel 𝑚 dan 𝑏 yang menyatakan posisi vektor. Selanjutnya, pada Langkah 25 hingga Langkah 29 merupakan looping untuk menghitung norm dari vektor posisi pertama hingga ke vektor ke-𝑘 dan didalamnya ada statemen “if” dimana vektor terpendek hasil reduksi pada Langkah 12 dibandingkan panjangnya. Jika kondisi ini terpenuhi, maka posisi vektor akan ditukar di posisi vektor ke-𝑘. Dalam Langkah 30 hingga Langkah 44, terdapat blok percabangan yang memungkinkan penyisipan vektor dengan norm terpendek untuk menempati posisi pertama, atau posisi vektor yang disisipkan antara vektor pertama dan vektor ke- 𝑘 . Jika kondisi ini terpenuhi, barisan yang mengandung vektor terpendek dihitung nilai vektor ortogonalnya dengan menggunakan ortogonalisasi Gram-Schmidt. Pada Langkah 45 hingga Langkah 48, di awali dengan inisialisasi vektor yang tidak masuk dalam kondisi percabangan, untuk dihitung nilai vektor ortogonalnya. Rincian banyaknya operasi dalam blok statemen “for” ini adalah: 1) 2 operasi inisialisasi 2) 1 operasi pembagian, 3 operasi perkalian vektor, dan 1 operasi pengurangan. Langkah terakhir adalah penambahan indeks 𝑘 kemudian kembali ke Langkah 3. Proses akan berakhir jika nilai 𝑘 ≔ 𝑛. Pengujian Eksperimental dan Perbandingan Running Time masing-masing Algoritme dengan Output Sama Selain dihitung banyaknya operasi aritmetik dalam algoritme, juga dilakukan pengujian terhadap algoritme LLL, algoritme LLL penyisipan dalam, dan algoritme greedy SVP LLL. Pengujian dilakukan dengan cara memasukkan 3 matriks latis bilangan bulat berukuran 𝑛 × 𝑛 (𝑛 = 10, 20, … 80) dengan 𝛿 = 4. Output dari program adalah matriks bilangan bulat tereduksi LLL berukuran 𝑛 × 𝑛 dan matriks hasil ortogonalisasi Gram-Schimdt. Pengujian ini bertujuan untuk melihat mana diantara ketiga program yang lebih cepat waktu eksekusinya. Untuk memperoleh running time, waktu eksekusi setiap ukuran matriks diambil sebanyak 5 kali, kemudian diambil nilai rata-ratanya.

40

Tabel 1 Ukuran matriks 𝑛 × 𝑛 versus running time (detik) dengan 𝛿 = 3/4 Jenis Algoritme

Ukuran matriks 10 x 10

20 x 20

30 x 30

40 x 40

50 x 50

60 x 60

70 x 70

80 x 80

0.059

1.207

8.234

13.104

33.712

83.034

93.544

388.099

0.072

1.763

13.625

64.659

136.485

401.216

651.058

2126.497

0.044

1.061

7.132

7.226

17.634

34.617

83.408

139.385

LLL Penyisipan Dalam Greedy SVP LLL

Berdasarkan Tabel 1 di atas, dengan meningkatnya ukuran matriks, running time eksekusi ketiga program mengalami peningkatan. Hal ini terjadi karena semakin besar ukuran input matriks maka ukuran iterasi proses yang dilakukan pun akan semakin besar. Untuk algoritme greedy SVP LLL yang merupakan varian baru yang telah dibuat, dalam percobaan yang telah dilakukan untuk ukuran matriks yang berbeda, mengungguli tiga algoritme lain dalam segi kecepatan. Untuk melihat fenomena ini, berikut diberikan grafik perbandingan running time versus ukuran matriks 𝑛 × 𝑛 sebagai masukkannya. 2500

Running Time (detik)

2000

LLL DI Greedy SVP LLL

1500

1000

500

0

10 x 10 20 x 20 30 x 30 40 x 40 50 x 50 60 x 60 70 x 70 80 x 80

Ukuran Matriks (n x n)

Gambar 6 Perbandingan running time (detik) versus ukuran matriks 𝑛 × 𝑛