Frumtölupróf og frumþáttun

Hvernig á að nota frumtöluprófið

1. Sláðu inn Heil tala. Segðir eru líka teknar gildar: 2^61-1, 10^12+39, 20!+1 eða 3711.
2. Svarið birtist jafnóðum; ýttu á Athuga til að gefa þáttuninni meiri tíma á erfiðri tölu.
3. Lestu niðurstöðuna, Frumþáttun, Fjöldi deila, Fyrri frumtala og Næsta frumtala. Hlutinn Hvers vegna útskýrir hvernig svarið fékkst og Afrita frumþáttun afritar margfeldi frumtalnanna.
4. Til að telja upp frumtölur fyllirðu út Frá og Til undir Frumtölur á bili og ýtir á Telja upp frumtölur.

Tölur upp í 2048 bita (um 617 tölustafir) eru teknar gildar og allt keyrir í vafranum þínum.

Hvað gerir tölu að frumtölu

Frumtala er heil tala stærri en 1 sem hefur engan annan deili en 1 og sjálfa sig: 2, 3, 5, 7, 11, 13 … Tala með aðra deila er samsett og hana má skrifa á nákvæmlega einn hátt sem margfeldi frumtalna, frumþáttun hennar (360 = 2³ × 3² × 5). Tölurnar 0 og 1 eru hvorki frumtölur né samsettar tölur og 2 er eina slétta frumtalan.

Fjöldi deila fæst út frá frumþáttuninni: bættu 1 við hvern veldisvísi og margfaldaðu. 360 = 2³ × 3² × 5 hefur (3 + 1)(2 + 1)(1 + 1) = 24 deila. Frumtala hefur alltaf nákvæmlega 2.

Hvernig prófið virkar

• Litlar tölur (undir einni milljón) eru athugaðar með því að prófa deilingu: ef engin frumtala upp að kvaðratrótinni gengur upp í töluna er hún frumtala. Ekki þarf að fara lengra, því að samsett tala hefur alltaf þátt sem er ekki stærri en kvaðratrót hennar.
• Stærri tölur eru fyrst deildar með öllum frumtölum undir 1000 og síðan sendar í gegnum Miller–Rabin-prófið. Með 13 grunntölum, 2, 3, 5, …, 41, er þetta próf sannað nákvæmt fyrir allar tölur undir 3,3 × 10²⁴, sem nær yfir allar 64 bita heiltölur. Fyrir þessar tölur er svarið öruggt.
• Yfir 3,3 × 10²⁴ eru notaðar 25 grunntölur og tala sem stenst þær allar er sögð líkleg frumtala. Líkurnar á villu eru undir 1 á móti 10¹⁵, en það er ekki stærðfræðileg sönnun. Þegar prófið fellur er talan örugglega samsett.

Hvernig tölur eru þáttaðar

Litlir þættir finnast með því að prófa deilingu. Stærri samsetta hluta er skipt með rho-reiknirit Pollards (afbrigði Brents), sem finnur þætti allt að um 10 tölustöfum á broti úr sekúndu. Erfiðari tölur, til dæmis margfeldi tveggja frumtalna með 15 tölustöfum eða fleiri, geta tekið mun lengri tíma en nokkur tímamörk, svo að þáttun stöðvast eftir nokkrar sekúndur. Síðasti þátturinn er þá merktur sem samsettur en ekki þáttaður, og með því að ýta aftur á Athuga fær hann meiri tíma.

Frumtölur á bili

Upptalning á bili notar bútaða sigti Eratosþenesar, sem strikar út margfeldi hverrar frumtölu. Hún tekur við allt að 1 000 000 tölum á bili með efri mörk upp í 10¹². Talningin nær yfir allt bilið og fyrstu 2000 frumtölurnar eru taldar upp. Til dæmis eru 25 frumtölur á milli 1 og 100 og 78 498 undir einni milljón.