Cos'è numero primo?

Numero Primo

Un numero primo è un https://it.wikiwhat.page/kavramlar/numero%20naturale maggiore di 1 che ha solo due divisori positivi distinti: 1 e se stesso.

Definizione Formale: Un numero intero p > 1 è primo se e solo se i suoi unici divisori positivi sono 1 e p.

Esempi:

Proprietà Importanti:

Ogni https://it.wikiwhat.page/kavramlar/numero%20intero maggiore di 1 può essere scritto come prodotto di numeri primi (Teorema fondamentale dell'aritmetica). Questa scomposizione è unica, a meno dell'ordine dei fattori.
Esistono infiniti numeri primi. Questa dimostrazione, spesso attribuita a https://it.wikiwhat.page/kavramlar/Euclide, è una delle dimostrazioni più eleganti in matematica.
Il numero 1 non è considerato un numero primo per preservare l'unicità della fattorizzazione prima.
La distribuzione dei numeri primi tra i numeri naturali è irregolare, ma segue tendenze statistiche ben definite descritte dal https://it.wikiwhat.page/kavramlar/Teorema%20dei%20numeri%20primi.

Utilizzo:

I numeri primi sono fondamentali in https://it.wikiwhat.page/kavramlar/crittografia, in particolare nella crittografia a chiave pubblica, come RSA. La difficoltà di fattorizzare numeri grandi nel prodotto dei loro fattori primi è sfruttata per garantire la sicurezza delle comunicazioni. Sono anche utilizzati in https://it.wikiwhat.page/kavramlar/informatica e https://it.wikiwhat.page/kavramlar/matematica pura.

Test di Primalità:

Determinare se un numero è primo è un problema computazionalmente impegnativo. Esistono diversi algoritmi per testare la primalità, tra cui:

Divisione per tentativi: Un metodo semplice ma inefficiente che consiste nel dividere il numero per tutti i numeri primi minori o uguali alla sua radice quadrata.
Test di Miller-Rabin: Un test probabilistico efficiente.
AKS primality test: Il primo algoritmo deterministico di primalità in tempo polinomiale.