Care dintre următoarele nu este un algoritm: RSA, NP sau situl general de câmp numeric? Având în vedere întrebarea anterioară, scrie un context care conține răspunsul. Poate fi de la 1 la 20 de propoziţii. Contextul:
Problema de factorizare a numerelor întregi este problema computațională de determinare a factorizării prime a unui anumit număr întreg. Exprimată ca o problemă de decizie, este problema de a decide dacă intrarea are un factor mai mic decât k. Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, iar acest fapt formează baza mai multor sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizării numerelor întregi este în NP și în co-NP (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia timpului polinomial se va prăbuși la primul său nivel (adică, NP va fi egal cu co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este situl general al câmpului numeric, care necesită timp O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) pentru factorizarea unui număr întreg de n biți. Cu toate acestea, cel mai cunoscut algoritm cuantic pentru această problemă, algoritmul lui Shor, funcționează în timp polinomic. Din păcate, acest fapt nu spune prea multe despre unde se află problema cu privire la clasele de complexitate non-cuantică.