Sadržaj

• Koraci
• 1. dio od 3: Testovi jednostavnosti
• 2. dio od 3: Kako rade testovi jednostavnosti
• 3. dio 3: Korištenje kineske teoreme ostataka
• Savjeti
• Što trebaš

Prosti brojevi su brojevi koji su djeljivi samo sami sa sobom i sa 1. Svi ostali brojevi nazivaju se složeni brojevi. Postoji mnogo načina da se utvrdi je li broj prost, a svi oni imaju svoje prednosti i nedostatke. S jedne strane, neke od metoda su vrlo točne, ali su prilično složene ako se bavite velikim brojevima. S druge strane, postoje mnogo brži načini, ali oni mogu dovesti do netočnih rezultata. Odabir odgovarajuće metode ovisi o tome s kojim velikim brojevima radite.

Koraci

1. dio od 3: Testovi jednostavnosti

Bilješka: u svim formulama n označava broj koji treba provjeriti.

1. 1 Nabrajanje djelitelja. Dovoljno je podijeliti n na sve proste brojeve od 2 do zaokružene vrijednosti (${ displaystyle { sqrt {n}}}$).
2. 2 Fermatov mali teorem. Upozorenje: ponekad će test lažno identificirati složene brojeve kao proste, čak i za sve vrijednosti a.
   • Odaberimo cijeli broj atako da 2 ≤ a ≤ n - 1.
   • Ako je a (mod n) = a (mod n) tada je broj vjerojatno prost. Ako jednakost nije zadovoljena, broj n je složen.
   • Provjerite datu jednakost za više vrijednosti akako bi se povećala vjerojatnost da je broj koji se testira doista prosti.
3. 3 Miller-Rabinov test. Upozorenje: ponekad, iako rijetko, za više vrijednosti a, test će lažno identificirati složene brojeve kao proste.
   • Nađi količine s i d takve da ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Odaberite cijeli broj a u rasponu 2 ≤ a ≤ n - 1.
   • Ako je a = +1 (mod n) ili -1 (mod n), tada je n vjerojatno prost. U tom slučaju idite na rezultat testa. Ako jednakost ne vrijedi, prijeđite na sljedeći korak.
   • Uokvirite svoj odgovor (${ displaystyle a ^ {2d}}$). Ako dobijete -1 (mod n), tada je n vjerojatno prost broj. U tom slučaju idite na rezultat testa. Ako jednakost ne uspije, ponovite (${ displaystyle a ^ {4d}}$ i tako dalje) do ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Ako u nekom koraku nakon kvadrata broj osim ${ displaystyle pm 1}$ (mod n), dobili ste +1 (mod n), pa je n kompozitni broj. Ako ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), tada n nije prost.
   • Rezultat testa: ako n prođe test, ponovite ga za ostale vrijednosti aza povećanje samopouzdanja.

2. dio od 3: Kako rade testovi jednostavnosti

1. 1 Nabrajanje djelitelja. Po definiciji, broj n je jednostavan samo ako nije djeljiv sa 2 i drugim cijelim brojevima osim 1 i samim sobom. Gornja formula omogućuje vam uklanjanje nepotrebnih koraka i uštedu vremena: na primjer, nakon provjere je li broj djeljiv s 3, nema potrebe provjeravati je li djeljiv s 9.
   • Funkcija floor (x) zaokružuje x na najbliži cijeli broj manji ili jednak x.
2. 2 Saznajte više o modularnoj aritmetici. Operacija "x mod y" (mod je kratica od latinske riječi "modulo", to jest "modul") znači "podijeli x po y i pronađi ostatak". Drugim riječima, u modularnoj aritmetici, po postizanju određene vrijednosti, koja se naziva modul, brojevi se opet "okreću" na nulu. Na primjer, sat odbrojava s modulom 12: prikazuje 10, 11 i 12 sati, a zatim se vraća na 1.
   • Mnogi kalkulatori imaju ključ za mod. Kraj ovog odjeljka prikazuje kako ručno izračunati ovu funkciju za velike brojeve.
3. 3 Saznajte o zamkama Fermatove male teoreme. Svi brojevi za koje nisu ispunjeni uvjeti ispitivanja su složeni, ali ostali su brojevi samo vjerojatno su jednostavne. Ako želite izbjeći netočne rezultate, tražite n na popisu "Carmichael brojeva" (složeni brojevi koji zadovoljavaju ovaj test) i "Fermatovih pseudoprimenih brojeva" (ti brojevi zadovoljavaju uvjete ispitivanja samo za neke vrijednosti a).
4. 4 Ako je prikladno, upotrijebite Miller-Rabinov test. Iako je ova metoda prilično nezgrapna za ručne izračune, često se koristi u računalnim programima. Omogućuje prihvatljivu brzinu i manje pogrešaka od Fermatove metode. Složeni broj neće se uzeti kao prost broj ako se proračuni izvode za više od ¼ vrijednosti a... Ako nasumično odaberete različite vrijednosti a i za sve njih test će dati pozitivan rezultat, možemo s prilično visokim stupnjem povjerenja pretpostaviti da n je prost broj.
5. 5 Za velike brojeve koristite modularnu aritmetiku. Ako nemate pri ruci kalkulator modova ili kalkulator nije dizajniran za rukovanje tako velikim brojevima, upotrijebite svojstva snage i modularnu aritmetiku kako biste olakšali izračune. Ispod je primjer za ${ displaystyle 3 ^ {50}}$ mod 50:
   • Prepišite izraz u prikladniji oblik: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Ručni izračuni mogu zahtijevati daljnja pojednostavljenja.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Ovdje smo uzeli u obzir svojstvo modularnog 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. dio 3: Korištenje kineske teoreme ostataka

