Conţinut

• A calca
• Metoda 1 din 4: Încercați să împărțiți
• Metoda 2 din 4: Folosirea Micii Teoreme a lui Fermat
• Metoda 3 din 4: Utilizarea testului Miller-Rabin
• Metoda 4 din 4: Utilizarea teoremei restului chinezesc
• sfaturi
• Necesități

Numerele prime sunt numere care sunt divizibile doar de la sine și se numesc 1 - alte numere compus numere. Când vine vorba de testarea dacă un număr este prim, există mai multe opțiuni. Unele dintre aceste metode sunt relativ simple, dar deloc practice pentru un număr mai mare. Alte teste care sunt adesea folosite sunt de fapt algoritmi completi pe baza unuia probabilitate care uneori consideră greșit un număr ca prim. Citiți la pasul 1 pentru a afla cum să vă testați dacă aveți de-a face cu un număr prim.

A calca

Metoda 1 din 4: Încercați să împărțiți

Încercarea de a împărți este de departe cea mai ușoară modalitate de a testa un număr. Pentru numere mici, este de obicei și cel mai rapid mod. Testul se bazează pe definiția unui număr prim: un număr este prim dacă este divizibil doar prin el însuși și 1.

1. Presupune n este numărul pe care doriți să-l testați. Împarte numărul n la toate numerele întregi posibile divizibile. Pentru numere mai mari, cum ar fi n = 101, este extrem de impracticabil să împărțiți cu orice număr întreg mai mic decât n. Din fericire, există mai multe trucuri pentru a reduce numărul de factori de testat.
2. Determinați dacă n chiar. Toate numerele pare sunt complet divizibile cu 2. Prin urmare, dacă n este par, puteți spune asta n este un număr compus (și, prin urmare, nu un număr prim). Pentru a determina rapid dacă un număr este par, trebuie doar să acordați atenție ultimei cifre. Dacă ultima cifră este 2, 4, 6, 8 sau 0, atunci numărul este par și nu prim.
   • Singura excepție de la această regulă este numărul 2 în sine, care, deoarece este divizibil prin el însuși și 1, este, de asemenea, prim. 2 este singurul prim egal.
3. Parte n cu orice număr între 2 și n-1. Deoarece un număr prim nu are alți factori decât el însuși și 1 și pentru că factorii întregi sunt mai mici decât produsul lor, verificarea divizibilității unui număr întreg mai mic decât n și mai mare decât 2 va determina dacă n este prim. Începem după 2, deoarece numerele pare (multipli de 2) nu pot fi numere prime. Acest lucru este departe de a fi un mod eficient de testare, așa cum veți vedea mai jos.
   • De exemplu, dacă am dori să folosim această metodă pentru a testa dacă 11 este prim sau nu, am împărți 11 la 3, 4, 5, 6, 7, 8, 9 și 10, căutând un răspuns întreg fără rest. Deoarece niciunul dintre aceste numere nu se încadrează complet în 11, putem spune că 11 este unul este prim.
4. Pentru a economisi timp, testați doar până la sqrt (n), rotunjit. Testarea unui număr n prin verificarea tuturor numerelor între 2 și n-1 poate dura rapid mult timp. De exemplu, dacă am dori să verificăm dacă 103 este prim cu această metodă, ar trebui să împărțim la 3, 4, 5, 6, 7 ... etc, până la 102! Din fericire, nu este necesar să testați așa. În practică, este necesar doar să se testeze factorii între 2 și rădăcina pătrată a lui n. Dacă rădăcina pătrată a lui n nu este un număr, rotunjiți-l la cel mai apropiat număr întreg și testați acest număr. Vedeți mai jos pentru o explicație:
   • Să examinăm factorii de 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 și 100 × 1. Rețineți că după 10 × 10, factorii sunt aceiași dacă asta pentru 10 × 10, doar atunci a răsturnat. În general, putem ignora factorii n mai mari decât sqrt (n) deoarece sunt pur și simplu o continuare a factorilor mai mici decât sqrt (n).
   • Să încercăm un exemplu. Dacă n = 37, atunci nu este nevoie să testăm toate numerele de la 3 la 36 pentru a determina dacă n este prim. În schimb, trebuie doar să ne uităm la numerele cuprinse între 2 și sqrt (37) (rotunjit în sus).
     • sqrt (37) = 6.08 - vom rotunji acest lucru la 7.
     • 37 nu este complet divizibil cu 3, 4, 5, 6 și 7 și astfel putem afirma cu încredere că este unul număr prim este.
