Útgáfa síðunnar 11. mars 2013 kl. 18:44 breyta Cessator (spjall \| framlög) 50.763 breytingar Ekkert breytingarágrip ← Eldri breyting		Útgáfa síðunnar 11. mars 2013 kl. 21:28 breyta taka aftur þessa breytingu Moi (spjall \| framlög) Möppudýr, Stjórnendur 13.005 breytingar m →‎Vöxtur frumtalna og umfang reikninga Nýrri breyting →
Lína 14: * Ef við lítum á <math>p_1, p_2, \dots</math> sem óendanlega runu frumtalna, þá segir [[frumtalnasetning]]in okkur að frumtalan <math>p_n</math> sé u.þ.b. <math>n \cdot \ln(n)</math>, og að matið batnar eftir því sem <math>n</math> stækkar. * Þær eru mikið notaðar í [[dulkóðun]]. Sem dæmi eru þær undirstaða öryggis [[RSA]] reikniritsins, þar sem það að þátta tölu er talið vera erfitt og núverandi aðferðir ganga út á að hreinlega prófa alla mögulega þætti (sjá hér að neðan). * Hægt er að ganga úr skugga um hvort tala <math>t</math> sé frumtala með því að prófa að deila sérhverri ~~náttúrulegri tölu~~frumtölu <math>kp \leq \sqrt{t}</math> í <math>t</math> og athuga hvort leifin sé 0. Það nægir að athuga frumtölur á þessu bili ef þær upplýsingar eru til staðar. Sem dæmi er hægt að athuga hvort talan 143 sé frumtala með því skoða hvort einhver frumtalnanna 2, 3, 5, 7 og 11 gangi upp í 143. Við skoðum ekki 13 þar sem <math>\sqrt{t} < 12</math>. Í ljós kemur að 11 gengur 13 sinnum upp í 143, svo talan er ekki frumtala. Ástæðan fyrir því að [[kvarðatrót]]in nægir er sú að ef einhver tala <math>b > \sqrt{t}</math> gengur upp í <math>t</math>, þá er talan <math>a = \frac t b < \frac{t}{\sqrt{t}} = \sqrt{t}</math> svo leit okkar fram að kvarðatrótinni af <math>t</math> myndi finna þáttinn <math>a</math>. * Reikniritið að ofan tekur <math>O(\sqrt{n})</math> tíma sem er ekki margliða í stærð inntaksins (þ.e. fjöldi bita í <math>n</math>). Árið 2004 sýndu þrír nemendur við IIT Kanpur, þeir Agrawal, Kayal og Saxena, fram á að unnt er að athuga hvort tala sé frumtala eða ekki í tíma sem er margliða í fjölda bita í <math>n</math>.

„Frumtala“: Munur á milli breytinga