0Pricing
Cryptology Academy · Lezione

Numeri primi e fattorizzazione

Scopra perché i numeri primi sono alla base della crittografia a chiave pubblica.

Numeri primi e fattorizzazione è una lezione Cryptology Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Cryptology Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Cryptology Academy include 4 lezioni in totale.

Benvenuto

I numeri primi sono divisibili solo per 1 e per se stessi. Sono gli atomi della moltiplicazione e il fondamento di RSA, Diffie-Hellman e molti altri sistemi crittografici.

Definizione ed esempi

Numeri primi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Un numero è primo se i suoi unici divisori positivi sono 1 e il numero stesso. Per convenzione, 1 NON è primo.

Teorema fondamentale dell'aritmetica

Ogni intero > 1 può essere scomposto in fattori primi in un unico modo (a meno dell'ordine). 60 = 2² × 3 × 5. È questa unicità a rendere possibile la crittografia basata sulla fattorizzazione.

Divisione per tentativi

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True È sufficiente controllare fino a √n: se non si trova alcun fattore minore di √n, n è primo.

Crivello di Eratostene

Per trovare tutti i numeri primi fino a N: iniziare con un elenco dei numeri da 2 a N. Cancellare i multipli di 2, poi quelli di 3, poi di 5 e così via. I numeri rimanenti sono primi. Ha complessità O(N log log N).

Test di primalità: Miller-Rabin

Per i numeri grandi (2048 bit), la divisione per tentativi è troppo lenta. Miller-Rabin è un test probabilistico: eseguirlo 40 volte porta la probabilità di errore a < 4^(-40).

Fattorizzazione degli interi

Dato n = p × q, trovare p e q è il problema della fattorizzazione degli interi. Se n è di 2048 bit, i migliori algoritmi conosciuti richiedono 2^112 operazioni, attualmente non realizzabili.

Perché RSA utilizza due numeri primi grandi

Il modulo RSA è n = p × q. Conoscere n ma non p e q rende difficile calcolare la chiave privata. La sicurezza dipende interamente dalla difficoltà di fattorizzare n.

Generazione di numeri primi grandi

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Procedura: generare un numero dispari casuale, verificarlo con Miller-Rabin e ripetere finché non è primo.

Numeri primi sicuri e forti

Un numero primo sicuro è un primo p = 2q+1 in cui anche q è primo. I numeri primi sicuri resistono a determinati attacchi contro DH. RSA talvolta utilizza numeri primi forti per prevenire l'attacco di Pollard p-1.

Distanze tra primi e infinità

Euclide dimostrò nel 300 a.C. che esistono infiniti numeri primi. La congettura dei primi gemelli (esistono infiniti primi p e p+2) non è ancora stata dimostrata. Non esauriremo mai i numeri primi per la crittografia.

Verifica rapida

Perché RSA utilizza numeri primi grandi?

Riepilogo

Ora comprende i numeri primi e la fattorizzazione. Successivamente applicheremo la funzione totiente di Eulero e il MCD, gli ultimi strumenti matematici necessari prima di RSA.

Domande Frequenti

La lezione «Numeri primi e fattorizzazione» è gratuita?

Sì — il testo completo di «Numeri primi e fattorizzazione» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Cryptology Academy, passa a CoddyKit PRO. Il corso Cryptology Academy include 4 lezioni in totale.

Cosa imparerò in «Numeri primi e fattorizzazione»?

Scopra perché i numeri primi sono alla base della crittografia a chiave pubblica. Eserciti Cryptology Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Cryptology Academy?

Non è richiesta alcuna esperienza precedente. Cryptology Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Numeri primi e fattorizzazione»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Cryptology Academy?

Sì. Ogni lezione Cryptology Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Fondamenti del binario e dell'esadecimale
  2. Fondamenti dell'aritmetica modulare
  3. Numeri primi e fattorizzazione
  4. MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri
← Torna a Cryptology Academy