5. Pentru a economisi și mai mult timp, folosim doar factori primi. Este posibil să se facă procesul de testare prin împărțirea și mai scurtă prin neincluderea acelor factori care nu sunt numere prime. Prin definiție, fiecare număr compus poate fi exprimat ca produsul a două sau mai multe numere prime. Deci, împărțirea numărului n la un număr compus nu este necesară - acest lucru este echivalent cu împărțirea la numere prime de mai multe ori. Deci, putem restrânge în continuare lista posibililor factori la numere prime mai mici decât sqrt (n).
   • Aceasta înseamnă că toți factorii pare, precum și factorii care sunt multipli ai numerelor prime, pot fi omiși.
   • De exemplu, să încercăm să determinăm dacă 103 este prim sau nu. Rădăcina pătrată a lui 103 este 11 (rotunjită în sus). Numerele prime cuprinse între 2 și 11 sunt 3, 5, 7 și 11. 4, 6, 8 și 10 sunt pare și 9 este multiplu de 3, un număr prim, deci îl putem sări peste. Făcând acest lucru, am redus lista noastră cu posibili factori la doar 4 numere!
     • 103 nu este complet divizibil nici cu 3, 5, 7, nici cu 11, deci știm acum că 103 este unul număr prim este.

Metoda 2 din 4: Folosirea Micii Teoreme a lui Fermat

În 1640, matematicianul francez Pierre de Fermat a propus mai întâi o teoremă (numită acum după el) care poate fi foarte utilă pentru a determina dacă un număr este sau nu prim. Din punct de vedere tehnic, testul Fermat este destinat să verifice dacă un număr este compus, mai degrabă decât prim. Acest lucru se datorează faptului că testul poate arăta cu „certitudine absolută” că un număr este compus, dar numai o „probabilitate” ca un număr să fie prim. Micuța teoremă a lui Fermat este utilă în situațiile în care încercarea de a împărți este imposibilă și când există o listă de numere disponibile care sunt excepții de la teoremă.

1. Presupune n numărul este pentru testare. Folosiți acest test pentru a determina dacă un număr dat n este prim. Totuși, așa cum s-a menționat mai sus, această teoremă poate caracteriza uneori în mod eronat un compus ca prim. Este important să țineți cont de acest lucru și să verificați răspunsul dvs., care este explicat mai jos.
2. Alegeți un număr întreg A între 2 și n-1 (inclusiv). Numărul întreg exact pe care îl alegeți nu este important. Deoarece parametrii pentru a includ 2 și n-1, îi puteți utiliza și.
   • Un exemplu: Este 100 prime sau nu. Să presupunem că luăm 3 ca valoare de testare - aceasta este între 2 și n-1, deci este suficientă.
3. calculati A (mod n). Elaborarea acestei expresii necesită o anumită cunoaștere a unui sistem matematic numit matematică modulară. În matematică modulară, numerele revin la zero la atingerea unei anumite valori, cunoscută și sub numele de modulul. Vă puteți gândi la asta ca la un ceas: în cele din urmă, mâna ceasului va reveni la ora 1 după ora 12, nu la ora 13. Modulul este notat ca (mod n). Deci, în acest pas calculați a cu un modul de n.
   • O altă metodă este să calculați a, apoi să o împărțiți cu n, apoi să folosiți restul ca răspuns. Calculatoarele specializate cu funcție de modul pot fi foarte utile atunci când se împart numere mari, deoarece pot calcula imediat restul unei diviziuni.
   • Folosind un astfel de calculator în exemplul nostru, putem vedea că 3/100 are un rest de 1. Deci, 3 (mod 100) este 1.
4. Dacă calculăm acest lucru manual, vom folosi exponentul ca format scurt. Dacă nu aveți un calculator cu funcție de modul, utilizați notația cu un exponent pentru a simplifica procedura de determinare a restului. Vezi mai jos:
   • În exemplul nostru, calculăm 3 cu un modul de 100. 3 este un număr foarte, foarte mare - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - atât de mare încât devine foarte dificil de lucrat. Decât să folosim răspunsul de 48 de cifre pentru 3, mai bine îl scriem ca exponent, deci (((((((3)*3))))*3)). Amintiți-vă că luarea exponentului unui exponent are ca efect multiplicarea exponenților ((x) = x).
     • Acum putem determina restul. Începeți prin rezolvarea ((((((3) * 3)))) * 3)) la setul interior de paranteze și ieșiți, împărțind fiecare pas la 100. Odată ce am găsit restul, îl vom folosi pentru pasul următor, mai degrabă decât pentru răspunsul real. Vezi mai jos:
       • ((((((9) * 3)))) * 3)) - 9/100 nu are rest, așa că putem continua.
       • (((((27)))) * 3)) - 27/100 nu are rest, deci putem merge mai departe.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Restul nostru este 29. Continuăm cu pasul următor, nu 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Folosim restul nostru 41 din nou în pasul următor.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Utilizăm restul nostru 81 în pasul următor.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Vom folosi restul nostru 43 în pasul următor.
       • (43 = 1849) - 1849/100 = 18 R 49. Vom folosi restul nostru 49 în pasul următor.
       • 49 = 2401 - 2401/100 = 24 R 1. restul nostru final este 1. Cu alte cuvinte, 3 (mod 100) = 1. Rețineți că acesta este același răspuns pe care l-am calculat în pasul anterior!
