Contenuto

• Passi
• Parte 1 di 3: test di semplicità
• Parte 2 di 3: come funzionano i test di semplicità
• Parte 3 di 3: utilizzo del teorema cinese del resto
• Consigli
• Di che cosa hai bisogno

I numeri primi sono numeri divisibili solo per se stessi e per 1. Tutti gli altri numeri sono chiamati numeri composti. Ci sono molti modi per determinare se un numero è primo e tutti hanno i loro vantaggi e svantaggi. Da un lato, alcuni metodi sono molto accurati, ma sono piuttosto complessi se hai a che fare con grandi numeri. D'altra parte, ci sono modi molto più veloci, ma possono portare a risultati errati. La scelta del metodo appropriato dipende dalla grandezza dei numeri con cui stai lavorando.

Passi

Parte 1 di 3: test di semplicità

Nota: in tutte le formule n indica il numero da controllare.

1. 1 Enumerazione dei divisori. Basta dividere n a tutti i numeri primi da 2 al valore arrotondato (${ displaystyle { sqrt {n}}}$).
2. 2 Piccolo teorema di Fermat. Attenzione: a volte il test identificherà erroneamente i numeri composti come primi, anche per tutti i valori di a.
   • Scegliamo un numero intero untale che 2 ≤ a ≤ n - 1.
   • Se a (mod n) = a (mod n) allora il numero è probabilmente primo. Se l'uguaglianza non è soddisfatta, il numero n è composto.
   • Controlla l'uguaglianza data per più valori unper aumentare la probabilità che il numero in esame sia effettivamente primo.
3. 3 Test di Miller-Rabin. Attenzione: a volte, anche se raramente, per più valori di a, il test identificherà erroneamente i numeri composti come primi.
   • Trova le quantità s e d tali che ${ stile di visualizzazione n-1 = 2 ^ {s} * d}$.
   • Seleziona un numero intero un nell'intervallo 2 ≤ a ≤ n - 1.
   • Se a = +1 (mod n) o -1 (mod n), allora n è probabilmente primo. In questo caso, vai al risultato del test. Se l'uguaglianza non è valida, vai al passaggio successivo.
   • Piazza la tua risposta (${ displaystyle a ^ {2d}}$). Se ottieni -1 (mod n), allora n è probabilmente un numero primo. In questo caso, vai al risultato del test. Se l'uguaglianza fallisce, ripetere (${ displaystyle a ^ {4d}}$ e così via) fino a ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Se ad un certo punto dopo aver eretto al quadrato un numero diverso da ${ displaystyle pm 1}$ (mod n), hai ottenuto +1 (mod n), quindi n è un numero composto. Se ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), allora n non è primo.
   • Risultato del test: se n supera il test, ripetilo per altri valori unper aumentare la fiducia.

Parte 2 di 3: come funzionano i test di semplicità

1. 1 Enumerazione dei divisori. Per definizione, il numero n è semplice solo se non è divisibile per 2 e altri interi tranne 1 e se stesso. La formula precedente consente di eliminare passaggi non necessari e risparmiare tempo: ad esempio, dopo aver verificato se un numero è divisibile per 3, non è necessario verificare se è divisibile per 9.
   • La funzione floor (x) arrotonda x all'intero più vicino minore o uguale a x.
