Vsebina

• Koraki
• 1. del 3: Preizkusi preprostosti
• 2. del 3: Kako delujejo preizkusi preprostosti
• 3. del 3: Uporaba kitajskega izreka o ostankih
• Nasveti
• Kaj potrebujete

Prosta števila so števila, ki so deljiva samo s seboj in s 1. Vsa druga števila se imenujejo sestavljena števila. Obstaja veliko načinov, kako ugotoviti, ali je število prosto, in vsi imajo svoje prednosti in slabosti. Po eni strani so nekatere metode zelo natančne, vendar so precej zapletene, če se ukvarjate z velikim številom. Po drugi strani pa obstajajo veliko hitrejši načini, ki pa lahko vodijo do napačnih rezultatov. Izbira ustrezne metode je odvisna od tega, kako velike številke delate.

Koraki

1. del 3: Preizkusi preprostosti

Opomba: v vseh formulah n označuje številko, ki jo je treba preveriti.

1. 1 Naštevanje deliteljev. Dovolj je razdeliti n za vsa prosta števila od 2 do zaokrožene vrednosti (${ displaystyle { sqrt {n}}}$).
2. 2 Fermatov mali izrek. Opozorilo: včasih bo test lažno določil sestavljena števila kot prosta, tudi za vse vrednosti a.
   • Izberemo celo število atako, da je 2 ≤ a ≤ n - 1.
   • Če je a (mod n) = a (mod n), je število verjetno prvo. Če enakost ni izpolnjena, je število n sestavljeno.
   • Preverite dano enakost za več vrednosti apovečati verjetnost, da je število, ki se testira, resnično prvovrstno.
3. 3 Miller-Rabinov test. Opozorilo: včasih, čeprav redko, za več vrednosti a, bo test lažno določil sestavljena števila kot prosta.
   • Poiščite količine s in d tako, da ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Izberite celo število a v območju 2 ≤ a ≤ n - 1.
   • Če je a = +1 (mod n) ali -1 (mod n), je n verjetno prost. V tem primeru pojdite na rezultat testa. Če enakost ne drži, pojdite na naslednji korak.
   • Oglasi svoj odgovor na kvadrat (${ displaystyle a ^ {2d}}$). Če dobite -1 (mod n), je n verjetno praštevilo. V tem primeru pojdite na rezultat testa. Če enakost ne uspe, ponovite (${ displaystyle a ^ {4d}}$ in tako naprej) do ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Če na nekem koraku po kvadraturi števila, ki ni ${ displaystyle pm 1}$ (mod n), dobili ste +1 (mod n), zato je n sestavljeno število. Če ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), potem n ni prost.
   • Rezultat testa: če n prestane preskus, ga ponovite za druge vrednosti aza povečanje zaupanja.

2. del 3: Kako delujejo preizkusi preprostosti

1. 1 Naštevanje deliteljev. Po definiciji število n je preprosto le, če ni deljivo z 2 in drugimi celimi števili, razen z 1 in samim sabo. Zgornja formula vam omogoča, da odstranite nepotrebne korake in prihranite čas: na primer po preverjanju, ali je število deljivo s 3, ni treba preverjati, ali je deljivo z 9.
   • Funkcija floor (x) zaokroži x na najbližje celo število, manjše ali enako x.
2. 2 Spoznajte modularno aritmetiko. Operacija »x mod y« (mod je okrajšava latinske besede »modulo«, torej »modul«) pomeni »delite x z y in poiščite preostanek«. Z drugimi besedami, v modularni aritmetiki, ko dosežemo določeno vrednost, ki se imenuje modul, se številke spet "obrnejo" na nič. Na primer, ura odšteva z modulom 12: prikazuje 10, 11 in 12 ur, nato pa se vrne na 1.
   • Mnogi kalkulatorji imajo ključ za mod. Na koncu tega razdelka je prikazano, kako ročno izračunati to funkcijo za velika števila.
3. 3 Spoznajte pasti Fermatovega malega izreka. Vse številke, za katere niso izpolnjeni preskusni pogoji, so sestavljene, preostale številke pa so samo verjetno so preproste. Če se želite izogniti napačnim rezultatom, poiščite n na seznamu "Carmichaelove številke" (sestavljene številke, ki ustrezajo temu preskusu) in "Fermatove številke psevdoprime" (te številke izpolnjujejo pogoje preskusa le za nekatere vrednosti a).
4. 4 Če je primerno, uporabite Miller-Rabinov test. Čeprav je ta metoda za ročne izračune precej okorna, se pogosto uporablja v računalniških programih. Zagotavlja sprejemljivo hitrost in manj napak kot Fermatova metoda. Sestavljeno število ne bo vzeto kot prvo število, če se izračuni izvedejo za več kot. Vrednosti a... Če naključno izberete različne vrednosti a in za vse bo test dal pozitiven rezultat, lahko z dokaj visoko stopnjo zaupanja domnevamo, da n je prvo število.
5. 5 Za velika števila uporabite modularno aritmetiko. Če kalkulatorja mode nimate pri roki ali pa kalkulator ni zasnovan za tako velika števila, uporabite lastnosti moči in modularno aritmetiko, da olajšate izračune. Spodaj je primer za ${ displaystyle 3 ^ {50}}$ mod 50:
   • Prepišite izraz v bolj priročno obliko: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Ročni izračuni lahko zahtevajo dodatne poenostavitve.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Tu smo upoštevali lastnost modularnega množenja.
   • ${ 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}$.

