Kokonaislukujen tekijöihinjako

Matematiikassa kokonaislukujen tekijöihinjaolla tarkoitetaan hajotelmaa, missä annettu kakkosta suurempi kokonaisluku esitetään sen tekijöiden tulona. Jos kaikki kyseiset tekijät ovat alkutekijoitä, puhutaan luvun alkutekijähajotelmasta. Tämä hajotelma on kullekin luvulle yksikäsitteinen tekijöiden järjestystä lukuun ottamatta ja alkutekijöiden löytämiseksi on kehitetty useita algoritmeja. Nykyiset salakirjoitusmenetelmät perustuvat siihen, että annettu kokonaisluku on vaikea jakaa alkutekijöihin. Toistaiseksi ei tiedetä, onko tekijöihinjaolle olemassa nopeaa algoritmia, eli voidaanko b bitin pituinen kokonaisluku jakaa alkutekijöihin aikavaativuusluokassa O(bⁿ) jollakin kokonaisluvulla n.

Algoritmeja tekijöihin jakamiseen

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 $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.