Faktorisasi prima

Matematika
$120px-Math.svg.png?utm_source=id.wikipedia.org&utm_campaign=parser&utm_content=thumbnail$
Artikel ini adalah bagian dari seri:
Ragam Garis besar matematika Aritmetika Bahasa pemrograman Filsafat matematika Matematika diskrit Matematika Islam Matematika keuangan Matematika murni Matematika terapan Matematika Yunani Pendidikan matematika
Aritmetika dasar Digit Penambahan (+) Pengurangan (-) Perkalian (×) Pembagian (÷)
Konsep matematika Faktorisasi dan Faktorisasi prima Bilangan prima dan Faktor persekutuan terbesar Garis bilangan Kelipatan dan Kelipatan persekutuan terkecil Pecahan Perpangkatan Akar bilangan dan Akar kuadrat Logaritma Himpunan Fungsi Peluang Rasio Dimensi Persamaan Sistem koordinat Statistika Teorema dasar kalkulus Teorema nilai antara Teorema nilai purata Teorema pythagoras Hipotenusa
Bangun datar dan ruang Persegi Persegi panjang Segitiga Segi lima Segi enam Segi delapan Tetrahedron Kubus Oktahedron Dodekahedron Ikosahedron
Alat matematika Swipoa Kalkulator Penggaris Jangka Jangka sorong Busur derajat
l b s

Masalah yang belum terpecahkan dalam Ilmu komputer

Apakah faktorisasi prima bisa dicapai dalam waktu polinomial?

Lebih banyak masalah yang belum terpecahkan dalam Ilmu komputer

Faktorisasi prima adalah pecahan bilangan komposit yang terdiri dari bilangan-bilangan pembagi yang lebih kecil, dan hasil perkalian dari bilangan-bilangan tersebut sama dengan bilangan komposit yang disebutkan. Contohnya, faktorisasi prima bilangan 84 adalah 2x2x3x7, di mana bilangan 2, 3 dan 7 adalah bilangan prima dan bilangan pembagi 84.

Sampai sekarang ini masih belum ditemukan algoritme faktorisasi non-kuantum yang efisien. Suatu percobaan^[1] faktorisasi bilangan dengan 232 digit yang dilaksanakan pada tahun 2009 oleh beberapa ilmuwan berlangsung selama 2 tahun dengan ratusan komputer. Sifat matematis ini adalah dasarnya algoritma enkripsi berkunci publik RSA. Karena sampai sekarang ini masih belum diketahui teknik untuk mendapatkan hasil faktorisasi prima yang cepat dan efisien, maka enkripsi RSA tergolong sangat aman dan hanya bisa dipecahkan dengan cara paksa (brute force) yang harus memakan waktu bertahun-tahun. Jika pada suatu hari telah ditemukannya algoritma yang mampu memecahkan masalah faktorisasi dalam waktu polinomial, semua enkripsi RSA akan langsung menjadi tidak aman.

Dua bilangan berbeda yang memiliki jumlah digit yang sama tidak sama sukar difaktorisasi. Menurut pengetahuan matematis sekarang, bilangan yang paling sulit difaktorisasi adalah bilangan semiprima (yaitu hasil perkalian dua bilangan prima).

Contoh

Tentukan faktor, faktor prima dan faktorisasi prima dari bilangan 18!

Faktor: 1, 2, 3, 6, 9 dan 18.

Faktor prima: 2 dan 3.

Faktorisasi prima: 2 dan 3².

Tentukan hasil dari 9.261 3 {\displaystyle {\sqrt[{3}]{9.261}}} ${\sqrt[{3}]{9.261}}$ dan 16 4 {\displaystyle {\sqrt[{4}]{16}}} ${\sqrt[{4}]{16}}$ !

9.261 3 {\displaystyle {\sqrt[{3}]{9.261}}} ${\sqrt[{3}]{9.261}}$: Faktorisasi prima dari 9.261 adalah 3³ dan 7³ maka hasilnya adalah 7 x 3 = 21.
16 4 {\displaystyle {\sqrt[{4}]{16}}} ${\sqrt[{4}]{16}}$: Faktorisasi prima dari 16 adalah 2⁴ maka hasilnya adalah 2.

Algoritma

Berikut adalah beberapa contoh algoritma faktorisasi prima:

Percobaan pembagian (Trial division): Algoritma yang lamban namun mudah dimengerti. Angka n yang perlu difaktorkan dibagi bulat dengan bilangan yang lebih besar dari 1 dan lebih kecil dari n.
Faktorisasi roda: Menggunakan Saringan Eratosthenes.
Algoritma rho Pollard: Ditemukan oleh John Pollard pada tahun 1975.
Faktorisasi kurva eliptik Lenstra
Faktorisasi Euler

Referensi

↑ Kleinjung; et al. (2010-02-18). "Factorization of a 768-bit RSA modulus" (PDF). International Association for Cryptologic Research. Diarsipkan (PDF) dari versi aslinya tanggal 2010-03-31. Diakses tanggal 2010-08-09.{{cite journal}}: Kutipan journal memerlukan |journal=; Penggunaan et al. secara eksplisit dalam: |author=