Watter van die volgende is nie iemand se van nie: Shor of RSA? Skryf 'n konteks wat die antwoord bevat, gegewe die vorige vraag. Dit kan 1 - 20 sinne wees. Konteks:
Die heelgetal faktorisering probleem is die rekenaar probleem van die bepaling van die eerste faktorisering van 'n gegewe heelgetal. Dit is die probleem om te besluit of die insette 'n faktor kleiner as k het. Geen doeltreffende heelgetal faktorisering algoritme is bekend nie, en hierdie feit vorm die basis van verskeie moderne kriptografiese stelsels, soos die RSA algoritme. Die heelgetal faktorisering probleem is in NP en in co-NP (en selfs in UP en co-UP). As die probleem NP-volledig is, sal die polinoom tyd hiërargie ineenstort tot sy eerste vlak (dit wil sê, NP sal gelyk wees aan co-NP). Die bekendste algoritme vir heelgetal faktorisering is die algemene getal veld sif, wat tyd neem O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) om 'n n-bis heelgetal te faktoriseer. Die bekendste kwantum algoritme vir hierdie probleem, Shor se algoritme, loop egter in polinoom tyd. Ongelukkig, hierdie feit sê nie veel oor waar die probleem lê met betrekking tot nie-kwantum kompleksiteit klasse.