Strettamente legato alla primalità di un numero è il problema
della fattorizzazione di un intero.
Il problema di
fattorizzare un intero è difficile, dal punto di vista computazionale, nel senso che non esistono a tutt'oggi
algoritmi efficienti per risolverlo.
- Fattorizzazione di un numero
intero n attraverso il
crivello di Eratostene: dividere n per tutti i
primi minori o uguali a
 .
-
Fattorizzazione di un numero intero dispari attraverso il metodo di
Fermat: che consiste nel determinare
due numeri,
X e Y tali che :
- X rappresenta la parte intera della radice
quadrata di n maggiorata di 1,
- Y rappresenta la radice
quadrata della differenza tra il quadrato di X e il numero n.
Per
tale procedimento il numero n risulta
Applicazione con
Excel
Applicazione con
Derive
|
