Verifika tan-numri primi

Kif tuża l-verifika tan-numri primi

1. Ikteb Numru sħiħ. L-espressjonijiet huma aċċettati wkoll: 2^61-1, 10^12+39, 20!+1 jew 3711.
2. It-tweġiba tidher hekk kif tikteb; agħfas Iċċekkja biex tagħti aktar ħin lill-fattorizzazzjoni ta’ numru diffiċli.
3. Aqra l-verdett, il-Fattorizzazzjoni f’numri primi, l-Għadd tad-diviżuri, il-Prim ta’ qabel u l-Prim li jmiss. Il-pannell Għaliex jispjega kif waslet it-tweġiba, u Ikkopja l-fattorizzazzjoni tikkopja l-prodott tal-primi.
4. Biex telenka l-primi, imla Minn u Sa taħt Numri primi f’medda u agħfas Elenka n-numri primi.

In-numri sa 2048 bit (madwar 617-il ċifra) huma aċċettati, u kollox jaħdem fil-brawżer tiegħek.

X’jagħmel numru prim

Numru prim huwa numru sħiħ akbar minn 1 li d-diviżuri uniċi tiegħu huma 1 u hu nnifsu: 2, 3, 5, 7, 11, 13… Numru b’diviżuri oħra huwa komposit, u jista’ jinkiteb b’mod wieħed biss bħala prodott ta’ numri primi, il-fattorizzazzjoni f’numri primi tiegħu (360 = 2³ × 3² × 5). In-numri 0 u 1 la huma primi u lanqas komposti, u 2 huwa l-unika prim parigi.

L-għadd tad-diviżuri jiġi mill-fattorizzazzjoni: żid 1 ma’ kull esponent u immultiplika. 360 = 2³ × 3² × 5 għandu (3 + 1)(2 + 1)(1 + 1) = 24 diviżur. Prim għandu dejjem eżattament 2.

Kif jaħdem it-test

• In-numri żgħar (taħt miljun) jiġu ċċekkjati bid-diviżjoni b’tentattivi: jekk l-ebda prim sal-għerq kwadru ma jaqsam in-numru, huwa prim. M’hemmx għalfejn tkompli, għax numru komposit dejjem għandu fattur li mhuwiex akbar mill-għerq kwadru tiegħu.
• In-numri akbar l-ewwel jinqasmu b’kull prim taħt 1000, imbagħad jgħaddu mit-test ta’ Miller–Rabin. Bit-13-il bażi 2, 3, 5, …, 41, dan it-test ġie ppruvat eżatt għal kull numru taħt 3.3 × 10²⁴, li jinkludi l-intieri kollha ta’ 64 bit. Għal dawn in-numri t-tweġiba hija ċerta.
• Fuq 3.3 × 10²⁴ jintużaw 25 bażi u numru li jgħaddi minnhom kollha jiġi rrappurtat bħala prim probabbli. Il-probabbiltà ta’ żball hija inqas minn 1 f’10¹⁵, imma mhijiex prova matematika. Meta t-test jfalli, in-numru huwa żgur komposit.

Kif jiġu fattorizzati n-numri

Il-fatturi żgħar jinstabu bid-diviżjoni b’tentattivi. Il-partijiet kompositi akbar jinqasmu bl-algoritmu rho ta’ Pollard (il-varjant ta’ Brent), li jsib fatturi ta’ sa madwar 10 ċifri f’frazzjoni ta’ sekonda. In-numri aktar diffiċli, bħall-prodott ta’ żewġ primi ta’ 15-il ċifra jew aktar, jistgħu jieħdu ħafna aktar minn kwalunkwe limitu ta’ ħin, u għalhekk il-fattorizzazzjoni tieqaf wara ftit sekondi. L-aħħar fattur imbagħad jiġi mmarkat bħala komposit imma mhux maqsum, u meta terġa’ tagħfas Iċċekkja jingħata aktar ħin.

Primi f’medda

Il-lista tal-medda tuża għarbiel ta’ Eratostene segmentat, li jaqta’ l-multipli ta’ kull prim. Taċċetta sa 1,000,000 numru għal kull medda b’limitu ta’ fuq sa 10¹². L-għadd ikopri l-medda kollha, u jiġu elenkati l-ewwel 2,000 prim. Per eżempju, hemm 25 prim bejn 1 u 100 u 78,498 taħt miljun.