Faktorisasi??

11Y05 – Factorization (Faktorisasi)

Faktorisasi dalam matematika merupakan dekomposisi dari suatu obyek (misalnya bilangan, polinomial, atau matriks) menjadi suatu obyek lain (dalam hal ini disebut faktor), yang ketika dikalikan bersama akan menghasilkan bilangan asalnya.

Tujuan dari faktorisasi biasanya adalah untuk mereduksi suatu objek menjadi “basic building block” atau “blok pembangunan dasar” nya, seperti bilangan-bilangan prima (untuk bilangan), atau polinomial tak tereduksi (untuk polinomial). Faktorisasi prima diatur oleh teorema dasar aritmatika, sementara faktorisasi polinomial diatur oleh teorema dasar aljabar. Selain itu, terdapat juga rumus-rumus Viète yang mengaitkan koefisien-koefisien suatu polinomial pada akar-akarnya.

1.      Faktorisasi Prima

Faktorisasi prima menggunakan teorema dasar aritmatika sebagai dasar atau landasannya. Teorema dasar aritmatika dikemukakan oleh Euclid sekitar tahun 300 SM dalam bukunya “Elements” bagian IX. Pada bagian ini, Euclid juga mengemukakan ketidak terbatasan bilangan prima.

Teorema dasar aritmatika berbunyi:

“Setiap bilangan komposit merupakan hasil perkalian bilangan-bilangan prima dengan cara yang unik”.

Maksud unik dalam teorema tersebut adalah bahwa untuk setiap anggota bilangan komposit (bilangan bulat positif yang lebih dari 1) hanya dapat dinyatakan dalam satu kombinasi perkalian bilangan prima. Contohnya adalah 11 x 3 = 33. Tidak ada bilangan prima lain selain 11 dan 3 yang bila dikombinasikan dengan perkalian akan menghasilkan 33.

Contoh faktorisasi prima:

200 = 2³ x 5²

164 = 2² x 41

Hingga kini, belum ada algoritma yang efisien untuk menunjukkan faktorisasi non-kuantum. Tahun 2009, dilakukan percobaan faktorisasi bilangan oleh beberapa peneliti yang dipimpin oleh Thorsten Kleinjung. Percobaan tersebut berlangsung lama, yakni sekitar 2 tahun. Padahal, dalam percobaan tersebut telah digunakan ratusan komputer sebagai alat bantunya.

Sifat matematis inilah yang hingga sekarang menjadi dasar algoritma enkripsi berkunci publik RSA. Karena hingga sekarang, belum ditemukan teknik untuk mendapatkan hasil faktorisasi prima yang cepat dan efisien. Karena hal tersebut juga, enkripsi RSA tergolong sangat amandan hanya bisa dibuka dengan cara paksa yang harus memakan waktu bertahun-tahun.

2.      Faktorisasi Polinomial

Faktorisasi Polinomial merupakan proses dekomposisi untuk mengubah bentuk suatu polinomial ke dalam bentuk polinomial tak tereduksi. Faktorisasi polinomial ini merupakan dasar dari sistem aljabar dalam komputer.

Dalam buku Vera Sanford, A Short History of Mathematics, dikemukakan bahwa metode pemfaktoran polinom yang paling sering kita gunakan saat ini merupakan metode pemfaktoran yang paling baru. Karena metode ini baru muncul setelah diperkenalkan oleh Thomas Harriot pada tahun 1631. Harriot meninggal pada tahun 1621, namun bukunya “Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas” dipublikasikan setelah kematiannya. Awalnya Harriot menuliskan sejumlah penjumlahan dan pengurangan seperti (a+b) lalu (a-b), kemudian (a+c) dan seterusnya. Kemudian hHarriot menuliskan bahwasannya (aa-ba+ca) asalnya adalah (a-b)(a+c) dimana ia menggunakan a sebagai variabel nya (sekarang kita biasa menggunakan x). Harriot pun menuliskan seluruh (a±b)(a±c).

Faktorisasi polinomial diatur dalam teorema dasar aljabar yang berbunyi:

“Setiap polinomial berderajat n akan selalu memepunyai akar  sebanyak n di ”

Teorema tersebut pertama kali ditulis oleh Peter Rothe dalam bukunya, Arithmetica Philosophica tahun 1608, dan kemudian dikemukakan lagi oleh Albert Girard dalam bukunya L'invention nouvelle en l'Algèbre pada tahun 1629. Kemudian pada tahun 1799 barulah Gauss berhasil membuktikan teorema tersebut dalam disertasinya.

Selain itu terdapat juga Rumus Vieta yang menyatakan rumus-rumus jumlah dan hasil kali akar-akar pada persamaan polinom. Dengan menggunakan jumlah dan hasil kali ini kita bisa mendapatkan berbagai perhitungan akar-akar walaupun kita tidak mengetahui nilai akar-akarnya. Bentuk-bentuk yang dicari tersebut bisa simetris, bisa juga tidak simetris.

Bentuk Teorema Vieta:

a.       Persamaan Kuadrat

ax² + bx + c = 0

x₁ + x₂ = -b/a

x₁x₂ = c/a

b.      Persamaan Kubik

ax³ + bx² + cx + d = 0

x₁ + x₂ + x₃= -b/a

x₁x₂ + x₁x₃ +  x₂x₃ = c/a

x₁x₂x₃ = -d/a

c.       Persamaan Kuartik

ax⁴ + bx³ + cx² + dx + e = 0

x₁ + x₂ + x₃ + x₄ =-b/a

x₁x₂ + x₁x₃ + x₁x₄ +  x₂x₃ + x₂x₄ + x₃x₄  = c/a

x₁x₂x₃ + x₁x₂x₄ + x₁x₃x₄ +x₂x₃x₄ = -d/a

x₁x₂x₃x₄  = e/a

d.      Persamaan Kuintik

ax⁵ + bx⁴ + cx³ + dx² + ex + f = 0

x₁ + x₂ + x₃ + x₄ + x₅ =-b/a

x₁x₂ + x₁x₃ + x₁x₄ + x₁x₅ +  x₂x₃ + x₂x₄  + x₂x₅ + x₃x₄ + x₃x₅ + x₄x₅ = c/a

x₁x₂x₃ +x₁x₂x₄ +x₁x₂x₅ +x₁x₃x₄ +x₁x₃x₅ +x₁x₄x₅ +x₂x₃x₄ +x₂x₃x₅ +x₂x₄x₅ +x₃x₄x₅ =-d/a

x₁x₂x₃x₄ +x₁x₂x₃x₅ + x₁x₂x₄x₅ + x₁x₃x₄x₅ + x₂x₃x₄x₅ = e/a

x₁x₂x₃x₄x₅ = -f/a

Referensi

https://en.wikipedia.org/wiki/Factorization

https://en.wikipedia.org/wiki/Integer_factorization

https://en.wikipedia.org/wiki/Factorization_of_polynomials

https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra

http://eprint.iacr.org/2010/006.pdf (Factorization of a 768-bit RSA modulus)

https://books.google.co.id/books?id=771CAAAAcAAJ&printsec=frontcover&source=gbs_ge_summary_r&redir_esc=y#v=onepage&q&f=false