3. del 3: Uporaba kitajskega izreka o ostankih

1. 1 Izberite dve številki. Eno od števil mora biti sestavljeno, drugo pa točno tisto, ki ga želite poenostaviti.
   • Število1 = 35
   • Število 2 = 97
2. 2 Izberite dve vrednosti, ki sta večji od nič in manjši od številk Number1 in Number2. Te vrednosti ne smejo biti enake.
   • Vrednost 1 = 1
   • Vrednost 2 = 2
3. 3 Izračunajte MMI (matematično multiplikativno obratno) za številko 1 in številko 2.
   • Izračunajte MMI
     • MMI1 = Število2 ^ -1 Mod Številka1
     • MMI2 = Število1 ^ -1 Mod Številka2
   • Samo za prosta števila (to bo dalo število za sestavljena števila, vendar to ne bo njegov MMI):
     • MMI1 = (Število2 ^ (Število1-2))% Število1
     • MMI2 = (Število1 ^ (Število2-2))% Število2
   • Na primer:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Ustvarite tabelo za vsak MMI vse do modulov log2:
   • Za MMI1
     • F (1) = Število2% Število1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Število1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Število1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Število1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Število1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Število1 = 1 * 1% 35 = 1
   • Izračunajte seznanjena števila 1 - 2
     • 35 -2 = 33 (10001) osnova 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Za MMI2
     • F (1) = Število1% Število2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Število2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Število2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Število2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Število 2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Število 2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Število 2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Število 2 = 35 * 35 mod 97 = 61
   • Izračunajte seznanjeno številko 2 - 2
     • 97 - 2 = 95 = (1011111) osnova 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 Izračunaj (vrednost1 * številka2 * MMI1 + vrednost2 * številka1 * MMI2)% (številka1 * številka2)
   • Odgovor = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Odgovor = (2619 + 4270)% 3395
   • Odgovor = 99
6. 6 Preverite, da številka 1 ni osnovna
   • Izračunajte (odgovor - vrednost1)% število1
   • 99 – 1 % 35 = 28
   • Ker je 28 večje od 0, 35 ni praštevilo.
7. 7 Preverite, ali je številka 2 osnovna.
   • Izračunajte (odgovor - vrednost2)% število2
   • 99 – 2 % 97 = 0
   • Ker je 0 0, je 97 najverjetneje praštevilo.
8. 8 Ponovite korake od 1 do 7 vsaj še dvakrat.
   • Če v koraku 7 dobite 0:
     • Uporabite drugo število1, če številka1 ni osnovna.
     • Uporabite drugo število 1, če je število 1 prosto. V tem primeru morate v korakih 6 in 7 dobiti 0.
     • Uporabite drugačen pomen1 in pomen2.
   • Če v koraku 7 dosledno dobite 0, potem je številka 2 zelo verjetno glavna.
   • Koraki od 1 do 7 lahko povzročijo napako, če Number1 ni prost in je Number2 delitelj Number1. Opisana metoda deluje v vseh primerih, ko sta obe številki prosti.
   • Razlog, da morate ponoviti korake od 1 do 7, je v tem, da v nekaterih primerih, tudi če številka 1 in številka 2 nista primarni, v koraku 7 dobite 0 (za eno ali obe številki). To se redko zgodi.Izberite drugo število 1 (sestavljeno) in če številka 2 ni osnovna, potem številka 2 v koraku 7 ne bo enaka nič (razen v primeru, ko je število 1 delitelj števila 2 - tukaj bodo številke v koraku 7 vedno enake nič).

Nasveti

• Osnovne številke od 168 do 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.
• Čeprav je testiranje surove sile mučen pri delu z velikimi številkami, je pri majhnih številkah zelo učinkovito. Tudi v primeru velikih številk začnite s preskušanjem majhnih deliteljev in nato preidite na bolj izpopolnjene metode za preverjanje preprostosti števil (če majhnih deliteljev ne najdete).

Kaj potrebujete

• Papir, pisalo ali računalnik