Kokonaislukujen tekijöihinjako

Jokainen kokonaisluku voidaan jakaa alkutekijöihin käymällä läpi kaikki luvun neliöjuurta pienemmät alkuluvut ja katsomalla, onko luku jaollinen kyseisellä alkuluvulla. Tämä on kuitenkin varsin tehotonta. Toistaiseksi nopein tunnettu menetelmä alkulukuhajotelman löytämiseen on niin sanottu yleinen lukukuntaseula -menetelmä, joka jakaa b-bitin kokoisen luvun n alkutekijöihin ajassa ${\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right)}$. Jos kuitenkin joku onnistuu rakentamaan toimivan kvanttitietokoneen, voidaan tällä koneella jakaa luvut alkutekijöihin polynomiaalisessa ajassa Peter Shorin kehittämällä algoritmilla. Vuonna 2001 saatiin rakennettua seitsemällä kubitillä toimiva kvanttitietokone, joka jakoi luvun 15 onnistuneesti alkutekijöihin.

Toistaiseksi ei tiedetä, mihin aikavaativuusluokkaan tekijöihinjakamisongelma kuuluu. Se, onko annetulla luvulla n alkutekijää, joka on pienempi kuin M on nimeltään tekijöihinjaon päätösongelma. Sen tiedetään olevan sekä NP että co-NP. Tämä siksi, että voidaan tarkistaa kyllä- ja ei-vastaukset annetuille tekijäehdokkaille jos ne tiedetään alkuluvuiksi tai yhdistetyiksi luvuiksi. Tekijöihinjaon tiedetään olevan BQP Shorin algoritmin perusteella. Tekijöihinjaosta oletetaan, että se ei kuulu luokkiin P, NP-täydellinen eikä co-NP-täydellinen. Jos onnistutaan osoittamaan, että ongelma ei ole NP-täydellinen eikä co-NP-täydellinen, tulee samalla osoitettua, että NP = co-NP. Tulos olisi hämmästyttävä, joten nykyään uskotaankin, että tekijöihinjako ei kuulu näihin luokkiin. Monet ovat yrittäneet tuloksetta löytää polynomiaalista algoritmia tekijöihinjaolle, joten epäillään, että tekijöihinjako ei ole P-ongelma.

Sen sijaan annetun luvun toteaminen yhdistetyksi luvuksi on helpompaa kuin sen tekijöiden etsiminen. Tämä ongelma voidaan ratkaista polynomiaalisessa ajassa AKS alkulukutestin avulla. On myös kehitetty monia probabilistisiä testejä luvun alkuluvuksi osoittamiseen. Monet näistä ovat nopeita, mutta ne eivät anna täydellistä varmuutta sille, onko annettu luku alkuluku. Alkulukutestauksen helppous on tärkeä osa RSA-algoritmia, jossa on välttämätöntä löytää suuria alkulukuja.