Come riconoscere un numero primo

La matematica è da sempre considerata una tra le materie tanto amate ed odiate dagli studenti. Tra le sue difficoltà, vi è senza dubbio quella di riconoscere un numero primo, cioè quel numero che è divisibile solo per uno e per se stesso. Riconoscerli è semplice solo se si tratta di cifre basse per cui non sono richiesti troppi calcoli. Molto spesso, a forza di utilizzarli, per abitudine, alcuni sono individuabili fin da subito, mentre per scoprire gli altri, occorre fare qualche calcolo in più. La teoria dei numeri primi è alla base della sezione della matematica che studia i numeri interi. In questa guida, verranno forniti alcuni consigli su come riconoscere un numero primo che fa parte di una categoria molto utilizzata per la crittografia delle password. Iniziamo!

Innanzitutto, il più noto e semplice test di primalità è quello di "divisioni per tentativi", ovvero si applica direttamente la definizione provando a dividere il numero in questione per tutti i numeri minori. Se nessuno soddisfa il risultato, fa parte dunque di questa categoria. Un ulteriore miglioramento per raffinare questo metodo, consiste nell'utilizzare solo quei numeri che risultano essere minori della radice quadrata della cifra in questione. Tuttavia, questo procedimento è abbastanza lungo e prevede calcoli notevoli prima di giungere al risultato.

Un altro procedimento per scoprire se si tratta di un numero primo riguarda il "Piccolo Teorema di Fermat (PTF)", dovuto a Pierre de Fermat e dimostrato successivamente da Eulero. Risulta essere un metodo antichissimo ma ancora valido, utilizzato già nel XVII secolo, che conserva ancora il suo fascino. È quasi sempre tirato in ballo, anche nei nuovi metodi di primalità come AKS. Se a^n mod n = a mod n allora n è primo. Ad esempio, se il resto 2^17 MOD 17 è 2, allora 17 è probabilmente primo. Un terzo metodo è quello che riguarda il test probabilistico di Miller-Rabin che può essere utilizzato per stabilire se un numero n è primo o composto, cioè divisibile attraverso cifre minori.

In particolare, se il test identifica n come composto, n è certamente composto; se al contrario il test lo identifica come primo, n è tale con probabilità maggiore di 1/2. Successivamente, effettuando k test fra loro indipendenti, se n viene indicato anche una sola volta come composto, n è composto con certezza. Se invece il numero viene sempre indicato come primo, n è primo con un margine di errore inferiore a 1/2 elevato a k. In conclusione, ci si può esercitare svariate volte, cercando il metodo migliore con cui si ha più dimestichezza.

• Numeri primi.
• Come riconoscere un numero primo.
• Come riconoscere i numeri primi.
• Riconoscere un numero primo, criteri di divisibilità.