1. 1 Odaberite dva broja. Jedan od brojeva mora biti sastavljen, a drugi mora biti upravo onaj koji želite testirati radi jednostavnosti.
   • Broj1 = 35
   • Broj2 = 97
2. 2 Odaberite dvije vrijednosti veće od nule, odnosno manje od brojeva Number1 i Number2. Ove vrijednosti ne smiju biti iste.
   • Vrijednost1 = 1
   • Vrijednost 2 = 2
3. 3 Izračunajte MMI (matematički multiplikativni inverz) za broj 1 i broj 2.
   • Izračunajte MMI
     • MMI1 = Broj2 ^ -1 Mod Broj1
     • MMI2 = Broj1 ^ -1 Mod Broj2
   • Samo za proste brojeve (ovo će dati broj za složene brojeve, ali to neće biti njegov MMI):
     • MMI1 = (Broj2 ^ (Broj1-2))% Broj1
     • MMI2 = (Broj1 ^ (Broj2-2))% Broj2
   • Na primjer:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Izradite tablicu za svaki MMI do log2 modula:
   • Za MMI1
     • F (1) = Broj2% Broj1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Broj1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Broj1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Broj1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Broj1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Broj1 = 1 * 1% 35 = 1
   • Izračunajte uparene brojeve 1 - 2
     • 35 -2 = 33 (10001) baza 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Za MMI2
     • F (1) = Broj1% Broj2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Broj2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Broj2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Broj2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Broj2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Broj2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Broj2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Broj2 = 35 * 35 mod 97 = 61
   • Izračunajte upareni broj 2 - 2
     • 97 - 2 = 95 = (1011111) baza 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 (vrijednost1 * broj2 * MMI1 + vrijednost2 * broj1 * MMI2)% (broj1 * broj2)
   • Odgovor = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Odgovor = (2619 + 4270)% 3395
   • Odgovor = 99
6. 6 Provjerite da broj 1 nije prost
   • Izračunajte (odgovor - vrijednost1)% broj1
   • 99 – 1 % 35 = 28
   • Budući da je 28 veće od 0, 35 nije prost broj.
7. 7 Provjerite je li broj 2 prost.
   • Izračunajte (odgovor - vrijednost2)% broj2
   • 99 – 2 % 97 = 0
   • Budući da je 0 0, 97 je najvjerojatnije prost broj.
8. 8 Ponovite korake od 1 do 7 još najmanje dva puta.
   • Ako u koraku 7 dobijete 0:
     • Koristite drugi broj 1 ako broj 1 nije prost.
     • Upotrijebite drugi broj1 ako je broj 1 prost. U tom slučaju trebali biste dobiti 0 u koracima 6 i 7.
     • Koristite različita značenja1 i značenja2.
   • Ako u koraku 7 dosljedno dobivate 0, tada će broj 2 vrlo vjerojatno biti prost.
   • Koraci od 1 do 7 mogu dovesti do pogreške ako Number1 nije prost, a Number2 je djelitelj Number1. Opisana metoda funkcionira u svim slučajevima kada su oba broja prosta.
   • Razlog zašto morate ponoviti korake od 1 do 7 je taj što u nekim slučajevima, čak i ako Broj 1 i Broj 2 nisu prosti, u koraku 7 dobit ćete 0 (za jedan ili oba broja). To se rijetko događa.Odaberite drugi Broj1 (složeni), a ako Broj 2 nije prost, tada Broj 2 neće biti jednak nuli u koraku 7 (osim u slučaju kada je Broj 1 djelitelj broja 2 - ovdje će prostori u koraku 7 uvijek biti jednaki nuli).

Savjeti

• Prosti brojevi 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.
• Iako je ispitivanje grube sile dosadan test pri radu s velikim brojevima, vrlo je učinkovito za male brojeve. Čak i u slučaju velikih brojeva, počnite s testiranjem malih djelitelja, a zatim prijeđite na sofisticiranije metode provjere jednostavnosti brojeva (ako mali djelitelji nisu pronađeni).

Što trebaš

• Papir, olovka ili računalo