Content

• Per trepitjar
• Mètode 1 de 4: intenteu dividir
• Mètode 2 de 4: Utilització del petit teorema de Fermat
• Mètode 3 de 4: utilitzar la prova de Miller-Rabin
• Mètode 4 de 4: Utilització del teorema de la resta de la Xina
• Consells
• Necessitats

Els nombres primers són nombres que només són divisibles per si mateixos i s’anomenen 1 - altres nombres compost números. A l’hora de provar si un nombre és primer, hi ha diverses opcions. Alguns d'aquests mètodes són relativament senzills, però gens pràctics per a un nombre més gran. Altres proves que s'utilitzen sovint són algoritmes complets basats en un probabilitat que de vegades consideren erròniament un nombre com a primer. Seguiu el pas 1 per aprendre a provar-vos si teniu un número primer.

Per trepitjar

Mètode 1 de 4: intenteu dividir

Intentar dividir és, amb diferència, la forma més senzilla de provar un número. Per a xifres petites, també sol ser la forma més ràpida. La prova es basa en la definició d’un nombre primer: un nombre és primer si només és divisible per si mateix i 1.

1. Suposem n és el número que voleu provar. Dividiu el nombre n per tots els enters possibles divisibles. Per a nombres més grans com n = 101, és molt poc pràctic dividir per qualsevol enter possible inferior a n. Afortunadament, hi ha diversos trucs per reduir el nombre de factors a provar.
2. Determineu si n fins i tot. Tots els nombres parells són completament divisibles per 2. Per tant, si n és parell, podeu dir-ho n és un nombre compost (i per tant no és un nombre primer). Per determinar ràpidament si un número és parell, només cal parar atenció a l’últim dígit. Si l’últim dígit és un 2, 4, 6, 8 o 0, el nombre és parell i no és primer.
   • L'única excepció a aquesta regla és el mateix número 2, que, perquè és divisible per si mateix i l'1, també és primer. 2 és l'únic primer parell.
3. Part n per qualsevol nombre entre 2 i n-1. Com que un nombre primer no té cap altre factor que ell mateix i 1, i perquè els factors enters són menors que el seu producte, comprovar la divisibilitat d’un enter inferior a n i superior a 2 determinarà si n és primer. Comencem després de 2 perquè els nombres parells (múltiples de 2) no poden ser nombres primers. Això està lluny de ser una manera eficaç de provar, com es veurà a continuació.
   • Per exemple, si volguéssim utilitzar aquest mètode per comprovar si 11 és primer o no, dividiríem 11 per 3, 4, 5, 6, 7, 8, 9 i 10, cercant una resposta sencera sense resta. Com que cap d’aquests números s’adapta completament a l’11, podem dir que l’11 és un és primer.
4. Per estalviar temps, només proveu fins a sqrt (n), arrodonit. Provar un número n comprovant tots els números entre 2 i n-1 pot trigar molt de temps ràpidament. Per exemple, si volguéssim comprovar si 103 és el primer amb aquest mètode, hauríem de dividir per 3, 4, 5, 6, 7 ... etc, fins a 102! Afortunadament, no cal fer proves així. A la pràctica, només cal provar els factors entre 2 i l’arrel quadrada de n. Si l’arrel quadrada de n no és un nombre, arrodoneu-la al nombre enter més proper i proveu aquest número. Vegeu a continuació una explicació:
   • Examinem els factors de 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 i 100 × 1. Tingueu en compte que després de 10 × 10, els factors són els mateixos si això és de 10 × 10, només es dóna la volta. En general, podem ignorar els factors de n majors de sqrt (n), ja que són simplement una continuació de factors menors de sqrt (n).
   • Provem un exemple. Si n = 37, no cal que provem tots els números del 3 al 36 per determinar si n és primer. En lloc d’això, només hem de mirar els números entre 2 i sqrt (37) (arrodonit cap amunt).
     • sqrt (37) = 6,08: arrodonirem fins a 7.
     • 37 no és completament divisible per 3, 4, 5, 6 i 7 i, per tant, podem afirmar amb seguretat que és un nombre primer és.