2. 2 Impara l'aritmetica modulare. L'operazione "x mod y" (mod è un'abbreviazione della parola latina "modulo", cioè "modulo") significa "dividi x per y e trova il resto". In altre parole, nell'aritmetica modulare, al raggiungimento di un certo valore, che si chiama modulo, i numeri "rivolgono" di nuovo a zero. Ad esempio, l'orologio esegue il conto alla rovescia con il modulo 12: mostra 10, 11 e 12 ore, quindi torna a 1.
   • Molte calcolatrici hanno un tasto mod. La fine di questa sezione mostra come calcolare manualmente questa funzione per grandi numeri.
3. 3 Scopri le insidie ​​del Piccolo Teorema di Fermat. Tutti i numeri per i quali le condizioni del test non sono soddisfatte sono composti, ma il resto dei numeri è solo probabilmente sono semplici. Se vuoi evitare risultati errati, cerca n nell'elenco dei "Numeri di Carmichael" (numeri composti che soddisfano questo test) e dei "Numeri pseudoprimi di Fermat" (questi numeri soddisfano le condizioni del test solo per alcuni valori un).
4. 4 Se conveniente, usa il test di Miller-Rabin. Sebbene questo metodo sia piuttosto complicato per i calcoli manuali, viene spesso utilizzato nei programmi per computer. Fornisce una velocità accettabile e meno errori rispetto al metodo di Fermat. Un numero composto non sarà considerato un numero primo se i calcoli vengono eseguiti per più di valori un... Se scegli a caso valori diversi un e per tutti loro il test darà esito positivo, possiamo ritenere con un grado di confidenza abbastanza alto che n è un numero primo.
5. 5 Per i grandi numeri, usa l'aritmetica modulare. Se non hai una calcolatrice mod a portata di mano, o la calcolatrice non è progettata per gestire numeri così grandi, usa le proprietà di potenza e l'aritmetica modulare per rendere i calcoli più facili. Di seguito è riportato un esempio per ${ stile di visualizzazione 3 ^ {50}}$ modulo 50:
   • Riscrivi l'espressione in una forma più comoda: ${ stile di visualizzazione (3 ^ {25} * 3 ^ {25})}$ mod 50. I calcoli manuali possono richiedere ulteriori semplificazioni.
   • ${ stile di visualizzazione (3 ^ {25} * 3 ^ {25})}$ modulo 50 = ${ stile di visualizzazione (3 ^ {25}}$ mod 50 ${ stile di visualizzazione * 3 ^ {25}}$ mod 50) mod 50. Qui abbiamo preso in considerazione la proprietà della moltiplicazione modulare.
   • ${ stile di visualizzazione 3 ^ {25}}$ modulo 50 = 43.
   • ${ stile di visualizzazione (3 ^ {25}}$ mod 50 ${ stile di visualizzazione * 3 ^ {25}}$ mod 50) mod 50 = ${ stile di visualizzazione (43 * 43)}$ modulo 50.
   • ${ displaystyle = 1849}$ modulo 50.
   • ${ stile di visualizzazione = 49}$.

Parte 3 di 3: utilizzo del teorema cinese del resto

1. 1 Scegli due numeri. Uno dei numeri deve essere composto e l'altro deve essere esattamente quello che si desidera testare per semplicità.
   • Numero1 = 35
   • Numero2 = 97
2. 2 Seleziona due valori maggiori di zero e, rispettivamente, minori dei numeri Number1 e Number2. Questi valori non devono essere gli stessi.
   • Valore1 = 1
   • Valore2 = 2
3. 3 Calcola l'MMI (Inverso moltiplicativo matematico) per Numero1 e Numero2.
   • Calcola MMI
     • MMI1 = Numero2 ^ -1 Numero Mod1
     • MMI2 = Numero1 ^ -1 Numero Mod2
   • Solo per i numeri primi (questo darà un numero per i numeri composti, ma non sarà il suo MMI):
     • MMI1 = (Numero2 ^ (Numero1-2))% Numero1
     • MMI2 = (Numero1 ^ (Numero2-2))% Numero2
   • Per esempio:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35^95)% 97
4. 4 Crea una tabella per ogni MMI fino ai moduli log2:
   • Per MMI1
     • F (1) = Numero2% Numero1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Numero1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Numero1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Numero1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Numero1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Numero1 = 1 * 1% 35 = 1
   • Calcola i numeri accoppiati 1 - 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 MMI2
     • F (1) = Numero1% Numero2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Numero2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Numero2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Numero2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Numero2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Numero2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Numero2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Numero2 = 35 * 35 mod 97 = 61
   • Calcola il numero accoppiato 2 - 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. 5 Calcola (Valore1 * Numero2 * MMI1 + Valore2 * Numero1 * MMI2)% (Numero1 * Numero2)
   • Risposta = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Risposta = (2619 + 4270)% 3395
   • Risposta = 99
6. 6 Controlla che Number1 non sia primo
   • Calcola (Risposta - Valore1)% Numero1
   • 99 – 1 % 35 = 28
   • Poiché 28 è maggiore di 0, 35 non è un numero primo.
7. 7 Controlla che Number2 sia primo.
   • Calcola (Risposta - Valore2)% Numero2
   • 99 – 2 % 97 = 0
   • Poiché 0 è 0, 97 è molto probabilmente un numero primo.
8. 8 Ripetere i passaggi da 1 a 7 almeno altre due volte.
   • Se ottieni 0 al passaggio 7:
     • Utilizzare un Numero1 diverso se Numero1 non è primo.
     • Usa un altro Number1 se Number1 è primo. In questo caso, dovresti ottenere 0 nei passaggi 6 e 7.
     • Usa Significato1 e Significato diversi.
   • Se nel passaggio 7 ottieni costantemente 0, è molto probabile che il numero 2 sia primo.
   • I passaggi da 1 a 7 possono generare un errore se Number1 non è primo e Number2 è un divisore di Number1. Il metodo descritto funziona in tutti i casi in cui entrambi i numeri sono primi.
   • Il motivo per cui devi ripetere i passaggi da 1 a 7 è perché in alcuni casi, anche se Numero1 e Numero 2 non sono primi, nel passaggio 7 otterrai 0 (per uno o entrambi i numeri). Questo accade raramente.Scegli un altro Numero1 (composito) e se Numero2 non è primo, allora Numero2 non sarà uguale a zero nel passaggio 7 (tranne il caso in cui Numero1 è un divisore di Numero2 - qui i numeri primi saranno sempre uguali a zero nel passaggio 7).

Consigli

• Numeri primi da 168 a 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.
• Sebbene il test della forza bruta sia un test noioso quando si lavora con numeri grandi, è abbastanza efficiente per numeri piccoli. Anche nel caso di grandi numeri, iniziare testando divisori piccoli, per poi passare a metodi più sofisticati per verificare la semplicità dei numeri (se non si trovano divisori piccoli).

Di che cosa hai bisogno

• Carta, penna o computer