Conţinut

• Pași
• Partea 1 din 3: Teste de simplitate
• Partea 2 din 3: Cum funcționează testele de simplitate
• Partea 3 din 3: Folosirea teoremei restului chinezesc
• sfaturi
• De ce ai nevoie

Numerele prime sunt numere care sunt divizibile numai prin ele însele și cu 1. Toate celelalte numere se numesc numere compuse. Există multe modalități de a determina dacă un număr este prim și toate au propriile avantaje și dezavantaje. Pe de o parte, unele dintre metode sunt foarte exacte, dar sunt destul de complexe dacă aveți de-a face cu un număr mare. Pe de altă parte, există modalități mult mai rapide, dar pot duce la rezultate incorecte. Alegerea metodei adecvate depinde de cât de mari sunt numerele cu care lucrați.

Pași

Partea 1 din 3: Teste de simplitate

Notă: în toate formulele n denotă numărul care trebuie verificat.

1. 1 Enumerarea divizorilor. Este suficient să împărțiți n la toate numerele prime de la 2 la valoarea rotunjită (${ displaystyle { sqrt {n}}}$).
2. 2 Teorema mică a lui Fermat. Atenție: uneori testul va identifica în mod fals numerele compuse drept prime, chiar și pentru toate valorile unui.
   • Să alegem un număr întreg Aastfel încât 2 ≤ a ≤ n - 1.
   • Dacă a (mod n) = a (mod n), atunci numărul este probabil prim. Dacă egalitatea nu este satisfăcută, numărul n este compus.
   • Verificați egalitatea dată pentru mai multe valori Apentru a crește probabilitatea ca numărul testat să fie într-adevăr prim.
3. 3 Testul Miller-Rabin. Atenție: uneori, deși rar, pentru mai multe valori ale lui a, testul va identifica în mod fals numerele compuse drept prime.
   • Găsiți cantitățile s și d astfel încât ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Selectați un număr întreg A în intervalul 2 ≤ a ≤ n - 1.
   • Dacă a = +1 (mod n) sau -1 (mod n), atunci n este probabil prim. În acest caz, accesați rezultatul testului. Dacă egalitatea nu se menține, treceți la pasul următor.
   • Păstrați-vă răspunsul (${ displaystyle a ^ {2d}}$). Dacă obțineți -1 (mod n), atunci n este probabil un număr prim. În acest caz, accesați rezultatul testului. Dacă egalitatea eșuează, repetați (${ displaystyle a ^ {4d}}$ și așa mai departe) până când ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Dacă la un anumit pas după pătrarea unui alt număr decât ${ displaystyle pm 1}$ (mod n), ai primit +1 (mod n), deci n este un număr compus. Dacă ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), atunci n nu este prim.
   • Rezultatul testului: dacă n trece testul, repetați-l pentru alte valori Apentru a spori încrederea.

Partea 2 din 3: Cum funcționează testele de simplitate

1. 1 Enumerarea divizorilor. Prin definiție, numărul n este simplu numai dacă nu este divizibil cu 2 și cu alți numere întregi cu excepția lui 1 și în sine. Formula de mai sus vă permite să eliminați pașii inutili și să economisiți timp: de exemplu, după verificarea dacă un număr este divizibil cu 3, nu este necesar să verificați dacă acesta este divizibil cu 9.
   • Funcția etaj (x) rotunjește x la cel mai apropiat întreg mai mic sau egal cu x.
2. 2 Aflați despre aritmetica modulară. Operațiunea „x mod y” (mod este o abreviere a cuvântului latin „modulo”, adică „modul”) înseamnă „împarte x la y și găsește restul”. Cu alte cuvinte, în aritmetică modulară, la atingerea unei anumite valori, care se numește modul, numerele „se întorc” la zero din nou. De exemplu, ceasul numără înapoi cu modulul 12: arată 10, 11 și 12 ore, apoi revine la 1.
   • Multe calculatoare au o tastă mod. Sfârșitul acestei secțiuni vă arată cum să calculați manual această funcție pentru un număr mare.