5. Per estalviar encara més temps, només utilitzem factors primers. És possible fer el procés de proves dividint encara més curt en no incloure aquells factors que no són nombres primers. Per definició, cada nombre compost es pot expressar com el producte de dos o més nombres primers. Per tant, no és necessari dividir el nombre n per un nombre compost: equival a dividir per nombres primers diverses vegades. Per tant, podem restringir encara més la llista de possibles factors a només nombres primers inferiors a sqrt (n).
   • Això significa que es poden ometre tots els factors parells, així com els factors que són múltiples de nombres primers.
   • Per exemple, intentem determinar si 103 és primer o no. L’arrel quadrada de 103 és 11 (arrodonida cap amunt). Els nombres primers entre 2 i 11 són 3, 5, 7 i 11. 4, 6, 8 i 10 són parells i 9 és múltiple de 3, un nombre primer, de manera que podem saltar-lo. En fer això, hem reduït la nostra llista de possibles factors a només 4 números.
     • 103 no és completament divisible ni per 3, 5, 7 ni per 11, de manera que ara sabem que 103 és un nombre primer és.

Mètode 2 de 4: Utilització del petit teorema de Fermat

El 1640, el matemàtic francès Pierre de Fermat va proposar per primera vegada un teorema (que ara porta el seu nom) que pot ser molt útil per determinar si un nombre és primer o no. Tècnicament, la prova de Fermat està destinada a verificar que un nombre sigui compost, en lloc de primer. Això es deu al fet que la prova pot mostrar amb "absoluta certesa" que un nombre és compost, però només una "probabilitat" que un nombre sigui primer. El petit teorema de Fermat és útil en situacions en què no és pràctic intentar dividir i quan hi ha una llista de nombres disponibles que són excepcions al teorema.

1. Suposem n el número és per a proves. Utilitzeu aquesta prova per determinar si un nombre determinat n és primer. Tanmateix, com es va assenyalar anteriorment, aquest teorema pot caracteritzar erròniament alguns compostos com a primers. És important tenir-ho en compte i comprovar la vostra resposta, que s’explica a continuació.
2. Trieu un nombre enter a entre 2 i n-1 (inclòs). El número enter exacte que trieu no és important. Com que els paràmetres per a inclouen 2 i n-1, també els podeu utilitzar.
   • Un exemple: és 100 primer o no. Suposem que prenem 3 com a valor de prova: es troba entre 2 i n-1, de manera que és suficient.
3. calcular a (mod n). Per elaborar aquesta expressió es requereix un cert coneixement d’un sistema matemàtic anomenat matemàtiques modulars. En matemàtiques modulars, els números tornen a zero en assolir un valor determinat, també conegut com a mòdul. Es pot pensar en això com en un rellotge: amb el temps, l’agulla del rellotge tornarà a la 1 hora després de les 12, no a les 13. El mòdul s’anota com (mod n). Així doncs, en aquest pas calculeu a amb un mòdul de n.
   • Un altre mètode és calcular a, després dividir-la per n, i després utilitzar la resta com a resposta. Les calculadores especialitzades amb funció de mòdul poden ser molt útils quan es divideixen nombres grans, ja que poden calcular immediatament la resta d’una divisió.
   • Utilitzant aquesta calculadora al nostre exemple, podem veure que 3/100 té una resta d’1. Per tant, 3 (mod 100) és 1.
4. Si ho calculem a mà, utilitzarem l’exponent com a format curt. Si no teniu una calculadora amb funció de mòdul, utilitzeu la notació amb un exponent per facilitar el procediment per determinar la resta. Mirar abaix:
   • En el nostre exemple, calculem 3 amb un mòdul de 100. 3 és un nombre molt, molt gran: 515.377.520.732.011.331.036.461.129.765.621.272.702.107.522.001 - tan gran que es fa molt difícil treballar-hi. En lloc d’utilitzar la resposta de 48 dígits per a 3, és millor que l’escrivim com a exponent (((((((3)*3))))*3)). Recordeu que prendre l'exponent d'un exponent té l'efecte de multiplicar els exponents ((x) = x).
     • Ara podem determinar la resta. Comenceu per resoldre ((((((3) * 3)))) * 3)) al conjunt intern de parèntesis i sortiu, dividint cada pas per 100. Un cop trobem la resta, l’utilitzarem per al següent pas en lloc de la resposta real. Mirar abaix:
       • ((((((9) * 3)))) * 3)) - 9/100 no té resta, de manera que podem continuar.
       • (((((27)))) * 3)) - 27/100 no té resta, de manera que podem seguir endavant.
       • ((((729))) * 3)) - 729/100 = 7 R 29. La nostra resta és 29. Continuem amb el següent pas, no 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Tornem a utilitzar la resta 41 en el següent pas.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Utilitzem la nostra resta 81 al següent pas.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Utilitzarem la nostra resta 43 al següent pas.
       • (43 = 1849) - 1849/100 = 18 R 49. Utilitzarem la nostra resta 49 al següent pas.
       • 49 = 2401 - 2401/100 = 24 R 1. el nostre residu final és 1. En altres paraules, 3 (mod 100) = 1. Tingueu en compte que aquesta és la mateixa resposta que hem calculat al pas anterior.
