Fattorizzazione dei Numeri Primi

La fattorizzazione di un numero n consiste nello scriverlo come il prodotto di altri numeri, ad esempio:

$n = a \times b \times c$.

• Moltiplicare i numeri è un'operazione semplice, ma fattorizzare (trovare i fattori) è un problema difficile.
• Non siamo in grado di fattorizzare la maggior parte dei numeri con più di 1024 bit.

Fattorizzazione in Numeri Primi

La fattorizzazione in numeri primi di un numero $a$ significa scriverlo come il prodotto di potenze di numeri primi:

$a = \prod_{p \in P} p^{a_p} = 2^{a_2} \times 3^{a_3} \times 5^{a_5} \times 7^{a_7} \times 11^{a_{11}} \times \dots$

• $P$: l'insieme dei numeri primi.
• $a_p \in \mathbb{N}$: l'esponente del numero primo $p$.

Esempi

• $91 = 7 \times 13$
• $3600 = 2^4 \times 3^2 \times 5^2$

Numeri relativamente primi & Massimo comun divisore (gcd o mcd)

Due numeri $a$ e $b$ sono relativamente primi se non hanno divisori comuni a parte 1, ovvero se il loro massimo comun divisore (gcd) è uguale a 1.

Ad esempio, 8 e 15 sono relativamente primi perché:

• I fattori di 8 sono: 1, 2, 4, 8
• I fattori di 15 sono: 1, 3, 5, 15