Tegemist on masintõlkega; originaaltekst on inglise keeles. Loe originaali
Algarvud harvenevad kiirusel, mida saab nimetada
1024-bitise arvu lähedal on üks paaritu arv 355-st algarv. See ei ole väike tõenäosus ja see on ainus põhjus, miks avaliku võtme krüptograafia on üldse võimalik.
25 algarvu jääb alla 100, 168 alla 1000 ja 78,498 alla miljoni. Arvud vähenevad, kuid need ei lõpe kunagi, ning kiirus, millega algarvud harvenevad, on matemaatika üks kasulikumaid fakte.
Üks ln n-st
Arvu n lähedal on umbes üks arv ln n-st algarv. Alla 100 ennustab see 100 / ln 100 = 21.7 algarvu ning Prime Sieve kuvab täpselt selle tegeliku arvu 25 kõrval koos 13.1% veaga.
Hinnang on siin ligikaudne ja see paraneb. Miljoni juures annab N / ln N tulemuseks 72,382 tegeliku 78,498 vastu, mis teeb veaks 7.8%. Suhteline viga väheneb N kasvades, mis ongi algarvuteoreemi tegelik sisu.
Parem hinnang, mis näib halvem
Tööriist kuvab ka teise lähenduse, logaritmilise integraali Li(N). Kui N = 100, annab see tulemuseks 29.1 ja on toorest valemist halvem: viga on 16.3% võrreldes 13.1%-ga.
Kes loeks ainult seda rida, järeldaks, et keerulisemat valemit pole mõtet kasutada. Kui aga N-i muuta, pöördub järjestus vastupidiseks ega taastu enam kunagi:
- N = 100: N/lnN eksib 13.1%, Li eksib 16.3%
- N = 1000: N/lnN eksib 13.8%, Li eksib 5.1%
- N = 10⁶: N/lnN eksib 7.8%, Li eksib 0.16%
Li ei ole niivõrd valemi N / ln N täpsustus, kuivõrd selle ausam versioon. Lihtne valem rakendab tihedust kohal n kogu vahemikule 0-st n-ni, kuigi tihedus 2 lähedal on väga erinev tihedusest miljoni lähedal. Li integreerib avaldist 1/ln t üle kogu vahemiku, selle asemel et pidada seda konstantseks, ning tasuks on viga vaid üks osa kuuesajast seal, kus lihtsustus eksib ikka veel 8%.
Lähenduse ühekordne arvutamine ei ütle midagi selle kohta, kas see on hea. Vaja on jälgida selle käitumist sisendi kasvades.
Miks need kunagi otsa ei lõpe
Sest 1/ln n kahaneb aeglaselt. Selle summa hajub, seega on algarve hõredalt, kuid mitte piisavalt hõredalt, et neid oleks lõplik arv.
Eukleidese tõestus on otsesem ja vanem. Võta mis tahes lõplik algarvude loend, korruta need omavahel ja liida üks. Tulemus annab jäägi 1, kui seda jagada mis tahes loendis oleva algarvuga, seega puuduvad selle kõik algtegurid sinu loendist. Ükski lõplik loend ei saa olla täielik.
Tööriista ülejäänud kaks näitu viitavad sellele, kui palju on veel lahtine. See loendab 8 kaksikalgarvude paari alla 100 ning esitab suurimaks vaheks 8. Kas kaksikalgarvude paarid jätkuvad lõputult, on tõestamata, nagu ka hüpotees, et järjestikuste ruutude vahel asub alati mõni algarv.
Arv, mis määrab võtme suuruse
RSA-võtme genereerimine tähendab suurte algarvude leidmist ning meetod seisneb õige suurusega juhusliku paaritu arvu valimises ja selle kontrollimises.
Kui kaua see aega võtab, ongi otseselt tiheduse küsimus. 1024-bitine arv on arvu 2¹⁰²⁴ lähedal ja ln(2¹⁰²⁴) = 1024 × ln 2 = 710. Seega on selle läheduses umbes üks arv 710-st algarv ja kuna kontrollitakse ainult paarituid kandidaate, siis üks 355-st.
Kolmsada viiskümmend viis katset, millest igaüks on kiire tõenäosuslik algarvulisuse test. Seetõttu võtab võtme genereerimine hetke, mitte geoloogilise ajastu, ning kogu ajakulu tuleneb logaritmist. Kui eksponenti suurendada, kasvab kulu bitipikkuses lineaarselt, mistõttu on 2048-bitised ja 4096-bitised võtmed jätkuvalt praktilised.
Kui algarvud oleksid harvenenud kas või pisut kiiremini, näiteks nagu 1/n, oleks otsing lootusetu ning internet põhineks millelgi muul.
Keegi ei tõesta kasutusel olevaid algarve
Üks detail teeb need 355 katset odavaks: test ei tee kindlaks algarvulisust.
Miller-Rabin valib juhusliku tunnistaja ja esitab küsimuse, millele iga algarv vastab ühtemoodi. Liitarv võib vastata nagu algarv, kuid kõige rohkem veerand võimalikest tunnistajatest lubab tal seda teha, seega vähendab iga sõltumatu voor petta saamise tõenäosust vähemalt neli korda. Neljakümne vooru järel jääb halvim juhtum alla 4⁻⁴⁰, mis on umbes 10⁻²⁴.
See on märgatavalt väiksem kui avastamata mäluvea tõenäosus arvutusi tegevas masinas. Kogu maailma andmeliiklust kaitsvad võtmed põhinevad arvudel, mis on peaaegu kindlasti algarvud, ning jääkkahtlus on väiksem kui riistvara oma.