5. Esbrineu si a (mod n) = a (mod n). Si no, n és compost. Si és cert, llavors n probablement, (però no estic segur) un nombre primer. Repetir la prova amb valors diferents per a pot fer que el resultat sigui més segur, però hi ha nombres compostos rars que compleixen el teorema de Fermat per a tot Els valors de A. Es denominen nombres de Carmichael: el més petit d'aquests nombres és 561.
   • En el nostre exemple, 3 (mod 100) = 1 i 3 (mod 100) = 3,1 ≠ 3, de manera que podem dir que 100 és un nombre compost.
6. Utilitzeu els números de Carmichael per assegurar-vos del vostre resultat. Saber quins números compleixen la sèrie de Carmichael abans de continuar us pot estalviar molta preocupació per si un número és o no primer. En general, els nombres de Carmichael són el producte de nombres primers individuals, on per a tots els nombres primers es considera que si p és divisor de n, llavors també p-1 és divisor de n-1. La llista en línia de nombres de Carmichael pot ser molt útil per determinar si un nombre és primer, utilitzant el Petit Teorema de Fermat.
   
   

Mètode 3 de 4: utilitzar la prova de Miller-Rabin

La prova de Miller-Rabin funciona de la mateixa manera que el petit teorema de Fermat, però tracta millor els nombres no estàndards com els nombres de Carmichael.

1. Suposem n és un nombre senar que volem provar per a la primalitat. Com en els mètodes indicats anteriorment, n és la variable de la qual volem determinar la primalitat.
2. Pressió n-1 en la forma 2 × d una bruixa d és estrany. El nombre n és primer si és senar. Per tant, n - 1 ha de ser parell. Com que n - 1 és parell, es pot escriure com una potència de 2 vegades un nombre senar. Per tant, 4 = 2 × 1; 80 = 2 × 5; etcètera.
   • Suposem que volem determinar si n = 321 és primer. 321 - 1 = 320, que podem expressar com 2 × 5.
     • En aquest cas, n = 321 és un nombre adequat. Determinar n - 1 per a n = 371 pot requerir un gran valor per a d, cosa que dificulta tot el procés en una etapa posterior. 371 - 1 = 370 = 2 × 185
3. Tria qualsevol número a entre 2 i n-1. El número exacte que trieu no importa, només ha de ser inferior a n i superior a 1.
   • Al nostre exemple amb n = 321, escollim a = 100.
4. calcular a (mod n). Si a = 1 o -1 (mod n), després passa n la prova de Miller-Rabin i és probablement un nombre primer. Com passa amb el Petit teorema de Fermat, aquesta prova no pot determinar amb absoluta certesa la primalitat d’un nombre, però requereix proves addicionals.
   • En el nostre exemple amb n = 321, a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Utilitzem una calculadora especial, o el mètode abreujat amb un exponent com es va descriure anteriorment, per trobar la resta de 100/321.
     • Com que no hem obtingut 1 o -1, no podem dir amb certesa que n sigui primer. Però encara hi ha més coses que hem de fer: continuar llegint.
5. Com que el resultat no és igual a 1 o -1, calculeu a, a, ... i així successivament, fins a ad. Calculeu un augmentat a la potència de d vegades, fins a 2. Si algun d’aquests és igual a 1 o -1 (mod n), després passa n les proves de Miller-Rabin i probablement és el primer. Si heu determinat que n supera la prova, comproveu la vostra resposta (vegeu el pas següent). Si n falla en cap d'aquestes proves, és una compost número.
   • Com a recordatori, en el nostre exemple, el valor de a és 100, el valor de s és 6 i d és 5. Continuem provant com es mostra a continuació:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 o -1. Seguiu amb calma.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244.244 ≠ 1 o -1.
     • En aquest punt podem parar. s - 1 = 6 - 1 = 5. Ara hem arribat a 4d = 2 i no hi ha potències de 2 vegades d per sota de 5d. Com que cap dels nostres càlculs no va respondre a 1 ni -1, podem dir que n = 321 compost el número és.