3. 3 Aflați despre capcanele Micii teoreme ale lui Fermat. Toate numerele pentru care nu sunt îndeplinite condițiile de testare sunt compuse, dar restul numerelor sunt numai probabil sunt simple. Dacă doriți să evitați rezultatele incorecte, căutați n în lista „numerelor Carmichael” (numere compozite care satisfac acest test) și „numerelor pseudoprime Fermat” (aceste numere îndeplinesc condițiile de testare doar pentru unele valori A).
4. 4 Dacă este convenabil, utilizați testul Miller-Rabin. Deși această metodă este destul de greoaie pentru calculele manuale, este adesea utilizată în programele de calculator. Oferă viteză acceptabilă și mai puține erori decât metoda Fermat. Un număr compus nu va fi luat ca număr prim dacă se efectuează calcule pentru mai mult de ¼ valori A... Dacă alegeți aleatoriu diferite valori A iar pentru toți testul va da un rezultat pozitiv, putem presupune cu un grad destul de ridicat de încredere că n este un număr prim.
5. 5 Pentru un număr mare, utilizați aritmetica modulară. Dacă nu aveți un calculator mod la îndemână sau calculatorul nu este conceput pentru a gestiona astfel de numere mari, utilizați proprietăți de putere și aritmetică modulară pentru a face calculele mai ușoare. Mai jos este un exemplu pentru ${ displaystyle 3 ^ {50}}$ mod 50:
   • Rescrieți expresia într-o formă mai convenabilă: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Calculele manuale pot necesita simplificări suplimentare.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Aici am luat în considerare proprietatea multiplicării modulare.
   • ${ 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}$.

Partea 3 din 3: Folosirea teoremei restului chinezesc

1. 1 Alegeți două numere. Unul dintre numere trebuie să fie compus, iar celălalt trebuie să fie exact cel pe care doriți să îl testați pentru simplitate.
   • Numărul 1 = 35
   • Număr2 = 97
2. 2 Selectați două valori mai mari decât zero și, respectiv, mai mici decât numerele Number1 și Number2. Aceste valori nu trebuie să fie aceleași.
   • Valoare1 = 1
   • Valoare2 = 2
3. 3 Calculați MMI (inversă multiplicativă matematică) pentru numărul 1 și numărul 2.
   • Calculați MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Numai pentru numerele prime (aceasta va da un număr pentru numerele compuse, dar nu va fi MMI-ul său):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • De exemplu:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Creați un tabel pentru fiecare MMI până la module log2:
   • Pentru MMI1
     • F (1) = Număr2% Număr1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Număr1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Număr1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Număr1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Număr1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Număr1 = 1 * 1% 35 = 1
   • Calculați numerele pereche 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
   • Pentru MMI2
     • F (1) = Număr1% Număr2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Număr2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Număr2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Număr2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Număr2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Număr2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Număr2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Număr2 = 35 * 35 mod 97 = 61
   • Calculați numărul asociat 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 Calculați (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
   • Răspuns = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Răspuns = (2619 + 4270)% 3395
   • Răspuns = 99
6. 6 Verificați dacă numărul 1 nu este prim
   • Calculați (Răspuns - Valoare1)% Număr1
   • 99 – 1 % 35 = 28
   • Deoarece 28 este mai mare decât 0, 35 nu este un număr prim.
7. 7 Verificați dacă numărul 2 este prim.
   • Calculați (Răspuns - Valoare2)% Număr2
   • 99 – 2 % 97 = 0
   • Deoarece 0 este 0, 97 este cel mai probabil un număr prim.
8. 8 Repetați pașii de la 1 la 7 de cel puțin încă două ori.
   • Dacă primiți 0 la pasul 7:
     • Folosiți un număr diferit 1 dacă numărul 1 nu este prim.
     • Folosiți un alt număr 1 dacă numărul 1 este prim. În acest caz, ar trebui să obțineți 0 în pașii 6 și 7.
     • Folosiți diferite semnificații1 și semnificații2.
   • Dacă la pasul 7 obțineți în mod constant 0, atunci numărul 2 este foarte probabil să fie prim.
   • Pașii de la 1 la 7 pot duce la o eroare dacă Numărul 1 nu este prim și Numărul 2 este divizor al Numărului 1. Metoda descrisă funcționează în toate cazurile când ambele numere sunt prime.
   • Motivul pentru care trebuie să repetați pașii de la 1 la 7 este că, în unele cazuri, chiar dacă numărul 1 și numărul 2 nu sunt prime, în pasul 7 veți obține 0 (pentru unul sau ambele numere). Acest lucru se întâmplă rar.Alegeți un alt număr1 (compozit), iar dacă numărul 2 nu este prim, atunci numărul 2 nu va fi egal cu zero în pasul 7 (cu excepția cazului în care numărul 1 este divizor al numărului 2 - aici primele vor fi întotdeauna egale cu zero în pasul 7).

sfaturi

• Numere prime de la 168 la 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.
• Deși testarea forței brute este un test obositor atunci când se lucrează cu un număr mare, este destul de eficient pentru un număr mic. Chiar și în cazul numerelor mari, începeți prin testarea divizorilor mici, apoi treceți la metode mai sofisticate pentru verificarea simplității numerelor (dacă nu se găsesc divizori mici).

De ce ai nevoie

• Hârtie, pix sau computer