O fea o mea nei e lē o se faavasegaga mo faafitauli: NP, co-NP, po o le RSA? I le taliina o le fesili na muamua atu, ia tusi se tala o loo iai le tali. E mafai ona faia i le 1 i le 20 fuaiupu. Faamatalaga:
O le integer factorization problem o le computational problem o le fuafuaina o le prime factorization o se integer ua tuuina mai. Pe a faaupuina o se faafitauli o le faia o se faaiʻuga, o le faafitauli lea o le filifili pe o iai se vaega o le faamatalaga o loo i totonu e itiiti ifo i le k. E leai se lelei integer factorization algorithm e iloa, ma o lenei mea moni e avea ma faavae o le tele o faiga cryptographic po nei, e pei o le RSA algorithm. O le faafitauli o le factorization integer o loo i le NP ma le co-NP (ma e oo lava i le UP ma le co-UP). Afai o le faafitauli e NP-atoa, o le polynomial taimi faatulagaga o le a pauu i lona tulaga muamua (ie, o le a NP tutusa co-NP). O le algorithm sili ona lauiloa mo integer factorization o le lautele numera fanua sieve, lea e ave taimi O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) e vaega se integer n-bit. Peitaʻi, o le algorithm e sili ona lauiloa mo lenei faafitauli, o le algorithm a Shor, e tamoʻe i le taimi o le polynomial. Ae paga lea, e lē o taʻu mai ai e lenei mea moni po o fea o loo iai le faafitauli e tusa ai ma vasega e lē o se tulaga lavelave.