www.wikidata.id-id.nina.az

Faktorisasi prima adalah pecahan bilangan komposit yang terdiri dari bilangan bilangan pembagi yang lebih kecil dan hasi

Faktorisasi prima

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.

Gambar di atas menunjukkan proses faktorisasi angka 864.
Masalah yang belum terpecahkan dalam Ilmu komputer:

Apakah faktorisasi prima bisa dicapai dalam waktu polinomial?

(lebih banyak masalah yang belum terpecahkan dalam Ilmu komputer)

Sampai sekarang ini masih belum ditemukan algoritme faktorisasi non-kuantum yang efisien. Suatu percobaan 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 algoritme 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 algoritme 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 Sunting

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

Algoritme Sunting

Berikut adalah beberapa contoh algoritme faktorisasi prima:

  • Percobaan pembagian (Trial division): Algoritme 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.
  • Algoritme rho Pollard: Ditemukan oleh John Pollard pada tahun 1975.
  • Faktorisasi kurva eliptik Lenstra
  • Faktorisasi Euler

Referensi Sunting

  1. Kleinjung; et al. (2010-02-18). "Factorization of a 768-bit RSA modulus" (PDF). International Association for Cryptologic Research. (PDF) dari versi asli tanggal 2010-03-31. Diakses tanggal 2010-08-09. 

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

  • l
  • b
  • s
wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
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 Gambar di atas menunjukkan proses faktorisasi angka 864 Masalah yang belum terpecahkan dalam Ilmu komputer Apakah faktorisasi prima bisa dicapai dalam waktu polinomial lebih banyak masalah yang belum terpecahkan dalam Ilmu komputer 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 algoritme 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 algoritme 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 SuntingTentukan 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 32 Tentukan hasil dari 9 261 3 displaystyle sqrt 3 9 261 nbsp dan 16 4 displaystyle sqrt 4 16 nbsp 9 261 3 displaystyle sqrt 3 9 261 nbsp Faktorisasi prima dari 9 261 adalah 33 dan 73 maka hasilnya adalah 7 x 3 21 16 4 displaystyle sqrt 4 16 nbsp Faktorisasi prima dari 16 adalah 24 maka hasilnya adalah 2 Algoritme SuntingBerikut adalah beberapa contoh algoritme faktorisasi prima Percobaan pembagian Trial division Algoritme 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 Algoritme rho Pollard Ditemukan oleh John Pollard pada tahun 1975 Faktorisasi kurva eliptik Lenstra Faktorisasi EulerReferensi Sunting Kleinjung et al 2010 02 18 Factorization of a 768 bit RSA modulus PDF International Association for Cryptologic Research Diarsipkan PDF dari versi asli tanggal 2010 03 31 Diakses tanggal 2010 08 09 Pemeliharaan CS1 Penggunaan et al yang eksplisit link nbsp Artikel bertopik matematika ini adalah sebuah rintisan Anda dapat membantu Wikipedia dengan mengembangkannya lbs Diperoleh dari https id wikipedia org w index php title Faktorisasi prima amp oldid 23865476