5. Află dacă A (mod n) = A (mod n). Dacă nu, n este compus. Dacă este adevărat, atunci n probabil, (dar nu sigur) un număr prim. Repetarea testului cu valori diferite pentru a poate face rezultatul mai sigur, dar există numere compuse rare care satisfac teorema lui Fermat pentru toate valorile lui a. Acestea se numesc numere Carmichael - cel mai mic dintre aceste numere este 561.
   • În exemplul nostru, 3 (mod 100) = 1 și 3 (mod 100) = 3,1 ≠ 3, deci putem spune că 100 este un număr compus.
6. Folosiți numerele Carmichael pentru a fi siguri de rezultatul dvs. Știind ce numere îndeplinesc seria Carmichael înainte de a continua, vă puteți salva o mulțime de îngrijorări cu privire la faptul dacă un număr este sau nu prim. În general, numerele lui Carmichael sunt produsul numerelor prime individuale, unde pentru toate numerele prime se consideră că dacă p este divizor al lui n, atunci și p-1 este divizorul lui n-1. Lista online a numerelor lui Carmichael poate fi foarte utilă pentru a determina dacă un număr este prim, folosind Teorema mică a lui Fermat.
   
   

Metoda 3 din 4: Utilizarea testului Miller-Rabin

Testul Miller-Rabin funcționează în același mod ca teorema mică a lui Fermat, dar se ocupă mai bine cu numerele nestandardizate, cum ar fi numerele Carmichael.

1. Presupune n este un număr impar pe care vrem să-l testăm pentru primalitate. Ca și în metodele indicate mai sus, n este variabila căreia dorim să o determinăm primalitatea.
2. Presiune n-1 sub forma 2 × d la care d este ciudat. Numărul n este prim dacă este impar. Deci n - 1 trebuie să fie egal. Deoarece n - 1 este par, poate fi scris ca o putere de 2 ori un număr impar. Deci, 4 = 2 × 1; 80 = 2 × 5; și așa mai departe.
   • Să presupunem că vrem să determinăm dacă n = 321 este prim. 321 - 1 = 320, pe care îl putem exprima ca 2 × 5.
     • În acest caz n = 321 este un număr potrivit. Determinarea n - 1 pentru n = 371 poate necesita o valoare mare pentru d, făcând întregul proces mai dificil într-o etapă ulterioară. 371 - 1 = 370 = 2 × 185
3. Alegeți orice număr A între 2 și n-1. Numărul exact pe care îl alegeți nu contează - doar că trebuie să fie mai mic decât n și mai mare de 1.
   • În exemplul nostru cu n = 321, alegem a = 100.
4. calculati A (mod n). Dacă A = 1 sau -1 (mod n), apoi trece n testul Miller-Rabin și este probabil un număr prim. Ca și în cazul teoremei mici a lui Fermat, acest test nu poate determina cu certitudine absolută primalitatea unui număr, dar necesită teste suplimentare.
   • În exemplul nostru cu n = 321, a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Folosim un calculator special sau metoda de prescurtare cu un exponent așa cum s-a descris anterior, pentru a găsi restul de 100/321.
     • Deoarece nu am obținut 1 sau -1, nu putem spune cu certitudine că n este prim. Dar sunt încă mai multe de făcut - citiți mai departe.
5. Deoarece rezultatul nu este egal cu 1 sau -1, calculați A, A, ... și așa mai departe, până la Ad. Calculați un ridicat la puterea de d ori, până la 2. Dacă oricare dintre acestea este egal cu 1 sau -1 (mod n), apoi trece n testele Miller-Rabin și este probabil prim. Dacă ați stabilit că n trece testul, verificați răspunsul (consultați pasul de mai jos). Dacă n eșuează la oricare dintre aceste teste, acesta este unul compusă număr.
   • Ca memento, în exemplul nostru, valoarea lui a este 100, valoarea lui s este 6 și d este 5. Continuăm testarea așa cum se arată mai jos:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 sau -1. Continuați să mergeți calm.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244.244 ≠ 1 sau -1.
     • În acest moment ne putem opri. s - 1 = 6 - 1 = 5. Am ajuns acum la 4d = 2 și nu există puteri de 2 ori d sub 5d. Deoarece niciunul dintre calculele noastre nu a răspuns la 1 sau -1, putem spune că n = 321 unul compusă numărul este.
