Ing ngisor iki endi sing dudu jeneng mburi wong: Shor utawa RSA? Ing pitakonan sadurungé, tulis konteks sing isiné jawabané. Bisa 1 - 20 ukara. Kontèks:
Masalah faktorisasi wilangan bulat yaiku masalah komputasi kanggo nemtokake faktorisasi prima saka wilangan bulat tartamtu. Ditulis minangka masalah kaputusan, iku masalah saka panentu apa input wis faktor kurang saka k. Ora ana algoritma faktorisasi integer sing efisien sing dingerteni, lan kasunyatan iki dadi dhasar sawetara sistem kriptografi modern, kayata algoritma RSA. Masalah faktorisasi wilangan bulat ana ing NP lan ing co-NP (lan uga ing UP lan co-UP). Yèn masalah iku NP-lengkap, hiérarki wektu polinomial bakal ambruk menyang tingkat pisanan (yaiku, NP bakal padha karo co-NP). Algoritma kang paling misuwur kanggo faktorisasi wilangan bulat ya iku general number field sieve, kang mbutuhaké wektu O(e(64/9)1/3(n.log 2)1/3(log (n.log 2))2/3) kanggo faktorisasi wilangan bulat n-bit. Nanging, algoritma kuantum sing paling misuwur kanggo masalah iki, algoritma Shor, mlaku ing wektu polinomial. Sayange, kasunyatan iki ora ngomong akeh babagan ngendi masalah dumunung gegayutan karo kelas kerumitan non-kuantum.