„Frumtala“: Munur á milli breytinga
Efni eytt Efni bætt við
Ekkert breytingarágrip |
m Tók aftur breytingar 157.157.160.249 (spjall), breytt til síðustu útgáfu Moi |
||
Lína 15:
* Þæ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 frumtölu <math>p \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 í
Talið er að [[zetufall Riemanns]] geti gefið mikilvægar upplýsingar um dreifingu frumtalna.
| |||