6. Dacă n trece testul Miller-Rabin, repetați pentru celelalte valori ale A. Dacă ați constatat că valoarea lui n poate fi primă, încercați din nou cu o valoare diferită, aleatorie pentru a pentru a confirma rezultatul testului. Dacă n este de fapt prim, va fi adevărat pentru orice valoare a. Dacă n este un număr compus, va eșua pentru trei sferturi din valorile lui a. Acest lucru vă oferă mai multă certitudine decât Teorema mică a lui Fermat, unde anumite numerele compuse (numerele Carmichael) trec testul pentru orice valoare a.

Metoda 4 din 4: Utilizarea teoremei restului chinezesc

1. Alegeți două numere. Unul dintre numere nu este prim, iar al doilea este numărul testat pentru primalitate.
   • „Numărul de testare1” = 35
   • Numărul de test2 = 97
2. Alegeți două puncte de date mai mari decât zero și mai mici decât TestNumber1 și respectiv TestNumber2. Nu pot fi egali între ei.
   • Date1 = 1
   • Date2 = 2
3. Calculați MMI (inversă multiplicativă matematică) pentru numărul de test 1 și numărul de test 2
   • Calculați MMI
     • MMI1 = Test Number2 ^ -1 Mod Test Number1
     • MMI2 = Număr test1 ^ -1 Mod Număr test2
   • Numai pentru numerele prime (va exista un rezultat pentru numerele non prime, dar acesta nu este MMI):
     • MMI1 = (NumărTest2 ^ (NumărTest1-2))% NumărTest1
     • MMI2 = (NumărTest1 ^ (NumărTest-2))% NumărTest2
   • Asa de:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Creați un tabel binar pentru fiecare MMI până la Log2 al modulului
   • Pentru MMI1
     • F (1) = Număr test 2% Număr test 1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Număr test 1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Număr test 1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Număr test 1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Număr test 1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Număr test 1 = 1 * 1% 35 = 1
   • Calculați logaritmul binar al TestNumber1 - 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ăr test 1% Număr test 2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Număr test2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Număr test2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Număr test2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Număr test2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Număr test2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Număr test2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Număr test2 = 35 * 35 mod 97 = 61
   • Calculați logaritmul binar al TestNumber2 - 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. Calculați (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Răspuns = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Răspuns = (2619 + 4270)% 3395
   • Răspuns = 99
6. Verificați dacă „TestNumber1” nu este prime1
   • Calculați (Răspuns - Date1)% Număr test1
   • 99 -1 % 35 = 28
   • Deoarece 28 este mai mare decât 0, 35 nu este prim
7. Verificați dacă TestNumber2 este prim
   • Calculați (Răspuns - Date2)% Număr test2
   • 99 - 2 % 97 = 0
   • Deoarece 0 este egal cu 0, 97 este un număr prim potențial
8. Repetați pașii de la 1 la 7 de cel puțin încă două ori.
   • Dacă pasul 7 este egal cu 0:
     • Utilizați un alt „NumărTest1” dacă NumărTest1 nu este prim.
     • Utilizați un alt număr de testare1 în care un număr de testare1 este de fapt prim. În acest caz, pașii 6 și 7 sunt egali cu 0.
     • Utilizați diferite puncte de date pentru data1 și data2.
   • Dacă pasul 7 este întotdeauna egal cu 0, atunci probabilitatea ca numărul 2 să fie un număr prim este foarte mare.
   • Pașii de la 1 la 7 sunt cunoscuți a fi incorecte în anumite cazuri când primul număr nu este prim, iar al doilea este un factor prim al numărului non-prim "Numărul de test 1". Funcționează în toate scenariile în care ambele numere sunt prime.
   • Motivul pentru care pașii de la 1 la 7 se repetă se datorează faptului că există câteva scenarii în care, chiar dacă NumărulTest1 nu este prim și NumărulTest2 nu este prim, oricare dintre numărul de la Pasul 7 este încă zero. Aceste condiții sunt rare. Prin schimbarea TestNumber1 cu un alt număr non-prim, dacă TestNumber2 nu este prim, TestNumber2 nu va mai fi egal cu zero, la pasul 7. Cu excepția cazului în care "TestNumber1" este un factor al TestNumber2, numerele prime vor fi întotdeauna zero. pasul 7.

sfaturi

• 168 de numere prime sub 1000 sunt: ​​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
• Când încercați să împărțiți este mai lent decât metodele mai sofisticate, este încă eficient pentru un număr mai mic. Chiar și atunci când testați numere mai mari, nu este neobișnuit să verificați mai întâi numerele mici înainte de a trece la metodele mai avansate.

Necesități

• Hârtie, stilou, creion și / sau calculator pentru antrenament