Teorema Cinese del Resto
Uno dei due interi scelti è un numero composto (cioè non primo), mentre il secondo è il numero di cui si vuole testare la primalità.  "Numero_1" = 35 "Numero_2" = 97 Valore_1 = 1 Valore_2 = 2 Calcolo dell'Inverso Moltiplicativo (IM)  IM_1 = Numero_2 ^ -1 mod Numero_1 IM_2 = Numero_1 ^ -1 mod Numero_2   Da usare solo nel caso di numeri primi (questo metodo, nel caso di numeri composti, dà come risultato un valore che non è l'inverso moltiplicativo degli interi di partenza):  IM_1 = (Numero_2 ^ (Numero_1-2)) mod Numero_1 IM_2 = (Numero_1 ^ (Numero_2-2)) mod Numero_2   Nel nostro esempio otterremo:  IM_1 = (97 ^ 33) % 35 IM_2 = (35 ^ 95) % 97 Inverso moltiplicativo IM_1  F(1) = Numero_2 mod Numero_1 = 97 % 35 = 27 F(2) = F(1) * F(1) mod Numero_1 = 27 * 27 % 35 = 29 F(4) =  F(2) * F(2) mod Numero_1 = 29 * 29 % 35 = 1 F(8) = F(4) * F(4) mod Numero_1 = 1 * 1 % 35 = 1 F(16) =F(8) * F(8) mod Numero_1 = 1 * 1 % 35 = 1 F(32) =F(16) * F(16) mod Numero_1 = 1 * 1 % 35 = 1   Calcola il corrispondente binario dell'espressione (Numero_1 - 2)  35 - 2 = 33 = (10001) in base 2 IM_1 = F(33) = F(32) * F(1) mod 35 IM_1 = F(33) = 1 * 27 % 35 IM_1 = 27   Inverso moltiplicativo IM_2  F(1) = Numero_1 mod Numero_2 = 35 % 97 = 35 F(2) = F(1) * F(1) mod Numero_2 = 35 * 35 % 97 = 61 F(4) = F(2) * F(2) mod Numero_2 = 61 * 61 % 97 = 35 F(8)  = F(4) * F(4) mod Numero_2 = 35 * 35 % 97 = 61 F(16) = F(8) * F(8) mod Numero_2 = 61 * 61 % 97 = 35 F(32)  = F(16) * F(16) mod Numero_2 = 35 * 35 % 97 = 61 F(64)  = F(32) * F(32) mod Numero_2 = 61 * 61 % 97 = 35 F(128) = F(64) * F(64) mod Numero_2 = 35 * 35 % 97 = 61   Calcola il corrispondente binario dell'espressione (Numero_2 - 2)  97 - 2 = 95 = (1011111) in base 2 IM_2 = (((((F(64) * F(16) mod 97) * F(8) mod 97) * F(4) mod 97) * F(2) mod 97) * F(1) mod 97) IM_2 = (((((35 * 35) % 97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97) IM_2 = 61 Nel nostro esempio otterremo:  Risultato_finale = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35) Risultato_finale = (2.619 + 4.270) % 3.395 Risultato_finale = 99 Esegui il seguente calcolo (Risultato_finale - Valore_1) mod Prime1. Dopo la sostituzione delle variabile con i rispettivi valori, otterremo 99 -1 % 35 = 28. Dato che 28 è maggiore di 0, allora 35 è un numero composto. Esegui il seguente calcolo (Risultato_finale - Valore_2) mod Prime2. Dopo la sostituzione delle variabile con i rispettivi valori, otterremo 99 - 2 % 97 = 0. Dato che l'equazione 0 = 0 è sempre vera, significa che 97 è potenzialmente un numero primo. Se il passaggio numero 7 dà come risultato 0, esegui altri test basandoti sulle seguenti indicazioni:  Scegli un valore della variabile "Numero_1" che sia diverso dal precedente e che non sia un numero primo. Scegli un valore della variabile "Numero_1" che sia diverso dal precedente, ma che questa volta sia effettivamente un numero primo. In questo caso, il risultato dei passaggi 6 e 7 dovrebbe essere pari a zero. Scegli due valori diversi per le variabili "Valore_1" e "Valore_2".   Se il risultato del passaggio numero 7 è sempre pari a zero, significa che la probabilità che il "Numero_2" scelto sia primo è altissima. Ricorda che è noto che la serie di calcoli indicati nei passaggi dal numero 1 al numero 7 diano un risultato sbagliato in alcuni casi specifici. Ad esempio, quando la variabile "Numero_1" non rappresenta un numero primo e la variabile "Numero_2" è un fattore del valore assunto dalla variabile "Numero_1". Al contrario, questo metodo funziona perfettamente in tutti gli scenari in cui entrambi i numeri scelti ("Numero_1" e "Numero_2") sono numeri interi primi. Il motivo per cui è necessario ripetere più volte i calcoli descritti nei passaggi dal numero 1 al numero 7 risiede nel fatto che esistono alcuni scenari in cui, anche se il "Numero_1" non è un numero primo così come il "Numero_2", il risultato ottenuto dal passaggio numero 7, relativamente a uno dei due numeri testati o a entrambi, è comunque pari a zero. Si tratta di una circostanza che si verifica molto raramente. Scegliendo un diverso numero composto da assegnare alla variabile "Numero_1", se il "Numero_2" non è un numero primo, il risultato che si ottiene nel passaggio numero 7 sarà subito diverso da zero. Ad eccezione dello scenario in cui l'intero scelto per la variabile "Numero_1" è un fattore del valore scelto per la variabile "Numero_2", questo test darà sempre zero come risultato finale se il numero esaminato è effettivamente un numero primo.
Scegli due numeri. Adesso scegli due valori maggiori di zero e diversi fra loro ma entrambi inferiori al valore assunto dalle variabili "Numero_1" e "Numero_2". A questo punto, calcola l'inverso moltiplicativo del "Numero_1" e del "Numero_2". Crea una tabella binaria per ogni inverso moltiplicativo che abbia come limite il logaritmo in base 2 del modulo. Calcola la seguente espressione (Valore_1 * Numero_2 * IM_1 + Valore_2 * Numero_1 * IM_2) mod (Numero_1 * Numero_2). Controlla che il "Numero_1" non sia un numero primo. Controlla se il Numero_2 è un numero primo. Ripeti i passaggi dal numero 1 al numero 7 per almeno altre due volte.
https://www.wikihow.com/Check-if-a-Number-Is-Prime
Chinese Remainder Theorem Test