Frumtala

Úr Wikipediu, frjálsa alfræðiritinu

Frumtölur (eða prímtölur) eru allar þær náttúrulegu tölur sem ekki er unnt að deila með öðrum tölum en henni sjálfri og 1. ^[1] Talan 1 er ekki skilgreind sem frumtala þar sem hún er eining og gengur því upp í sérhverja náttúrulega tölu.

Efnisyfirlit

1 Nokkrar staðreyndir um frumtölur
2 Vöxtur frumtalna og umfang reikninga
3 Neðanmálsgreinar
4 Tenglar

[breyta] Nokkrar staðreyndir um frumtölur

Þær frumtölur sem eru lægri en 100 eru: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Til eru óendanlega margar frumtölur. Ef svo væri ekki getum við látið $P = \{ p_1, p_2, \dots, p_n \}$ tákna mengi allra frumtalna. Skoðum töluna $t = p_1 \cdot p_2 \cdot \dots \cdot p_n + 1$ . Sérhver frumtala í $P$ skilar þá 1 í leif þegar henni er deilt í $t$ . En þá er $t$ annað hvort frumtala sjálf sem er stærri en þær sem eru í $P$ , eða þá að hún er margfeldi frumtalna sem eru ekki meðal þeirra í $P$ . Hvoru tveggja er mótsögn, svo það fær ekki staðist að $P$ sé mengi allra frumtalna.
Það hefur ekki fundist lokuð formúla fyrir frumtölur. Stærsta frumtala sem fundist hefur er 44. Mersenne frumtalan, talan $232582657 - 1$ , sem fannst í september 2006. (Upplýsingar frá apríl 2007).
Frumtölur sem eru samliggjandi oddatölur, eins og til dæmis 17 og 19, 71 og 73 o.s.frv., eru nefndar tvíburafrumtölur (enska: twin primes).
Tala í tugakerfinu sem endar á 5 eða sléttri tölu getur ekki verið frumtala (nema hún sé 2 og 5). Ef þversumma tölunnar er deilanleg með 3 þá er talan sjálf deilanleg með 3. (T.d. er talan 5217 deilanleg með 3 því 5+2+1+7=15 er deilanleg með 3).
Sé deilt með 6 í frumtölu, sem er stærri en 5, verður afgangurinn alltaf annað hvort 1 eða 5. Því ef leifin er slétt er talan sjálf slétt, og ef afgangurinn er 3 má deila tölunni sjálfri með 3.
Litla setning Fermats segir að ef $p$ er frumtala, og $a$ er ósamþátta $p$ , þá er $a^{p-1} \equiv 1 (\text{mod } p)$ . Hún er gjarnan notuð til að sýna fram á að tala sé ekki frumtala. Almennari útgáfa hennar er notuð til að sýna fram á virkni RSA dulkóðunarkerfisins.

[breyta] Vöxtur frumtalna og umfang reikninga

Ef við lítum á $p_1, p_2, \dots$ sem óendanlega runu frumtalna, þá segir frumtalnasetningin okkur að frumtalan $p n$ sé u.þ.b. $n \cdot \ln(n)$ , og að matið batnar eftir því sem $n$ 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 í skugga um hvort tala $t$ sé frumtala með því að prófa að deila sérhverri náttúrulega tölu $k \leq \sqrt{t}$ í $t$ 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 $\sqrt{t} < 12$ . Í ljós kemur að 11 gengur 13 sinnum upp í 143, svo talan er ekki frumtala. Ástæðan fyrir því að kvarðatrótin nægir er sú að ef einhver tala $b > \sqrt{t}$ gengur upp í $t$ , þá er talan $a = \frac t b < \frac{t}{\sqrt{t}} = \sqrt{t}$ svo leit okkar fram að kvarðatrótinni af $t$ myndi finna þáttinn $a$ .
Reikniritið að ofan tekur $O(\sqrt{n})$ tíma sem er ekki margliða í stærð inntaksins (þ.e. fjöldi bita í $n$ ). Á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 í $n$ .

[breyta] Neðanmálsgreinar

↑ Einnig kemur fyrir að orðið „frumtala“ sé notað um fjöldatölur en slík orðanotkun er á undanhaldi. Orðið „prímtala“ er þó ætíð notað um tölur af því tagi sem eru til umfjöllunar hér.