BAB II TINJAUAN PUSTAKA Pada bab ini dituliskan beberapa aspek teoritis berupa definisi, teorema dan sifat-sifat yang berhubungan dengan teori bilangan, integer modulo , aljabar abstrak, masalah logaritma diskret, sistem persamaan linear, dan kompleksitas waktu asimptotik sebagai landasan teori untuk penulisan tugas akhir ini. 2.1
Teori Bilangan
Definisi 2.1.1 Misalkan integer
,
dan
adalah integer dengan
menghasilkan integer +, dimana 0 ≤
pembagian dinotasikan
(hasil pembagian) dan
| dan
2.
dan , dinotasikan
adalah pembagi bersama dari jika
| dan
| , maka
dan
mod dan hasil
= gcd ( , , jika ) :
Teorema 2.1.5 (Algoritme Euclidean) Diberikan integer
,
algoritme pembagian, dapat dibentuk barisan persamaan berikut : =
= =
+
+
+
,0 <
<
,0 <
<
,0 < ⋮
+ ,0 < =
dan ,
disebut pembagi bersama terbesar
| (Menezes et al. 1997).
=
oleh
(sisa pembagian) sehingga
dikatakan sebagai pembagi bersama dari
Definisi 2.1.4 Suatu integer non-negatif 1.
| )jika terdapat
≥ 1, maka pembagian
≤ . Sisa pembagian dinotasikan
| (Menezes et al. 1997).
(gcd) dari integer
(notasi
div (Menezes et al. 1997).
Definisi 2.1.3 Suatu integer jika
membagi
= .
sedemikian sehingga
Definisi 2.1.2 Jika =
integer.
<
<
> .0Berdasarkan
= gcd ( , ,) yang merupakan sisa terakhir tak nol dari proses
dengan
pembagian. Nilai dari menuliskan setiap
dari ( , ) =
dan
sebagai kombinasi linear dari
Definisi 2.1.6 Integer
dan
+
dapat diperoleh dengan
dan
(Lestari 2007).
dikatakan prima relatif atau koprima jika
gcd( , ) = 1 (Lestari 2007).
≥ 1, didefinisikan ∅( ) adalah
Definisi 2.1.7 (Fungsi-∅ Euler) Untuk banyaknya integer pada selang [1,
] yang prima relatif dengan
disebut fungsi-∅ Euler (Menezes et al. 1997).
. Fungsi ∅
Teorema 2.1.8 (Sifat-sifat fungsi-∅ Euler) prima, maka ∅( ) =
− 1.
1.
Jika
2.
Fungsi-∅ Euler bersifat multiplikatif. Artinya, jika gcd( ) = ∅( )∅( )
∅(
3.
Jika
∅( ) =
=
1−
…
adalah
1−
faktorisasi
⋯ 1−
prima
sebagai produk dari kuasa prima yang khas: bilangan
prima
yang
dari
,
maka
(Menezes et al. 1997).
Fakta 2.1.9 (Teorema Dasar Aritmetika) Setiap integer adalah
, ) = 1 maka
berbeda
=
dan
≥ 2dapat difaktorkan …
adalah
, dimana
integer
positif
(Menezes et al. 1997). 2.2
Integer Modulo
Definisi 2.2.1 (Kongruensi) modulo , ditulis
≡
dan
adalah integer.
(mod , jika )
dikatakan kongruen dengan
membagi habis (
disebut modulus kongruensi (Menezes et al. 1997).
Teorema 2.2.2 (Syarat-syarat Kekongruenan) Untuk semua hal-hal di bawah ini adalah benar. 1)
≡
(mod jika ) dan hanya jika
dan
− .)Selanjutnya , ,
, ,
∈ ℤ,
mempunyai sisa yang sama jika
dibagi dengan . 2) (refleksif)
≡
(mod
) 6
≡
3) (simetri) Jika
≡
4) (transitif) Jika
≡ (mod
5) Jika
≡
(mod dan )
(mod
≡
dan
(mod maka ) ) dan
≡
≡ (mod
(mod . )
(mod , maka ) ), maka
)(Guritman et al. 2004).
ekuivalensi) integer {0,1,2, … ,
⇔
=
+
⇔
≡
,
(mod ) ≡ (mod
,
modulo
)
≡ (mod
sedemikian sehingga
(mod , maka )
={ ,
,…,
}
terdapat
)(Lestari 2007).
) Sistem residu tereduksi
, dimana gcd( , ) = 1,
adalah himpunan integer
Selanjutnya setiap
≡
jika untuk setiap integer
Definisi 2.2.5 (Sistem Residu Tereduksi Modulo modulo
)
(Guritman et al. 2004).
. Selanjutnya himpunan
dinamakan sistem residu lengkap modulo satu dan hanya satu
(mod
∈ℤ ,
Definisi 2.2.4 (Sistem Residu Lengkap Modulo ) Jika disebut residu dari
≡ +
− 1} yang dikenai operasi penjumlahan dan
perkalian diperlakukan dalam modulo . Untuk =
(mod . )
, dinotasikan ℤ , adalah himpunan (kelas
Definisi 2.2.3 Integer modulo
+
+
≡
≢
≠.
, jika
yang prima relatif dengan , kongruen dengan suatu
pada
himpunan tersebut (Lestari 2007). Fakta 2.2.6 (Invers) Misalkan
∈ ℤ.
memiliki invers jika dan hanya jika
gcd( , ) = 1 (Menezes et al. 1997).
Definisi 2.2.7 (Invers Multiplikatif) Misalkan
modulo
adalah suatu integer
∈ ℤ sehingga
∈ ℤ , Invers multiplikatif dari
≡ 1 (mod . Faktanya ) tidak
semua anggota ℤ mempunyai invers ( belum tentu ada). Dalam hal
bersangkutan ada, maka dinotasikan
=
disebut invertibel dan
invers modulo
disebut invers dari
,
(Guritman et al. 1997).
Definisi 2.2.8 (Pembagian) Misalkan adalah perkalian
yang
dengan
modulo
,
∈ ℤ. Pembagian
oleh
, yang terdefinisi jika
modulo mempunyai
(Menezes et al. 1997).
7
Definisi 2.2.9 Grup multiplikatif ℤ adalah ℤ bilangan prima, maka ℤ
∗
= { |1 ≤
≤
∗
={
∈ ℤ | gcd( , ) = 1}. Jika
− 1}(Menezes et al. 1997).
= gcd ( , . Persamaan )
Teorema 2.2.10 (Solusi Persamaan kongruen) Misal ≡
kongruen
(mod mempunyai ) solusi
dalam hal ini terdapat tepat modulo
jika dan hanya jika
− 1; solusi ini semua kongruen
solusi antara 0 dan
/ (Menezes et al. 1997).
,
Teorema 2.2.11 (Teorema Sisa Cina) Jika ,
prima relatif satu sama lain, kongruensi
,…,
≡ (mod ≡ (mod ⋮ ≡ (mod
mempunyai solusi unik modulo ,
=
,…,
=
mod
) )
)
… … (∗) …
(Menezes et al. 1997).
(i) (Teorema Euler) Jika (ii) Jika maka
dari sistem kongruensi Teorema
≥ 2adalah integer. ∈ ℤ ∗ , maka
∅(
)
≡ 1(mod
(mod
Teorema 2.2.14 Misalkan
), untuk semua integer
≡
(mod
Jika
3.
Untuk setiap integer ,
2.3
(mod (∅ )),
≡
prima,
− ,1) maka
2.
dan
(Menezes et al. 1997).
(Teorema Fermat) Jika gcd( , ) = 1, maka
1.
).
adalah produk bilangan prima berbeda, dan jika ≡
= ⁄
mod , dimana
=∑
(Menezes et al. 1997).
Teorema 2.2.13 Misalkan
merupakan integer yang
adalah sembarang integer, maka sistem
Algoritme 2.2.12 (Algoritme Gauss’s) Solusi 2.2.11 dapat dihitung sebagai
membagi ,
≡
≡
(mod
(mod
≡ 1 (mod
).
), untuk semua integer .
()Menezes et al. 1997).
Struktur Aljabar
Definisi 2.3.1 Operasi biner ∗ pada suatu himpunan × ke , yang membawa setiap ( , ) ∈
× ke
adalah suatu fungsi dari ∗
∈ yang unik. Jadi 8
( , )→
∗ . Karena
∗ juga berada dalam
bawah operasi ∗ (Aliatiningtyas 2002).
memenuhi aksioma-aksioma berikut ini, operasi ∗ bersifat assosiatif (
2.
ada
3.
∗
unsur =
untuk setiap
identitas
∗
= ,∀
∈ .
∗ )∗
∈ ,
∈ ada unsur
(Aliatiningtyas 2002).
∈,
=
untuk
∈
∗
∗(
∗ ), ∀ ,
,
pada
sehingga
∗
∈.
sehingga
=
∗
berlaku =
disebut grup komutatif jika operasi ∗ bersifat komutatif
Definisi 2.3.3 Grup yaitu ∀ ,
tertutup di
dengan operasi biner ∗ disebut grup jika
Definisi 2.3.2 (Grup) Struktur aljabar 1.
maka dikatakan
∗
=
∗(Aliatiningtyas 2002).
Definisi 2.3.4 (Grup Hingga dan Order) Suatu grup
dikatakan berhingga jika
banyaknya unsur berhingga. Banyaknya unsur dari grup hingga dinamakan order dari , dinotasikan ℴ(
)(Aliatiningtyas 2002).
Definisi 2.3.5 (Order dari Unsur Grup) Misalkan
(notasi ℴ( ))adalah integer positif
grup, dan
= . Jika tidak ada
minimal sehingga
bilangan yang demikian, maka dikatakan order dari
∈ . Order
tak hingga atau nol
(Aliatiningtyas 2002). Toerema 2.3.6 Berikut ini 3 sifat dasar yang berkaitan dengan pengertian order. 1.
Misalkan
2.
=
,
Misalkan
grup, , ,…,
grup,
∈ dan ℴ( ) = , maka ada tepat
3.
yaitu
yang semuanya berbeda.
∈ . Jika ℴ( )tak hingga, maka semua kuasa dari
berbeda. Artinya, jika ≠
kuasa dari
dan
adalah dua integer yang berbeda, maka
.
Misalkan
adalah unsur dari grup
hanya jika sehingga
adalah kelipatan dari =
dan ℴ( ) = . Maka ( kelipatan
=
jika dan
artinya ada integer
) (Aliatiningtyas 2002; Guritman 2004).
9
Definisi 2.3.7 (Subgrup) Misalkan dari
jika
⊆ . Maka
grup dan
grup dibawah operasi biner yang sama dengan operasi biner pada . ⊴ ) (Aliatiningtyas 2002).
(Notasi :
Definisi 2.3.8 (Grup Siklik) Suatu grup ∈
hanya jika ada unsur =〈 〉 =
(
berorder , maka
∈ sehingga ℴ( ) =
dikatakan siklik jika dan
disebut generator) sedemikian sehingga
∈ ℤ}(Guritman 2004).
Teorema 2.3.9 Jika grup ada
adalah siklik jika dan hanya jika
(Guritman 2004).
Teorema 2.3.10 (Teorema Lagrange’s) Jika subgrup
disebut subgrup
, maka order dari
grup hingga dan
membagi order dari
adalah
(Menezes et al. 1997;
Aliatiningtyas 2002). Definisi 2.3.11 (Ring) Struktur aljabar 〈
, +,∙〉 dengan operasi + disebut operasi
penjumlahan dan operasi ∙ disebut operasi perkalian, disebut ring jika memenuhi aksioma-aksioma berikut ini. 1. 2. 3.
〈 , +〉 grup komutatif.
Operasi perkalian bersifat assosiatif. Hukum
distributif
kiri
berlaku
:
Hukum distributif kanan berlaku : ∀ ,
,
∀ ,
,
∈
∈( ,+ )
(,
=
+ )=
+ .
+.
Unsur identitas terhadap + dinotasikan dengan 0 dan disebut unsur nol. Selanjutnya, 1.
Jika operasi perkalian bersifat komutatif, ∀ ,
∈,
ring komutatif. 2.
disebut
Jika ada unsur identitas dibawah operasi perkalian (unsur ini disebut unsur kesatuan, ∃1 ∈ ,
dinotasikan
1
dan
(Aliatiningtyas 2002).
Definisi 2.3.12 Misalkan
ring. Himpunan bagian
jika
∙1 = 1∙
dengan
= maka
dari
= maka
disingkat
unkes)
∀
disebut ring dengan unsur kesatuan
merupakan ring dibawah operasi dalam
dari ring
∈ ,
disebut subring
(Aliatiningtyas 2002).
10
Definisi 2.3.13 (Ideal) Misal
ring,
disebut ideal jika memenuhi : a.
,
∈
∈ dan
b.
⟹(
−
∈
⟹
) .∈
∈dan
⊆ ,
∈ (Aliatiningtyas 2002).
Teorema 2.3.14 (Ideal Utama) Misalkan 1 dan 〈 〉={
ring komutatif dengan unsur kesatuan
∈ . Suatu himpunan dilambangkan 〈 〉, yang didefinisikan sebagai |
dibangun oleh
∈ merupakan } ideal. Ideal yang demikian disebut ideal utama yang (Rosdiana 2009).
Definisi 2.3.15 Misalkan adalah
tidak kosong. Himpunan bagian
+
ring,
ideal dari
, maka koset-koset aditif dari
∈ . Definisikan
dengan
/
penjumlahan dan perkalian didefinisikan : ( Teorema 2.3.16 〈
/
(Aliatiningtyas 2002). Definisi 2.3.17 Fungsi ∈ R, berlaku
(
+ )+( + )(
+ )=(
+ )=
={
+ )+ +
+
|
∈. Operasi }
(Aliatiningtyas 2002).
〉 merupakan ring dan disebut ring faktor dari , +,∙
oleh
dari ring R ke ring R’ disebut homomorfisma jika ∀a,b (a + b) = (a) + (b) (ab) = (a) (b)
Kernel
={x∈R|
(x) = 0’}, 0’ unsur nol dari
.’ Jika ada homomorfisma
yang bijektif dari R ke R’, maka dikatakan R isomorfik dengan R’, dinotasikan : R ≃ R’ (Aliatiningtyas 2002).
Teorema 2.3.18 Misalkan θ: R → R’ adalah homomorfisma ring. Maka 1. θ(R) subring dari R’ 2. Ker θ adalah ideal dari R 3. Jika N ideal dari R, maka θ(N) juga ideal dari R’ (Aliatiningtyas 2002). Definisi 2.3.19 (Polinomial) Jika parameter
atas
ring komutatif, maka polinomial dengan
diekspresikan dalam bentuk : ( )=
+ ⋯+
+
+ 11
∈
dimana terbesar
≥ 0.
dan
disebut koefisien dari
≠ 0 disebut derajad
pada
≠ 0, maka
( a)dalah 0, maka
( . ) Jika
( )=
disebut
(polinomial
( )mempunyai derajad 0. Jika semua koefisien
( )disebut polinomial nol dan derajadnya dinotasikan −∞.
( ) dikatakan
Polinomial
( .) Integer
( , )dinotasikan deg ( )dan
koefisien utama (leading coeffisien) dari konstan) dan
dalam
monik
jika
koefisien
utamanya
1
(Menezes et al. 1997).
Definisi 2.3.20 ℤ [x] adalah himpunan semua polinomial dalam peubah x dengan
koefisien dalam ring ℤ merupakan sebuah ring di bawah operasi penjumlahan
dan perkalian polinomial (Fraleigh 2000).
Definisi 2.3.21 (Polinomial Irredusibel) Misal berderajad paling kecil 1.
( ) ∈ ℤ[ ]adalah polinomial
( )dikatakan irredusibel atas ℤ jika f(x) tidak dapat
dinyatakan sebagai produk dari dua polinomial berderajad lebih kecil dari f(x) dalam
ℤ [ ].
Dan
dikatakan
redusibel
jika
faktorisasinya
ada
(Menezes et al. 1997). Definisi 2.3.22 Misal polinomial tak-nol
( ), ℎ( ) ∈ ℤ [ ]. Maka
dari
( ) dan ℎ( ), dinotasikan gcd ( ( ), ℎ( )), adalah polinomial monik
berderajad terbesar dalam ℤ [ ]yang membagi 1997).
( )dan ℎ( )(Menezes et al.
Teorema 2.3.23 (Teorema Faktor) Jika ℤ adalah ring komutatif dengan unsur
kesatuan dan
( ) ∈ ℤ[ ] berderajad ≥ 1, maka ( ) = 0 jika dan hanya jika
− adalah faktor dari
( ()Michaels 2000).
Definisi 2.3.24 (Field) Suatu ring yang komutatif, ada unkes dan setiap unsur tak nolnya
mempunyai
invers
(multiplikatif)
disebut
lapangan
(field)
(Aliatiningtyas 2002). Definisi 2.3.25 (Subfield) Jika field operasi penjumlahan dan perkalian di subfield dari , dan
memuat field
(sedemikian sehingga
sama dengan di
disebut perluasan field dari
), maka
disebut
(Pretzel 1992).
12
Definisi 2.3.26 (Finite Field) Suatu field
dikatakan berhingga (finite field) jika
himpunannya memiliki banyak elemen yang berhingga. Order banyaknya anggota
adalah
(Menezes et al. 1997).
Teorema 2.3.27 Eksistensi dan kekhasan finite field. 1. 2.
Jika F adalah finite field maka F terdiri dari
unsur dengan p prima dan
≥ 1.
Untuk setiap prima berorder pm, ada finite field yang khas berorder pm. Field ini dinotasikan dengan GF(pm) (Menezes et al. 1997).
Teorema 2.3.28 Misal field berorder
bilangan prima. Himpunan integer modulo
dinotasikan dengan
Teorema 2.3.29 Unsur tak-nol
( atau ) ℤ (Rosdiana 2009).
( ) membentuk sebuah grup di bawah
operasi perkalian disebut grup perkalian dari ( ) ∗ (Menezes et al. 1997).
Teorema 2.3.30
= , untuk setiap
( ), dinotasikan dengan
( )∗ adalah grup siklik yang berorder ∈
Teorema 2.3.31 Finite field dan setiap elemen (Saeki 1997).
( )
( ) adalah perluasan field ℤ berderajad −
adalah akar polinomial
tak-konstan di ℤ [ .] Maka ada perluasan field
sedemikian sehingga ( ) = 0 (Fraleigh 2000). adalah perluasan field ℤ .
( ) = 0 untuk beberapa polinomial tak-nol
atas ℤ , maka
− 1 dan berlaku
( ) (Menezes et al. 1997).
Teorema 2.3.32 Misalkan ℤ adalah field dan misalkan
Definisi 2.3.33
berbentuk
atas
dari ℤ
dan ada
∈
∈ disebut algebraic atas ℤ jika
( ) ∈ ℤ[ ]. Jika
tidak algebraic
( ) ∈ ℤ[ ]adalah polinomial irredusibel berderajad
Maka ℤ [ ]/〈 ( )〉 adalah finite field dengan order perkalian polinomial dilakukan dalam modulo
ℤ
( )adalah polinomial
transcendental atas ℤ (Fraleigh 2000).
Teorema 2.3.34 Misal
,
.
. Penjumlahan dan
( ()Menezes et al. 1997). 13
( ) ∈ ℤ[ ]berderajad
Definisi 2.3.35 Suatu polinomial irredusibel polinomial primitif jika
disebut
( )∗ (Menezes et al. 1997).
adalah generator dari
Definisi 2.3.36 Misal E perluasan field dari field ℤ dan c ∈ E algebraic atas ℤ .
Polinomial irreducible untuk c atas ℤ dari polinomial monik ( ) dinotasikan dengan irr(c, ℤ ) dan derajad dari polinomial irreducible untuk c atas ℤ dinotasikan dengan deg(c, ℤ ) (Rosdiana 2009). = ℤ ( ) dengan
Teorema 2.3.37 Misal ,ℤ = ,
deg
unik dalam bentuk
≥ 1. Setiap unsur =
2009). Teorema
2.3.38
berderajad
dan
+
dari
+ ⋯+
Diberikan ( ) = 0,
(
∈
algebraic atas ℤ , dan
= ℤ ( )dapat dinyatakan secara
∈ ℤ (Rosdiana
, dimana
polinomial
( )∈ℤ [ ]
irredusibel
) ≅ ℤ [ ]/〈 ( 〉) ≅ ℤ ( ) ≅ {
+
⋯+
+ |
grup,
field. Pada V didefinisikan aturan penjumlahan dan aturan perkalian
skalar.
disebut ruang vektor atas
∈ℤ
untuk semua }(Michaels 2000).
Definisi 2.3.39 (Ruang Vektor) Misal
1.
∈
Untuk setiap
jika memenuhi aksioma berikut.
dan setiap
tertutup terhadap perkalian :
di bawah operasi penjumlahan abelian
⃗ ∈
⃗ =⃗.
∈ dan setiap ⃗,⃗ ∈ ,
terdapat tunggal ⃗ ∈ ⃗ = ⃗+
2.
Untuk setiap
3.
Untuk setiap
4.
Untuk setiap
5.
Untuk setiap ⃗ ∈ , 1 ⃗ = ;⃗1 unsur identitas di 〈
,
,
∈ dan setiap ⃗ ∈ , (
+) ⃗ =
∈ dan setiap ⃗ ∈ , ( ) ⃗ = ( )⃗.
⃗ +⃗.
⃗ +.
sehingga
⃗
,∙〉 (Rosdiana 2009).
Definisi 2.3.40 Misalkan V adalah ruang vektor atas skalar
, dan misalkan
A = {v1, v2, ..., vn} adalah himpunan yang terdiri atas n vektor dalam V. A disebut bebas linear jika (∑ni ci vi = 0) ⇒ (∀i ∈ I = {1,2,…,n} ci = 0).
Ingkarannya, A disebut terpaut linear jika (∑ni ci vi = 0) ∧
∃j ∈ I = {1,2,…,n} cj ≠ 0
(Guritman 2005).
14
Definisi 2.3.41 Misalkan V adalah ruang vektor atas
={ ,
, dan
,…,
}
adalah himpunan berhingga vektor-vektor di dalam V. Untuk menyatakan bahwa V adalah ruang yang direntang oleh vektor-vektor pada himpunan B dituliskan =〈 〉. Artinya ∀
∈ ,
=∑
,
adalah integer.
Definisi 2.3.42 Misalkan V adalah ruang vektor atas , dan B adalah himpunan berhingga vektor-vektor di dalam V. Dikatakan B adalah basis untuk V jika B bebas linear dan V=〈B〉 (Guritman 2005).
ℤ . Jika deg
basis {1, 2.4
, ℤ = , maka ℤ ( )ruang vektor atas ℤ berdimensi- dengan } (Rosdiana 2009).
, ,…,
Masalah Logaritma Diskret
Definisi 2.4.1 (Logaritma Diskret) Misalkan ∈ . Logaritma diskret
generator , dan adalah
integer
unik
0≤
,
(Menezes et al. 1997). Teorema 2.4.2 Misalkan Misal log (
∈ algebraic atas
perluasan field dari field ℤ dan
Teorema 2.3.43 Misal
≤
log
.
dengan basis , dinotasikan log
− ,1 sedemikian
generator grup siklik
adalah sebuah integer. Maka log (
)=
grup siklik berorder
) =(log
mod (Menezes et al. 1997).
=
hingga
berorder
, dan
,
0≤
≤
− 2sehingga
∈.
+ log )mod , dan
Definisi 2.4.3 (Masalah Logaritma Diskret) Diberikan bilangan prima generator dari ℤ ∗, dan
,
,
∈ ℤ ∗ . Masalah logaritma diskret adalah menentukan , ≡
(mod
()Menezes et al. 1997).
Definisi 2.4.4 (Masalah Logaritma Diskret diperumum) Diberikan grup siklik berorder
,
generator
menentukan , 0 ≤
≤
− ,1sehingga
Lemma 2.4.5 Jika order dari tidak kongruen modulo
, dan
modulo
(Lestari 2007).
∈ . Masalah logaritma diskret adalah =
(Menezes et al. 1997).
adalah , maka 1,
, ,…,
saling
15
generator dari ℤ ∗, maka untuk setiap
Teorema 2.4.6 Misalkan ≡
sehingga
(mod
()Lestari 2007).
( ),
∈
Teorema 2.4.7 Setiap unsur
(Rosdiana 2009). Lemma 2.4.8 Andaikan → . Dipilih
∈
menggunakan iterasi ≠
untuk
dan ada
dibangkitkan oleh
=
=
prima, memenuhi
=
ekivalen dengan akar dari persamaan
:
≤ ∅( ) − 1 sedemikian
yang khas pada rentang 0 ≤
terdapat integer
∈ ℤ∗
−
sehingga
=∏
∈
atau
(
−
adalah himpunan hingga dan diketahui ada fungsi untuk membangkitkan barisan =
( ) untuk
≥ 0. Ada
> 0 sehingga
=
,
Lemma 2.4.9 Andaikan bahwa 1 ≤
,
,
,
,
, …, dengan
∈ sehingga ,
. Jika barisan =
menggunakan iterasi
maka hasilnya akan sama dengan barisan
( ( )) untuk
, … (Safaat 2007).
,
≤ , dan bilangan-bilangan
,
=
,…
≥0
,…,
bebas dipilih dari himpunan {1, 2, …, }. Peluang bahwa setiap bilangan 1−
berbeda adalah 2.5
1−
… 1−
(Safaat 2007).
Sistem Persamaan Linear
Definisi 2.5.1 Suatu persamaan linear dalam
peubah (variabel) adalah
persamaan dengan bentuk dimana
,
, …,
dan
+
+ ⋯+
=
adalah bilangan-bilangan real dan
adalah peubah. Dengan demikian maka suatu sistem linear dari dalam
,
, …, persamaan
peubah adalah satu sistem berbentuk : +
+ dimana
dan
)
+
+⋯+ +⋯+ ⋮
+ ⋯+
=
= =
semuanya adalah bilangan-bilangan real (Leon 1998).
16
Definisi 2.5.2 Suatu sistem persamaan linear dikatakan homogen jika konstantakonstanta di ruas kanan semuanya nol. Sistem-sistem homogen selalu konsisten (Leon 1998). Teorema 2.5.3 Sistem persamaan linear homogen >
taktrivial jika 2.6
(Leon 1998).
× memiliki penyelesaian
Algoritme Berlekamp’s Q-matrix
Algoritme 2.6.1 Algoritme Berlekamp’s Q-Matrix Input : Polinomial monik bebas kuadrat Output : Faktorisasi 1.
Untuk
2.
∑
Bentuk matriks
3.
Tentukan basis
setiap
,
,
∈
5.
← { ( )}.
Untuk 1 ≤
dalam
( d) alam polinomial irredusibel monik.
,
matriks identitas 4.
( b) erderajad
0≤ .
×
,…,
≤
− ,1 hitung
polinomial
untuk ruang null pada matriks (
× . Banyaknya faktor irredusibel pada
[ ]. mod ( ) = − ), dengan
( a)dalah .
≤ , lakukan langkah berikut :
5.1 Untuk setiap polinomial ℎ( ) ∈ , degℎ( ) > 1, lakukan langkah berikut Hitung gcd (ℎ( ),
6.
), untuk setiap
∈
, dan ganti ℎ( )pada
dengan semua polinomial hasil perhitungan gcd yang berderajad ≥ 1.
Hasilnya adalah polinomial-polinomial F yang berupa faktor-faktor irredusibel
2.7
( )−
( ()Menezes et al. 1997).
Kompleksitas Waktu Asimptotik Algoritme aritmetik yang dihasilkan dalam penelitian ini akan dianalisis
dari segi fungsi kompleksitas waktu (time-complexity function), yaitu sebagai fungsi untuk mengukur banyaknya operasi dalam suatu algoritme yang mempunyai variabel input . Yang dimaksud dengan banyaknya operasi adalah banyaknya operasi dasar (jumlah, kurang, kali dan bagi) ditambahkan dengan assignment dan perbandingan (ekspresi logika) (Guritman 2004). Hal ini perlu
17
untuk mengetahui kinerja algoritme. Kinerja algoritme akan tampak untuk besar, bukan pada
kecil.
Langkah pertama dalam pengukuran kinerja algoritme adalah membuat makna sebanding. Gagasannya adalah dengan menghilangkan faktor koefisien di ( .) Sebagai contoh, andaikan bahwa kompleksitas waktu
dalam ekspresi
terburuk dari sebuah algoritme adalah pertumbuhan dibandingkan 2
( )sebanding dengan 2
( )=2
, suku 6
+6
. Suku-suku yang tidak mendominasi perhitungan pada rumus
mengabaikan koefisien 2), ditulis ( ) = ( )=
berorder paling besar ( )≤
Teorema
( )), untuk
2.7.2
polinom derajad
besar,
+ 1 menjadi tidak berarti
( )dapat diabaikan, sehingga kompleksitas waktu
Definisi 2.7.1
+ 1. Untuk
( )adalah
( ).
( ( )) (dibaca ” ( )adalah
( ))bila terdapat konstanta C dan
Bila
≥
(dengan
( ( ))” artinya
( )
sedemikian sehingga
(Munir 2001).
( )=
maka ( ) =
+
( ) (Munir 2001).
Setelah mendefinisikan fungsi
+ ⋯+
+
adalah
( )untuk suatu algoritme, kemudian
dengan Tabel Oh-Besar (Menezes et al. 1997) kita tentukan order dari
sebagai
ukuran efisiensi algoritme yang bersangkutan. Dalam tabel berikut diberikan beberapa bentuk Oh-Besar yang sering muncul dalam aplikasi analisis algoritme (Guritman 2004). Urutan batasan lebih baik disusun dari atas ke bawah. Tabel 2.7.1 Oh-Besar Bentuk Oh-Besar
Nama
O(1) O(log2 n) O(n) O(n log2 n) O(n2) O(n3) m O(n ), m = 0, 1, 2, ... O(cn), c > 1 O(n!)
konstan logaritmik linear n log2 n kuadratik kubik polinomial eksponensial faktorial 18
19
