Calcolatore di Scomposizione in Fattori Primi
Scomponi qualsiasi numero nei suoi fattori primi (ad esempio, 360 = 2³ × 3² × 5) e verifica se un numero è primo.
1.167 visualizzazioni
Come Funziona
La scomposizione in fattori primi significa scrivere un numero come prodotto dei suoi elementi costitutivi primi — ad esempio 60 = 2² × 3 × 5. Il teorema fondamentale dell'aritmetica garantisce che ogni intero maggiore di 1 abbia esattamente un'unica scomposizione di questo tipo (a parte il riordino dei fattori): esiste un solo modo per scomporre 60 nei suoi fattori primi, indipendentemente dall'ordine in cui provi a dividerlo. Questa unicità è ciò che rende la scomposizione in fattori primi un'operazione significativa e ben definita, non una questione di scelta.
Lo strumento la trova tramite divisione di prova: divide prima per tutti i fattori di 2 possibili (contando quante volte 2 entra esattamente), poi passa ai candidati dispari — 3, 5, 7, 9, 11… — dividendo per ciascuno tante volte quante è possibile, fino alla radice quadrata di ciò che rimane. Esempio svolto per 360: dividi per 2 tre volte (360→180→90→45, quindi 2³), poi 45 è dispari — dividi per 3 due volte (45→15→5, quindi 3²), poi rimane 5, che è esso stesso primo (5¹). Risultato: 360 = 2³ × 3² × 5, e moltiplicando di nuovo — 8 × 9 × 5 — si conferma 360. Se nessun candidato fino a √n divide esattamente il numero rimanente, quel numero rimanente è esso stesso primo e chiude la scomposizione.
Cosa Sapere
I numeri piccoli e medi si scompongono quasi istantaneamente con questo metodo. Ma lo stesso approccio di divisione di prova diventa computazionalmente arduo per numeri molto grandi — centinaia di cifre — perché il numero di candidati da controllare cresce enormemente, e non esiste alcun algoritmo efficiente noto (in tempo polinomiale) per interi generici sui computer classici. Questa asimmetria — moltiplicare due numeri primi grandi è veloce, ma scomporre di nuovo il loro prodotto è lento — non è solo una curiosità: è esattamente il fondamento di sicurezza della crittografia a chiave pubblica RSA: una chiave pubblica è costruita dal prodotto di due enormi numeri primi segreti, e violare la cifratura richiederebbe di scomporre quel prodotto, il che al momento non è fattibile alle dimensioni di chiave in uso.
- L'1 non ha alcuna scomposizione in fattori primi — non è né primo né composto, e la convenzione del "prodotto vuoto" lo tratta come un caso speciale.
- Un numero che sopravvive alla divisione di prova fino alla propria radice quadrata senza che nulla lo divida è, per definizione, primo.
- Oltre alla crittografia, la scomposizione in fattori primi è alla base della semplificazione delle frazioni, del calcolo del massimo comune divisore (MCD) e del minimo comune multiplo (mcm), e della determinazione di quanti divisori ha un numero.
Domande Frequenti
Il numero 1 è un numero primo?
No. I numeri primi hanno esattamente due divisori positivi distinti; l'1 ne ha solo uno (se stesso). Escludere l'1 mantiene unica la scomposizione in fattori primi — altrimenti il teorema fondamentale dell'aritmetica non reggerebbe, perché si potrebbe aggiungere un numero qualsiasi di fattori 1 in più a qualunque scomposizione.
A cosa serve la fattorizzazione?
A semplificare le frazioni, a trovare MCD e mcm di due numeri e — più famosamente — è alla base della crittografia RSA, dove la difficoltà di scomporre il prodotto di due numeri primi enormi è ciò che mantiene sicuro il traffico internet cifrato.
Perché scomporre numeri grandi è considerato "difficile"?
La divisione di prova e i suoi perfezionamenti devono controllare un numero di candidati che cresce molto rapidamente con la dimensione dell'input. Non è noto alcun algoritmo classico efficiente per scomporre rapidamente un numero grande qualsiasi, a differenza della moltiplicazione, che in linea di principio è veloce in entrambe le direzioni — è proprio questo divario che i crittografi sfruttano.
Come si collega la fattorizzazione alla crittografia RSA?
Una chiave pubblica RSA deriva dalla moltiplicazione di due grandi numeri primi scelti casualmente. Chiunque può moltiplicarli per ottenere la chiave pubblica, ma invertire quel passaggio — scomporre di nuovo il prodotto nei suoi due numeri primi — è il muro computazionale che protegge la chiave privata.
Cosa succede se inserisco direttamente un numero primo?
Lo strumento non trova alcun divisore fino alla sua radice quadrata, quindi riporta il numero stesso come unico fattore primo, elevato alla prima potenza — confermando che è primo e non composto.
Strumenti Simili
Segnala un Problema
Calcolatore di Scomposizione in Fattori Primi
Commenti
Ancora nessun commento — scrivi il primo!