Sisältö

• Askeleet
• Osa 1/3: Yksinkertaisuuden testit
• Osa 2/3: Kuinka yksinkertaistustestit toimivat
• Osa 3/3: Kiinan jäännöksen lauseen käyttäminen
• Vinkkejä
• Mitä tarvitset

Alkuluvut ovat numeroita, jotka jakautuvat vain itsellään ja yhdellä. Kaikkia muita numeroita kutsutaan yhdistelmäluvuiksi. On monia tapoja määrittää, onko numero ensisijainen, ja kaikilla on omat etunsa ja haittansa. Toisaalta jotkut menetelmät ovat erittäin tarkkoja, mutta ne ovat melko monimutkaisia, jos käsittelet suuria lukuja. Toisaalta on olemassa paljon nopeampia tapoja, mutta ne voivat johtaa vääriin tuloksiin. Sopivan menetelmän valinta riippuu siitä, kuinka suuria numeroita käytät.

Askeleet

Osa 1/3: Yksinkertaisuuden testit

merkintä: kaikissa kaavoissa n tarkoittaa tarkistettavaa numeroa.

1. 1 Jakajien luettelo. Jakautuminen riittää n kaikille alkuluvuille 2 pyöristettyyn arvoon (${ displaystyle { sqrt {n}}}$).
2. 2 Fermatin pieni lause. Varoitus: joskus testi tunnistaa väärin yhdistelmäluvut alkuluvuiksi, vaikka kaikki a: n arvot olisivat.
   • Valitaan kokonaisluku aniin, että 2 ≤ a ≤ n - 1.
   • Jos a (mod n) = a (mod n), luku on todennäköisesti alkuluku. Jos tasa -arvo ei täyty, luku n on yhdistelmä.
   • Tarkista annettu arvo yhtä monta alisätä todennäköisyyttä, että testattava luku on todellakin ensisijainen.
3. 3 Miller-Rabin-testi. Varoitus: joskus, vaikkakin harvoin, useiden a -arvojen kohdalla testi tunnistaa yhdistelmäluvut virheellisesti alkuluvuiksi.
   • Etsi määrät s ja d siten, että ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Valitse kokonaisluku a alueella 2 ≤ a ≤ n - 1.
   • Jos a = +1 (mod n) tai -1 (mod n), niin n on todennäköisesti prime. Siirry tässä tapauksessa testitulokseen. Jos tasa -arvo ei pidä paikkaansa, siirry seuraavaan vaiheeseen.
   • Neliötä vastauksesi (${ displaystyle a ^ {2d}}$). Jos saat -1 (mod n), n on todennäköisesti alkuluku. Siirry tässä tapauksessa testitulokseen. Jos tasa -arvo epäonnistuu, toista (${ displaystyle a ^ {4d}}$ ja niin edelleen) asti ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Jos jossakin vaiheessa muun numeron neliöimisen jälkeen kuin ${ displaystyle pm 1}$ (mod n), sait +1 (mod n), joten n on yhdistetty luku. Jos ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), niin n ei ole prime.
   • Testitulos: jos n läpäisee testin, toista se muille arvoille aluottamuksen lisäämiseksi.

Osa 2/3: Kuinka yksinkertaistustestit toimivat

1. 1 Jakajien luettelo. Määritelmän mukaan numero n on yksinkertainen vain, jos se ei jaa 2: lla ja muilla kokonaisluvuilla paitsi 1 ja itse. Yllä olevan kaavan avulla voit poistaa tarpeettomat vaiheet ja säästää aikaa: jos olet esimerkiksi tarkistanut, onko numero jaollinen kolmella, sinun ei tarvitse tarkistaa, onko se jaollinen yhdeksällä.
   • Kerros (x) -funktio pyöristää x: n lähimpään kokonaislukuun, joka on pienempi tai yhtä suuri kuin x.
2. 2 Opi modulaarisesta laskennasta. Operaatio "x mod y" (mod on lyhenne latinalaisesta sanasta "modulo" eli "moduuli") tarkoittaa "jaa x y: llä ja löydä loput". Toisin sanoen modulaarisessa laskennassa, kun saavutetaan tietty arvo, jota kutsutaan moduuli, numerot "kääntyvät" jälleen nollaan. Esimerkiksi kello laskee alas moduulin 12 kanssa: se näyttää 10, 11 ja 12 tuntia ja palaa sitten 1: een.
   • Monilla laskimilla on mod -näppäin. Tämän osan lopussa näytetään, kuinka tämä toiminto lasketaan manuaalisesti suurille numeroille.
