Ki nan sa ki annapre yo se pa yon klasifikasyon pou pwoblèm: NP, ko-NP, oswa RSA? Anviwon kesyon anvan an, ekri yon kontèks ki gen repons lan ladan l. Li kapab 1 - 20 fraz. Kontèks:
Pwoblèm faktorizasyon antye a se pwoblèm konpitasyonèl pou detèmine faktorizasyon prensipal yon antye bay. Fraze kòm yon pwoblèm desizyon, li se pwoblèm nan deside si wi ou non opinyon an gen yon faktè mwens pase k. Pa gen okenn algoritm efikas faktorize antye li te ye, ak reyalite sa a fòme baz la nan plizyè sistèm modèn kriptografik, tankou algoritm RSA la. Pwoblèm nan faktorize antye se nan NP ak nan ko-NP (e menm nan UP ak ko-UP). Si pwoblèm nan se NP-konplè, polynomial tan yerachi a pral tonbe nan premye nivo li yo (sa vle di, NP pral egal a co-NP). Algoritm ki pi byen li te ye pou faktorize antye se filtè jaden nimewo jeneral la, ki pran tan O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) pou faktorize yon antye n-bit. Sepandan, pi bon konnen algoritm Quantum pou pwoblèm sa a, algorithm Shor a, pa kouri nan tan polynomial. Malerezman, reyalite sa a pa di anpil sou kote pwoblèm nan manti ak respè nan klas konpleksite ki pa quantum.