Sisältö

• Astua
• Tapa 1/4: Yritä jakaa
• Menetelmä 2/4: Fermatin pienen lauseen käyttö
• Menetelmä 3/4: Miller-Rabin-testin käyttö
• Menetelmä 4/4: Kiinalaisen lauseen käyttö
• Vinkkejä
• Tarpeet

Pääluvut ovat numeroita, jotka ovat vain jaettavissa itsestään ja joita kutsutaan 1 - muiksi numeroiksi yhdiste numerot. Kun testataan, onko luku ensisijainen, on olemassa useita vaihtoehtoja. Jotkut näistä menetelmistä ovat suhteellisen yksinkertaisia, mutta eivät lainkaan käytännöllisiä suuremmille määrille. Muut usein käytetyt testit ovat itse asiassa kokonaisia ​​algoritmeja, jotka perustuvat yhteen todennäköisyys jotka joskus pitävät lukua virheellisesti ensisijaisena. Lue vaiheesta 1 oppiaksesi testaamaan itseäsi, jos kyseessä on alkuluku.

Astua

Tapa 1/4: Yritä jakaa

Jakamisen yrittäminen on ylivoimaisesti helpoin tapa testata numero. Pienille numeroille se on yleensä myös nopein tapa. Testi perustuu alkuluvun määritelmään: luku on alkuluku, jos se on jaettavissa vain itsestään ja 1.

1. Olettaa n on numero, jonka haluat testata. Jaa luku n kaikilla mahdollisilla jaettavilla kokonaisluvuilla. Suuremmille luvuille, kuten n = 101, on erittäin epäkäytännöllistä jakaa mahdollinen alle n: n pienempi kokonaisluku. Onneksi testattavien tekijöiden määrän vähentämiseksi on useita temppuja.
2. Määritä jos n jopa. Kaikki parilliset luvut ovat täysin jaettavissa 2: lla. Jos siis n on parillinen, voit sanoa sen n on yhdistetty luku (eikä siis alkuluku). Jos haluat nopeasti selvittää, onko numero tasainen, sinun on kiinnitettävä huomiota vain viimeiseen numeroon. Jos viimeinen numero on 2, 4, 6, 8 tai 0, luku on parillinen eikä alkuluku.
   • Ainoa poikkeus tälle säännölle on numero 2 itsessään, joka on myös ensisijainen, koska se on jaettavissa itsestään ja 1. 2 on ainoa tasainen prime.
3. Osa n millä tahansa numerolla välillä 2 ja n-1. Koska alkuluvulla ei ole muita tekijöitä kuin itsensä ja 1, ja koska kokonaislukukertoimet ovat pienempiä kuin niiden tulo, alle n: n ja yli 2: n kokonaisluvun jaettavuuden tarkistaminen määrittää, onko n alkuluku. Aloitamme 2: n jälkeen, koska parilliset luvut (2: n kerrannaiset) eivät voi olla alkulukuja. Tämä ei ole läheskään tehokas tapa testata, kuten näet alla.
   • Esimerkiksi, jos halusimme käyttää tätä menetelmää testataksemme, onko 11 ensisijainen vai ei, jakaamme 11 luvulla 3, 4, 5, 6, 7, 8, 9 ja 10 etsimällä kokonaislukuvastausta ilman loppuosaa. Koska mikään näistä numeroista ei sovi kokonaan 11: ään, voimme sanoa, että 11 on yksi on paras.
4. Ajan säästämiseksi testaa vain sqrt (n), pyöristetty. Numeron n testaaminen tarkistamalla kaikki numerot välillä 2 - n-1 voi nopeasti viedä paljon aikaa. Esimerkiksi, jos halusimme tarkistaa, onko 103 ensisijainen tällä menetelmällä, meidän on jaettava luvuilla 3, 4, 5, 6, 7 ... jne. Aina 102: een asti! Onneksi ei ole tarpeen testata näin. Käytännössä on tarpeen testata vain tekijät 2 ja n: n neliöjuuri. Jos n: n neliöjuuri ei ole luku, pyöristä se lähimpään kokonaislukuun ja testaa tähän numeroon. Katso selitys alla:
   • Tarkastellaan tekijöitä 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 ja 100 × 1. Huomaa, että 10 × 10 jälkeen kertoimet ovat samat jos se on 10 × 10, käännetään vasta sitten. Yleensä voimme jättää tekijät n suuremmiksi kuin sqrt (n), koska ne ovat yksinkertaisesti jatkoa tekijöille, jotka ovat vähemmän kuin sqrt (n).
   • Kokeillaan esimerkkiä. Jos n = 37, meidän ei tarvitse testata kaikkia lukuja 3 - 36 sen määrittämiseksi, onko n alkuluku. Sen sijaan meidän on vain tarkasteltava lukuja 2 - sqrt (37) (pyöristetty ylöspäin).
     • sqrt (37) = 6.08 - pyöristämme tämän seitsemään.
     • 37 ei ole täysin jaollinen luvuilla 3, 4, 5, 6 ja 7, joten voimme vakuuttaa, että se on yksi alkuluku On.