6. Si n passa la prova de Miller-Rabin, repeteix per als altres valors de a. Si heu trobat que el valor de n podria ser primer, torneu-ho a provar amb un valor aleatori diferent per a per confirmar el resultat de la prova. Si n és primer, serà cert per a qualsevol valor de a. Si n és un nombre compost, fallarà durant tres quartes parts dels valors de a. Això us dóna més certesa que el petit teorema de Fermat, on certs els nombres compostos (els nombres de Carmichael) passen la prova de qualsevol valor de a.

Mètode 4 de 4: Utilització del teorema de la resta de la Xina

1. Tria dos números. Un dels nombres no és primer i el segon és el nombre que s’està comprovant la primalitat.
   • "Número de prova1" = 35
   • Número de prova 2 = 97
2. Trieu dos punts de dades superiors a zero i inferiors a TestNumber1 i TestNumber2, respectivament. No poden ser iguals entre ells.
   • Dades1 = 1
   • Dades2 = 2
3. Calculeu el MMI (invers matemàtic multiplicatiu) per a la prova número 1 i la prova número 2
   • Calculeu el MMI
     • MMI1 = Test Number2 ^ -1 Mod Test Number1
     • MMI2 = Número de prova1 ^ -1 Mod Número de prova2
   • Només per a nombres primers (hi haurà un resultat per a nombres no primers, però aquest no és el MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Tan:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Creeu una taula binària per a cada MMI fins a Log2 del mòdul
   • Per al MMI1
     • F (1) = Número de prova2% Número de prova1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Número de prova1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Número de prova1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Número de prova1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Número de prova1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Número de prova1 = 1 * 1% 35 = 1
   • Calculeu el logaritme binari de TestNumber1 - 2
     • 35 -2 = 33 (10001) base 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Per a MMI2
     • F (1) = Número de prova1% Número de prova2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Número de prova2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Número de prova2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Número de prova2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Número de prova2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Número de prova2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Número de prova2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Número de prova2 = 35 * 35 mod 97 = 61
   • Calculeu el logaritme binari de TestNumber2-2
     • 97 - 2 = 95 = (1011111) base 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 (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Resposta = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Resposta = (2619 + 4270)% 3395
   • Resposta = 99
6. Comproveu que "TestNumber1" no sigui prime1
   • Calcula (Resposta - Dades1)% Número de prova1
   • 99 -1 % 35 = 28
   • Com que 28 és superior a 0, 35 no és primer
7. Comproveu si el número de prova2 és primer
   • Calcula (Resposta - Dades2)% Número de prova2
   • 99 - 2 % 97 = 0
   • Com que 0 és igual a 0, 97 és un nombre primer potencial
8. Repetiu els passos 1 a 7 almenys dues vegades més.
   • Si el pas 7 és igual a 0:
     • Utilitzeu un "TestNumber1" diferent si TestNumber1 no és primer.
     • Utilitzeu un altre TestNumber1 on un TestNumber1 sigui realment primer. En aquest cas, els passos 6 i 7 són iguals a 0.
     • Utilitzeu diferents punts de dades per a dades1 i dades2.
   • Si el pas 7 sempre és igual a 0, la probabilitat que el número 2 sigui un nombre primer és molt alta.
   • Se sap que els passos de l'1 al 7 són incorrectes en determinats casos en què el primer nombre no és primer i el segon és un factor primer del nombre no primer "Número de prova1". Funciona en tots els escenaris en què els dos números són primers.
   • La raó per la qual es repeteixen els passos 1 a 7 és perquè hi ha alguns escenaris en què, fins i tot si TestNumber1 no és primer i TestNumber2 no és primer, qualsevol dels números del pas 7 continua sent zero. Aquestes afeccions són rares. Si canvieu TestNumber1 a un altre nombre no primer, si TestNumber2 no és primer, TestNumber2 deixarà de ser igual a zero, al pas 7. Excepte el cas en què "TestNumber1" és un factor de TestNumber2, els nombres primers sempre seran zero pas 7.

Consells

• Els 168 nombres primers inferiors a 1000 són: 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
• Quan es tracta de dividir és més lent que els mètodes més sofisticats, encara és eficient per a nombres més petits. Fins i tot en provar nombres més grans, no és estrany comprovar primer els nombres petits abans de canviar als mètodes més avançats.

Necessitats

• Paper, bolígraf, llapis i / o calculadora per fer exercici