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 ๐ ร ๐