5. Säästämme vieläkin enemmän aikaa käytämme vain alkutekijöitä. On mahdollista tehdä testausprosessi jakamalla vielä lyhyemmäksi jättämättä huomioimatta tekijöitä, jotka eivät ole alkulukuja. Määritelmän mukaan jokainen yhdistetty luku voidaan ilmaista kahden tai useamman alkuluvun tulona. Joten luvun n jakaminen yhdistetyllä numerolla on tarpeetonta - tämä vastaa jakamista alkuluvuilla useita kertoja. Joten voimme edelleen kaventaa luetteloa mahdollisista tekijöistä vain alkulukuihin, jotka ovat pienempiä kuin sqrt (n).
   • Tämä tarkoittaa, että kaikki parilliset tekijät samoin kuin tekijät, jotka ovat alkulukujen kerrannaisia, voidaan ohittaa.
   • Yritetään esimerkiksi selvittää, onko 103 ensisijainen vai ei. 103: n neliöjuuri on 11 (pyöristetty ylöspäin). Pääluvut välillä 2 ja 11 ovat 3, 5, 7 ja 11. 4, 6, 8 ja 10 ovat parillisia ja 9 on 3: n kerrannaisluku, alkuluku, joten voimme ohittaa sen. Tällöin olemme vähentäneet luettelon mahdollisista tekijöistä vain 4 numeroon!
     • 103 ei ole täysin jaettavissa 3: lla, 5: llä, 7: llä tai 11: llä, joten tiedämme nyt, että 103 on yksi alkuluku On.

Menetelmä 2/4: Fermatin pienen lauseen käyttö

Vuonna 1640 ranskalainen matemaatikko Pierre de Fermat ehdotti ensin lauseetta (joka on nyt nimetty hänen mukaansa), joka voi olla erittäin hyödyllinen määritettäessä, onko luku alkuluku vai ei. Teknisesti Fermatin testillä on tarkoitus varmistaa, että luku on komposiitti eikä prime. Tämä johtuu siitä, että testi voi osoittaa "ehdottoman varmasti", että luku on yhdistetty, mutta vain "todennäköisyys", että luku on ensisijainen. Fermatin pieni lause on hyödyllinen tilanteissa, joissa jakamisen yrittäminen on epäkäytännöllistä ja kun käytettävissä on luettelo numeroista, jotka ovat lauseen poikkeuksia.

1. Olettaa n numero on testattavaa. Tämän testin avulla määrität, onko annettu luku n alkuluku. Kuten edellä todettiin, tämä lause voi toisinaan virheellisesti luonnehtia jotakin yhdistettä alkupääksi. On tärkeää ottaa tämä huomioon ja tarkistaa vastauksesi, joka selitetään alla.
2. Valitse kokonaisluku a välillä 2 ja n-1 (mukaan lukien). Valitsemasi tarkka kokonaisluku ei ole tärkeä. Koska a: n parametrit sisältävät 2 ja n-1, voit myös käyttää niitä.
   • Esimerkki: Onko 100 prime vai ei. Oletetaan, että otamme 3 testiarvona - tämä on välillä 2 ja n-1, joten se on riittävä.
