Kuidas kontrollida, kas number on esmane

Algarvud on need, mis jaguvad ainult iseenda ja 1-ga; kõiki teisi nimetatakse liitarvudeks. Kuigi primaalsuse testimiseks on mitmeid viise, on ka kompromisse. Täiuslikud testid on olemas, kuid need on suurte arvude puhul äärmiselt aeglased, samas kui palju kiiremad võivad anda valetulemusi. Siin on mõned valikud, mille vahel valida olenevalt sellest, kui suurt arvu te testite.

1
Proovijaotuse test. Jagage n iga algarvuga 2-st korruseni (n{displaystyle {sqrt {n}}}).

2
Fermat’ väike teoreem. Hoiatus: valepositiivsed tulemused on võimalikud isegi kõigi a väärtuste puhul. Valige a jaoks täisarv, et 2 ≤ a ≤ n – 1. Kui an (mod n) = a (mod n), siis n on tõenäoliselt esinumber. Kui see ei vasta tõele, ei ole n algväärtus. Korrake toimingut a erinevate väärtustega, et suurendada usaldust primaalsuse suhtes

3
Milleri-Rabini test. Hoiatus: valepositiivsed tulemused on võimalikud, kuid harva a mitme väärtuse korral. Otsige s-le ja d-le väärtused nii, et n−1=2s∗d{displaystyle n-1=2^{s}*d}. Valige väärtusele täisarv. a selline, et 2 ≤ a ≤ n – 1. Kui ad = +1 (mod n) või -1 (mod n), siis n on tõenäoliselt algväärtus. Jätke testi tulemuse juurde. Muul juhul minge järgmise sammu juurde. Pange oma vastus ruutu (a2d{displaystyle a^{2d}}). Kui see võrdub -1 (mod n), siis n on tõenäoliselt algväärtus. Jätke testi tulemuse juurde. Vastasel korral korrake (a4d{displaystyle a^{4d}} jne) kuni a2s−1d{displaystyle a^{2^{s-1}d}}. Kui teete kunagi ruudus arvu, mis ei ole ±1{ displaystyle pm 1} (mod n) ja tulemuseks on +1 (mod n), siis n ei ole algväärtus. Kui a2s−1d≠±1{displaystyle a^{2^{s-1}d}neq pm 1} (mod n), siis n ei ole esmane. Testi tulemus: kui n läbib testi, korrake kindlustunde suurendamiseks erinevad a väärtused.

4
Mõistke proovijaotuse meetodit. Primaalsuse definitsiooni järgi on n algväärtus ainult siis, kui seda ei saa jagada võrdselt täisarvudega 2 või suuremate arvudega. Antud valem säästab aega, eemaldades mittevajalikud testid (nt pärast 3. testimist pole vaja 9 testida). Põrand(x) ümardab x lähima täisarvuni ≤ x.

5
Modulaararitmeetika mõistmine. Operatsioon “x mod y” (lühend sõnast “modulo”) tähendab “jagage x y-ga ja leidke jääk”. Teisisõnu, moodularitmeetikas “keeravad arvud ümber” tagasi nulli, kui saavutavad teatud väärtuse, mida nimetatakse mooduliks. Kell loeb moodulis 12: see liigub 10-lt 11-le 12-le, seejärel pöördub tagasi väärtuseni 1. Paljudel kalkulaatoritel on mod-nupp, kuid vaadake selle jaotise lõpust, kuidas seda suurte arvude puhul käsitsi lahendada.

6
Teadke Fermat’ väikese teoreemi lõkse. Kõik arvud, mis selles testis läbi kukuvad, on liitarvud (mitte algarvud), kuid kahjuks on selle testi läbinud arvud ainult tõenäolised algarvud. Kui soovite olla kindel, et väldite valepositiivseid tulemusi, otsige loendist “Carmichaeli numbrid” (mis läbivad selle testi iga kord) ja “Fermati pseudoalgarvud” (mis läbivad selle testi ainult mõne a väärtuse korral).

7
Kasutage Miller-Rabini testi alati, kui see on praktiline. Kuigi käsitsi sooritamine on tüütu, kasutatakse seda testi tavaliselt tarkvaras. Seda saab teha praktilise kiirusega ja see annab vähem valepositiivseid tulemusi kui Fermat’ meetod. Liitarv ei anna kunagi valepositiivset tulemust rohkem kui ¼ a väärtustest. Kui valite juhuslikult mitu a väärtust ja need kõik läbivad selle testi, võite olla üsna kindel, et n on algväärtus.