3. 3 Opi Fermatin pienen lauseen sudenkuopista. Kaikki numerot, joiden testausehdot eivät täyty, ovat yhdistettyjä, mutta loput numerot ovat vain todennäköisesti ovat yksinkertaisia. Jos haluat välttää vääriä tuloksia, etsi n luettelossa "Carmichael -numerot" (yhdistelmäluvut, jotka täyttävät tämän testin) ja "Fermat -pseudoprime -numerot" (nämä luvut täyttävät testiolosuhteet vain joillekin arvoille a).
4. 4 Jos mahdollista, käytä Miller-Rabin-testiä. Vaikka tämä menetelmä on melko hankala manuaalisiin laskelmiin, sitä käytetään usein tietokoneohjelmissa. Se tarjoaa hyväksyttävän nopeuden ja vähemmän virheitä kuin Fermatin menetelmä. Yhdistettyä lukua ei oteta alkuluvuksi, jos laskelmat suoritetaan yli ¼ -arvoille a... Jos valitset satunnaisesti eri arvot a ja kaikille niistä testi antaa positiivisen tuloksen, voimme olettaa melko suurella luottamuksella, että n on alkuluku.
5. 5 Käytä suuria modulaarisia laskutoimituksia suurille numeroille. Jos sinulla ei ole mod -laskinta käsilläsi tai laskin ei ole suunniteltu käsittelemään niin suuria lukuja, käytä tehon ominaisuuksia ja modulaarista laskutoimitusta laskelmien helpottamiseksi. Alla on esimerkki ${ displaystyle 3 ^ {50}}$ mod 50:
   • Kirjoita lauseke uudelleen kätevämmässä muodossa: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Manuaaliset laskelmat voivat vaatia lisä yksinkertaistuksia.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}})$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Tässä otimme huomioon modulaarisen kertomisen ominaisuuden.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}})$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Osa 3/3: Kiinan jäännöksen lauseen käyttäminen

1. 1 Valitse kaksi numeroa. Toisen numeron on oltava yhdistetty ja toisen on oltava juuri se, jonka yksinkertaisuuden haluat testata.
   • Luku1 = 35
   • Luku2 = 97
2. 2 Valitse kaksi arvoa, jotka ovat suurempia kuin nolla ja vastaavasti pienempiä kuin numerot Number1 ja Number2. Nämä arvot eivät saa olla samat.
   • Arvo1 = 1
   • Arvo2 = 2
3. 3 Laske MMI (Mathematical Multiplicative Inverse) numeroille 1 ja numero2.
   • Laske MMI
     • MMI1 = numero2 ^ -1 modin numero1
     • MMI2 = Luku1 ^ -1 Modin numero2
   • Vain alkuluvuille (tämä antaa numeron yhdistelmäluvuille, mutta se ei ole hänen MMI):
     • MMI1 = (Luku2 ^ (Luku1-2))% Luku1
     • MMI2 = (Luku1 ^ (Luku2-2))% Luku2
   • Esimerkiksi:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Luo taulukko kullekin MMI: lle log2 -moduuleihin asti:
   • MMI1: lle
     • F (1) = luku2% luku1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Luku1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Luku1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Luku1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Luku1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Luku1 = 1 * 1% 35 = 1
   • Parillisten numeroiden laskeminen 1-2
     • 35 -2 = 33 (10001) kanta 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2: lle
     • F (1) = luku1% luku2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Luku2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Luku2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Luku2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Luku2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Luku2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Luku2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Luku2 = 35 * 35 mod 97 = 61
   • Laske pariluku 2 - 2
     • 97-2 = 95 = (1011111) kanta 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. 5 Laske (Arvo1 * Luku2 * MMI1 + Arvo2 * Luku1 * MMI2)% (Luku1 * Luku2)
   • Vastaus = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Vastaus = (2619 + 4270)% 3395
   • Vastaus = 99
6. 6 Tarkista, että numero 1 ei ole prime
   • Laske (Vastaus - Arvo1)% Luku1
   • 99 – 1 % 35 = 28
   • Koska 28 on suurempi kuin 0, 35 ei ole alkuluku.
7. 7 Tarkista, että numero 2 on ensisijainen.
   • Laske (Vastaus - Arvo2)% Luku2
   • 99 – 2 % 97 = 0
   • Koska 0 on 0, 97 on todennäköisesti alkuluku.
8. 8 Toista vaiheet 1-7 vähintään kaksi kertaa.
   • Jos saat 0 vaiheessa 7:
     • Käytä toista numeroa1, jos numero1 ei ole alkuluku.
     • Käytä toista numeroa1, jos numero1 on alkuluku. Tässä tapauksessa sinun pitäisi saada 0 vaiheissa 6 ja 7.
     • Käytä eri merkityksiä 1 ja 2.
   • Jos vaiheessa 7 saat jatkuvasti 0, niin numero 2 on erittäin todennäköisesti prime.
   • Vaiheet 1-7 voivat aiheuttaa virheen, jos numero1 ei ole alkuluku ja numero2 on luvun1 jakaja. Kuvattu menetelmä toimii kaikissa tapauksissa, kun molemmat luvut ovat alkutekijöitä.
   • Syy, miksi sinun on toistettava vaiheet 1–7, on se, että joissakin tapauksissa, vaikka numero 1 ja numero 2 eivät olisikaan alkutekijöitä, vaiheessa 7 saat 0 (yhdelle tai molemmille numeroille). Tätä tapahtuu harvoin.Valitse toinen numero1 (yhdistelmä), ja jos luku2 ei ole alkuluku, numero 2 ei ole nolla vaiheessa 7 (paitsi siinä tapauksessa, että numero1 on luvun 2 jakaja - tässä alkuluku on aina nolla vaiheessa 7).

Vinkkejä

• Esiluvut 168 - 1000: 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.
• Vaikka raa'an voiman testaus on työläs testi, kun työskennellään suurilla numeroilla, se on melko tehokas pienille numeroille. Jopa suurten lukujen tapauksessa aloita pienien jakajien testaamisesta ja siirry sitten kehittyneempiin menetelmiin lukujen yksinkertaisuuden tarkistamiseksi (jos pieniä jakajia ei löydy).

Mitä tarvitset

• Paperi, kynä tai tietokone