3. laskea a (mod n). Tämän lausekkeen laatiminen vaatii jonkin verran tietoa matemaattisesta järjestelmästä, jota kutsutaan modulaarinen matematiikka. Modulaarisessa matematiikassa luvut palautuvat nollaan saavutettuaan tietyn arvon, joka tunnetaan myös nimellä moduuli. Voit ajatella tätä kuin kelloa: lopulta kellon käsi palaa kelloon 12 klo 12 jälkeen, ei kelloon 13. Moduuli on merkitty seuraavasti (mod n). Joten tässä vaiheessa lasket a: n, jonka moduuli on n.
   • Toinen tapa on laskea a, jakaa se sitten n: llä ja käyttää loput vastaukseksi. Erikoislaskurit, joilla on moduulitoiminto, voivat olla hyödyllisiä suurten lukujen jakamisessa, koska ne voivat välittömästi laskea loput jaosta.
   • Käyttämällä tällaista laskinta esimerkissämme voimme nähdä, että 3/100: lla on loppuosa 1. Joten 3 (mod 100) on 1.
4. Jos laskemme tämän käsin, käytämme eksponenttia lyhyenä muotona. Jos sinulla ei ole laskintoimintoa, jolla on moduulitoiminto, käytä eksponentin merkintää helpottaaksesi loput. Katso alempaa:
   • Esimerkissämme laskemme 3 moduulilla 100. 3 on hyvin, hyvin suuri luku - 51537775207320101331,036,461,129,765,621,272,702,107,522,001 - niin suuri, että sen kanssa on erittäin vaikea työskennellä. Sen sijaan, että käytämme 48-numeroista vastausta 3: een, kirjoitamme sen paremmin eksponentiksi, joten (((((((3)*3))))*3)). Muista, että eksponentin eksponentin ottaminen vaikuttaa kertoimiin ((x) = x).
     • Nyt voimme määrittää loput. Aloita ratkaisemalla (((((((((3) * 3)))) * * 3)) sulkujen sisäosassa ja jatka ulospäin jakamalla jokainen vaihe 100: lla. Kun olemme löytäneet loput, käytämme sitä seuraavassa vaiheessa todellisen vastauksen sijaan. Katso alempaa:
       • ((((((((9) * 3)))) * * 3)) - 9/100: lla ei ole jäljellä olevaa osaa, joten voimme jatkaa.
       • ((((((27)))) * 3)) - 27/100: lla ei ole loppuosaa, joten voimme siirtyä eteenpäin.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Jäännösmme on 29. Jatkamme seuraavaan vaiheeseen, ei 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Loppuosa 41 käytetään uudelleen seuraavassa vaiheessa.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Käytämme loput 81 seuraavassa vaiheessa.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Käytämme loput 43 seuraavassa vaiheessa.
       • (43 = 1849) - 1849/100 = 18 R 49. Käytämme loput 49 seuraavassa vaiheessa.
       • 49 = 2401 - 2401/100 = 24 R 1. lopullinen jäännös on 1. Toisin sanoen 3 (mod 100) = 1. Huomaa, että tämä on sama vastaus kuin laskimme edellisessä vaiheessa!
5. Selvitä a (mod n) = a (mod n). Jos ei, n on yhdiste. Jos totta, n todennäköisesti (mutta ei varma) alkuluku. Testin toistaminen eri arvoilla a: lle voi tehdä tuloksen varmemmaksi, mutta on olemassa harvinaisia ​​yhdistettyjä lukuja, jotka tyydyttävät Fermatin lauseen kaikki a-arvot. Näitä kutsutaan Carmichael-numeroiksi - pienin näistä numeroista on 561.
   • Esimerkissämme 3 (mod 100) = 1 ja 3 (mod 100) = 3.1 ≠ 3, joten voimme sanoa, että 100 on yhdistetty luku.
6. Käytä Carmichael-numeroita varmistaaksesi lopputuloksesi. Tietäen, mitkä numerot täyttävät Carmichael-sarjan ennen jatkamista, voit säästää paljon huolta siitä, onko luku ensisijainen vai ei. Yleensä Carmichael-luvut ovat yksittäisten alkulukujen tulo, jossa kaikkien alkulukujen osalta se pitää, että jos p on n: n jakaja, niin myös p-1 on n-1: n jakaja. Online-luettelo Carmichael-numeroista voi olla erittäin hyödyllinen määritettäessä, onko luku alkuluku, käyttämällä Fermatin pientä teemaa.
   
   

Menetelmä 3/4: Miller-Rabin-testin käyttö

Miller-Rabin-testi toimii samalla tavalla kuin Fermatin pieni lause, mutta se käsittelee paremmin epätyypillisiä numeroita, kuten Carmichael-numeroita.

1. Olettaa n on pariton luku, jonka haluamme testata primaarisuudelle. Kuten edellä mainituissa menetelmissä, n on muuttuja, jonka haluamme määrittää primaalin.
2. Paine n-1 muodossa 2 × d jossa d on outoa. Luku n on alkuluku, jos se on pariton. Joten n - 1: n on oltava tasainen. Koska n - 1 on parillinen, se voidaan kirjoittaa kaksinkertaisen parittoman luvun tehona. Joten 4 = 2 × 1; 80 = 2 × 5; ja niin edelleen.
   • Oletetaan, että haluamme määrittää, onko n = 321 prime. 321 - 1 = 320, jonka voimme ilmaista 2 × 5.
     • Tässä tapauksessa n = 321 on sopiva luku. N - 1: n määrittäminen n = 371: lle voi vaatia suuren arvon d: lle, mikä vaikeuttaa koko prosessia myöhemmässä vaiheessa. 371-1 = 370 = 2 × 185
3. Valitse mikä tahansa numero a välillä 2 ja n-1. Valitsemallasi tarkalla luvulla ei ole väliä - vain sen, että sen on oltava alle n ja suurempi kuin 1.
   • Esimerkissämme n = 321 valitsemme a = 100.
4. laskea a (mod n). Jos a = 1 tai -1 (mod n), sitten ohittaa n Miller-Rabin-testi ja on todennäköisesti alkuluku. Kuten Fermatin pienen lauseen kohdalla, tämä testi ei voi määrittää ehdottomasti luvun ensiheyttä, mutta vaatii lisätestejä.
   • Esimerkissämme n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (mod 321) = 313. Käytämme erityistä laskinta tai lyhennemenetelmää eksponentin kanssa, kuten aiemmin on kuvattu, jäljellä olevan arvon 100/321 löytämiseksi.
     • Koska emme ole saaneet arvoa 1 tai -1, emme voi sanoa varmuudella, että n on alkuluku. Mutta meidän on vielä tehtävä enemmän - lue lisää.
5. Koska tulos ei ole yhtä suuri kuin 1 tai -1, laske a, a, ... ja niin edelleen, jopa ad. Laske korotus d-aikojen tehoon, enintään 2. Jos jompikumpi näistä on yhtä suuri kuin 1 tai -1 (mod n), sitten ohittaa n Miller-Rabin testaa ja on todennäköisesti paras. Jos olet todennut, että n läpäisee testin, tarkista vastauksesi (katso alla oleva vaihe). Jos n ei läpäise mitään näistä testeistä, se on yksi säveltänyt määrä.
   • Muistutettakoon, että esimerkissämme a: n arvo on 100, s: n arvo on 6 ja d on 5. Jatkamme testausta alla esitetyllä tavalla:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 tai -1. Jatka rauhallisesti.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 tai -1.
     • Tässä vaiheessa voimme pysähtyä. s - 1 = 6 - 1 = 5. Olemme nyt saavuttaneet 4d = 2, eikä arvoja 2 kertaa d alle 5d ole. Koska yksikään laskelmistamme ei vastannut arvoon 1 tai -1, voimme sanoa, että n = 321 yksi säveltänyt numero on.
6. Jos n läpäisee Miller-Rabin-testin, toista muut arvot a. Jos olet huomannut, että n: n arvo voi olla ensisijainen, yritä uudelleen eri, satunnaisella arvolla a vahvistaaksesi testin tuloksen. Jos n on tosiasiallisesti alkuluku, se pätee mihin tahansa a-arvoon. Jos n on yhdistetty luku, se epäonnistuu kolmeen neljäsosaan a-arvoista. Tämä antaa sinulle enemmän varmuutta kuin Fermatin pieni lause, jossa tietyt yhdistetyt numerot (Carmichael-numerot) läpäisevät testin a-arvon mille tahansa arvolle.

Menetelmä 4/4: Kiinalaisen lauseen käyttö

1. Valitse kaksi numeroa. Yksi numeroista ei ole alkuluku ja toinen on numero, jota testataan ensiherkkyyden suhteen.
   • "Testinumero1" = 35
   • Testinumero2 = 97
2. Valitse kaksi datapistettä, jotka ovat suurempia kuin nolla ja pienemmät kuin TestNumber1 ja TestNumber2. Ne eivät voi olla samanlaisia ​​keskenään.
   • Tiedot1 = 1
   • Data2 = 2
3. Laske MMI (Mathematical Multiplicative Inverse) testinumerolle1 ja testinumerolle2
   • Laske MMI
     • MMI1 = Testinumero2 ^ -1 Mod-testinumero1
     • MMI2 = testinumero1 ^ -1 Mod-testinumero2
   • Vain prime-numeroille (ei-prime-numeroille saadaan tulos, mutta se ei ole MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Niin:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Luo binaaritaulukko kullekin MMI: lle Moduluksen Log2: een saakka
   • MMI: lle1
     • F (1) = testiluku2% testiluku1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% testiluku1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% testiluku1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% testiluku1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% testiluku1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% testiluku1 = 1 * 1% 35 = 1
   • Laske TestNumber1 - 2: n binäärilogaritmi
     • 35 -2 = 33 (10001) emäs 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • MMI2: lle
     • F (1) = Testinumero 1% Testinumero2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% testiluku2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% testiluku2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% testiluku2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% testiluku2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% testiluku2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% testiluku2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% testiluku2 = 35 * 35 mod 97 = 61
   • Laske TestNumber2 - 2: n binäärilogaritmi
     • 97 - 2 = 95 = (1011111) emäs 2
     • MMI2 = ((((((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
5. Laske (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Vastaus = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Vastaus = (2619 + 4270)% 3395
   • Vastaus = 99
6. Tarkista, että "TestNumber1" ei ole prime1
   • Laske (vastaus - data1)% testiluku1
   • 99 -1 % 35 = 28
   • Koska 28 on suurempi kuin 0, 35 ei ole prime
7. Tarkista, onko TestNumber2 ensisijainen
   • Laske (vastaus - data2)% testiluku2
   • 99 - 2 % 97 = 0
   • Koska 0 on 0, 97 on potentiaalinen alkuluku
8. Toista vaiheet 1–7 vielä vähintään kaksi kertaa.
   • Jos vaihe 7 on 0:
     • Käytä toista "TestNumber1", jos TestNumber1 ei ole ensisijainen.
     • Käytä toista TestNumber1, jossa TestNumber1 on tosiasiallisesti ensisijainen. Tässä tapauksessa vaiheet 6 ja 7 ovat yhtä suuret kuin 0.
     • Käytä eri datapisteitä data1: lle ja data2: lle.
   • Jos vaihe 7 on aina yhtä suuri kuin 0, niin todennäköisyys, että luku 2 on alkuluku, on erittäin suuri.
   • Vaiheiden 1 - 7 tiedetään olevan virheellisiä tietyissä tapauksissa, kun ensimmäinen luku ei ole alkuluku ja toinen on ei-alkuluvun "Testinumero1" alkutekijä. Se toimii kaikissa tilanteissa, joissa molemmat luvut ovat ensisijaisia.
   • Syy vaiheiden 1 - 7 toistamiseen johtuu siitä, että on olemassa muutamia tilanteita, joissa, vaikka TestNumber1 ei ole alkuluku ja TestNumber2 ei ole alkuluku, kumpikin vaiheen 7 numero on edelleen nolla. Nämä olosuhteet ovat harvinaisia. Vaihtamalla TestNumber1 toiseksi ei-alkuluvuksi, jos TestNumber2 ei ole alkuluku, TestNumber2 ei enää ole sama kuin nolla, vaiheessa 7. Lukuun ottamatta tapausta, jossa "TestNumber1" on TestNumber2-tekijä, alkuluvut ovat aina nollia. vaihe 7.

Vinkkejä

• Alle 1000: n 168 päälukua ovat: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
• Kun yrittää jakaa on hitaampaa kuin kehittyneemmät menetelmät, se on silti tehokas pienemmille numeroille. Jopa testattaessa suurempia lukuja ei ole harvinaista tarkistaa pienet numerot ensin ennen siirtymistä edistyneemmille menetelmille.

Tarpeet

• Paperi, kynä, lyijykynä ja / tai laskin harjoittelua varten