8
Tehke suurte arvude jaoks modulaarne aritmeetika. Kui teil pole juurdepääsu modifikatsioonifunktsiooniga kalkulaatorile või kui teie kalkulaator ei suuda kuvada nii suuri numbreid, kasutage protsessi hõlbustamiseks eksponentide omadusi ja moodularitmeetikat. Siin on näide 350{displaystyle 3^{50}} mod 50 jaoks: kirjutage avaldis ümber paremini hallatavate eksponentide abil: (325∗325){displaystyle (3^{25}*3^{25})} mod 50. (Käsitsi arvutamisel võib tekkida vajadus selle täpsemaks jaotamiseks).(325–325){displaystyle (3^{25}*3^{25})} mod 50 = (325{displaystyle (3^{25) }} mod 50 ∗325{displaystyle *3^{25}} mod 50) mod 50. (See on modulaarse korrutamise omadus.)325{displaystyle 3^{25}} mod 50 = 43.(325 {displaystyle (3^{25}} mod 50 ∗325{displaystyle *3^{25}} mod 50) mod 50 = (43∗43){displaystyle (43*43)} mod 50=1849{ displaystyle =1849} mod 50=49{displaystyle =49}

9
Valige kaks numbrit. Üks numbritest ei ole algarv ja teine ​​number on arv, mille algarvu tuleb testida.”Algus1″ = 35Algus2 = 97

10
Valige kaks andmepunkti, mis on suuremad kui null ja väiksemad kui prime1 ja prime2. Need ei saa olla üksteisega võrdsed. Andmed1 = 1Andmed2 = 2

11
Arvutage MMI (matemaatika korduv pöördvõrdeline) algarvude 1 ja algarvu jaoks. Arvutage MMIMMI1 = Prime2 ^ -1 Mod Prime1MMI2 = Algarvu1 ^ -1 Mod Prime2 Ainult algarvude jaoks (see annab arvu mittealgarvude jaoks, kuid see ei ole selle MMI): MMI1 = (Prime2 ^ (Prime1-2)) % Algväärtus1MMI2 = (Prae1 ^ (Prame2-2)) % Prime2e.gMMI1 = (97 ^ 33) % 35MMI2 = (35 ^ 95) % 97

12
Looge iga MMI jaoks binaartabel kuni Log2-ni ModulusFor MMI1F(1) = Prime2 % Prime1 = 97 % 35 = 27F(2) = F(1) * F(1) % Prime1 = 27 * 27 % 35 = 29F(4) = F(2) * F(2) % Algväärtus1 = 29 * 29 % 35 = 1F(8) = F(4) * F(4) % Algväärtus1 = 1 * 1 % 35 = 1F( 16) =F(8) * F(8) % Algväärtus1 = 1 * 1% 35 = 1F(32) =F(16) * F(16)% Algväärtus1 = 1 * 1% 35 = 1 Arvutage kahendväärtus Algväärtus1 – 235 -2 = 33 (10001) alus 2MMI1 = F(33) = F(32) * F(1) mod 35MMI1 = F(33) = 1 * 27 Mod 35MMI1 = 27 MMI2F(1) jaoks = Prime1 % Prime2 = 35°% 97 = 35F(2) = F(1) * F(1) % Prime2 = 35 * 35 mod 97 = 61F(4) = F(2) * F(2)% Prime2 = 61 * 61 mod 97 = 35F(8) = F(4) * F(4) % Prime2 = 35 * 35 mod 97 = 61F(16) = F(8) * F(8) % Prime2 = 61 * 61 mod 97 = 35F(32) = F(16) * F(16) % Prime2 = 35 * 35 mod 97 = 61F(64) = F(32) * F(32) % Prime2 = 61 * 61 mod 97 = 35F (128) = F(64) * F(64) % Algväärtus2 = 35 * 35 mod 97 = 61 Arvutage Prime2 binaar – 297 – 2 = 95 = (1011111) alus 2MMI2 = (((((F(64)) * F(16) % 97) * F(8) % 97) * F (4)% 97) * F(2)% 97) * F(1)% 97) MMI2 = ((((35 * 35) %97) * 61)% 97) * 35% 97 ) * 61 % 97) * 35 % 97) MMI2 = 61

13
Arvutage (Data1 * Prime2 * MMI1 + Data2 * Prime1 * MMI2) % (Prime1 * Prime2) Vastus = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35) Vastus = (2619 + 4270)  % 3395 vastus = 99

14
Veenduge, et “Prime1” ei ole algarvutus (Answer – Data1) % Prime199 -1 % 35 = 28Kuna 28 on suurem kui 0, siis 35 ei ole algväärtus

15
Kontrollige, kas Prime2 on PrimeCalculate (Vastus – Data2) % Prime299 – 2 % 97 = 0 Kuna 0 võrdub 0, on 97 potentsiaalselt algväärtus

16
Korrake samme 1 kuni 7 veel vähemalt kaks korda. Kui samm 7 on 0: kasutage erinevat algarvu 1, kus algnumber1 ei ole algarvuks Kasutage erinevat algarvu 1, kus algnumber 1 on tegelik algväärtus. Sel juhul peaksid sammud 6 ja 7 võrduma 0-ga. Kasutage andme1 ja data2 jaoks erinevaid andmepunkte. Kui samm 7 on iga kord 0, on väga suur tõenäosus, et algarvuks2 on algväärtus. Sammud 1 kuni 7 nurjuvad teatud juhtudel juhud, kui esimene arv on mittealgarv ja teine ​​algarv on mittealgaarv “algav1” tegur. See töötab kõigis stsenaariumides, kus mõlemad arvud on algarvud. Põhjus, miks samme 1 kuni 7 korratakse, on see, et on mõned stsenaariumid, kus isegi siis, kui algnumber1 ei ole algarvu ja algnumber2 ei ole algarvud, osutub samm 7 siiski nulliks, ühe või mõlema numbri jaoks. Need asjaolud on haruldased. Kui algarvu1 muudetakse erinevaks mittealgarvuks, kui algarvud2 ei ole algarvud, ei võrdu algarvud 7. sammus kiiresti nulliga. Algarvud on sammus 7 alati võrdsed nulliga, välja arvatud juhul, kui “alg1” on algarvu 2 tegur. .