Primaalsuse kontrollija
Testige, kas arv on algarv, ja vaadake täpselt, miks: tõeline proovijaotus kuni √n väikeste ja keskmiste arvude jaoks ning ehtne Milleri-Rabini ülevaade krüptograafiasuuruste arvude jaoks.
Tulemus
Primaalsuse kontrollija ütleb teile, kas täisarv on algarv, ja erinevalt enamikust võrgukalkulaatoritest näitab tegelikku algoritmi, mis seda tõestas, mitte vahemällu salvestatud otsingutabelit. Sisestage mis tahes täisarv, positiivne või negatiivne, väike või tohutu, ja tööriist otsustab selle suuruse põhjal, millist tegelikku algoritmi käivitada.
Arvude puhul, mis on väiksemad kui 10¹² (üks triljon), teostab see ehtsat proovijaotust: alustades numbrist 2, proovib see võimaliku jagajana iga kandidaati kuni √n alampiirini, peatades hetke, kui üks jagab ühtlaselt (liit) või kinnitades, et ükski ei jaga, kui iga kuni √n kandidaat on kontrollitud (alim). Suurte kandidaatide arvu korral piirdub kuvatav jälg esimesele ~18 katsele pluss viimasele, kusjuures aus märkus selle kohta, kui palju kandidaate ekraanil vahele jäeti, kuid tegelikult kontrollitakse koodi järgi iga üksikut kandidaati, arvutuses ei jäeta ühtegi kandidaati vahele.
Sellel lävel (krüptograafias kasutatav suurusvahemik) olevate või sellest suuremate arvude puhul võtaks proovijagamine liiga kaua aega, nii et tööriist lülitub Milleri-Rabini primaalsustestile fikseeritud, deterministliku 13 peamise tunnistaja komplektiga (2, 3, 5, 7, 11, 13, 17, 19, 9, 3, 3). See täpne tunnistajate kogum on hästi tuntud tulemus: sellel pole valepositiivseid tulemusi ühegi n-i puhul, mis on alla 3 317 044 064 679 887 385 961 981 (umbes 3,3 × 10²⁴), mis on arvutusliku kontrolliga kindlaks määratud (vt Sorenson & Webster, retermineeritud ja laiaulatuslik tabel 2015. kuulub). Üle selle piiri jookseb endiselt sama test, kuid tööriist ütleb teile ausalt, et garantii muutub pigem väga tugevaks tõenäosuslikuks kui matemaatiliseks kindluseks.
Milleri-Rabini jälg kirjutab n − 1 = 2ˢ × d koos d paarituga, seejärel läbib tõelise BigInti modulaarse astenduse – ruut ja korrutamine, vähendades moodulit n igal sammul, nii et numbrid ei plahvataks kunagi – esimese tunnistaja puhul tükihaaval, ja teatab iga tunnistaja liitarvust, kui tunnistaja ei osutu, sealhulgas see, kumb ei osutu. Kõik töötab teie brauseris lokaalselt: serverit, välist API-t ega andmeid teie seadmest ei välju.
Teie failid ja sisendid ei lahku sellest seadmest kunagi. Töötlemine toimub täiesti võrguühenduseta. 100% turvaline.
Aktsepteeritud vormingud ja reeglid
- Proovijagamisjälg: kandidaadid vahemikus 2 kuni √n, koos jagajaga, mis tõestab komposiiti, või ausa '√n kontrollitud, jagajat ei leitud' ürgsuse tõend.
- Deterministlik Miller–Rabin esimese 13 peamise tunnistajaga (2 kuni 41) – osutunud õigeks alla 3 317 044 064 679 887 385 961 981 (≈3,3 × 10²⁴).
- Tõeline BigInti ruudu ja korrutamise modulaarne eksponentsiaaljälg, mis on ükshaaval, nii et näete, kuidas a(^d) mod n tegelikult arvutatakse.
Peamised eelised
Kasutusjuhtumid
- • Kontrollige arvu esmatähtsust diskreetse matemaatika või CS-i kodutöö jaoks, vaadates samal ajal tegelikku proovijaotust või Miller-Rabini samme, mitte ainult jah/ei vastust.
- • Mõistusega kontrollige suurt kandidaadi algarvu, õppides samal ajal, kuidas RSA ja teised krüptosüsteemid tuginevad tegelikule Milleri-Rabini algoritmile, kusjuures modulaarset eksponentsimist jälgitakse bittide kaupa.
- • Enne sellele eeldusele täiendava loogika loomist veenduge kiiresti, kas konkreetne arv, mis pidevalt mõistatuses või ülesannete komplektis kuvatakse, on peamine.
Hinda seda tööriista
