Come riconoscere un numero primo

tramite: O2O
Difficoltà: media
15

Introduzione

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!

25

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.

35

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.

Continua la lettura
45

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.

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Elementari e Medie

Come sapere se un numero è divisibile per tre o per quattro

La matematica è una scienza ben precisa, con le sue regole, dove nulla è lasciato al caso. Fare delle operazioni a mente non sempre è facile, in particolare se ci troviamo di fronte a numeri di una certa entità. Esistono però delle regole che, se...
Elementari e Medie

Come stabilire il tipo di numero decimale dalla sua frazione generatrice

Nella concezione classica, una frazione è un modo per esprimere una quantità basandosi sulla divisione di un oggetto in un certo numero di parti uguali. Ogni frazione corrisponde ad un numero decimale, come ad esempio 2,54, ossia un numero formato da...
Elementari e Medie

Come calcolare la radice cubica di un numero con la virgola

L'estrazione della radice cubica di un numero decimale è un procedimento molto semplice, se possedete le basilari competenze in materia. Il calcolo non è molto differente da quello di un numero naturale, quindi, se siete consapevoli di non essere delle...
Elementari e Medie

Come Verificare Se Un Numero è Divisibile Per Sette

In aritmetica esistono delle regole ben precise, che ci danno la possibilità di comprendere facilmente se un numero è divisibile per un altro. In buona sostanza, si tratta degli algoritmi, grazie ai quali si può verificare la divisibilità di un numero,...
Elementari e Medie

Come Sapere Se Un Numero è Divisibile Per Due

A partire dalle scuole dell'infanzia fino ad arrivare all'università e alla vita quotidiana (compreso il lavoro, le piccole mansioni domestiche, fare la spesa e comprare ciò che ci piace) ci hanno abituato a imparare mnemonicamente quali sono i criteri...
Elementari e Medie

Come convertire un numero decimale in frazione

La matematica è senza dubbio una materia piuttosto complessa e non tutti sono in grado di capirla. Tuttavia ci sono delle operazioni che risultano sicuramente più facili di altre. Nella seguente guida pertanto verrà spiegato, in pochi e semplici passaggi,...
Elementari e Medie

Come distinguere il genere e il numero del nome

Nella grammatica italiana ogni parola viene suddivisa in genere (maschile o femminile) e numero (singolare o plurale). Il nome è una variabile del discorso e può indicare una persona, un animale, una cosa. La maggior parte di essi ha una forma per il...
Elementari e Medie

Come arrotondare un numero decimale ai decimi

In matematica, le regole sono molto importanti, e uno dei principi più importanti, da dover conoscere alla perfezione, perché può essere utile sia in algebra che in geometria, è la semplificazione di un numero decimale in decimi. I numeri sono distinti...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.