Metodo delle frazioni continue per la fattorizzazione

Il metodo delle frazioni continue per la fattorizzazione sfrutta le frazioni continue dello sviluppo di \( \sqrt{n} \) per trovare numeri che soddisfano una relazione quadratica $ b^2≡c^2 \mod  n $ e, successivamente, usa il MCD per determinare un divisore di \( n \) $$ MCD(b \pm c,n) $$.

In altre parole è un trucchetto furbo per sfruttare la periodicità delle frazioni continue della radice quadrata di $ n $ e trovare un bel $ b^2 \equiv c^2 \mod  n $ che poi, col massimo comune divisore, individua uno dei fattori di n.

Come funziona il metodo?

I principali passaggi del metodo delle frazioni continue sono i seguenti:

1. Calcolo la parte intera del numero da fattorizzare $$ a_0 = \lfloor \sqrt{n}  \rfloor $$
2. Assegno i valori iniziali ai convergenti: $$  u_0 = 1 ,  u_1 = a_0   , v_0 = 0  ,  v_1 = 1 $$
3. Trovo i convergenti \( C_k = \frac{u_k}{v_k} \)
4. Riduco i numeratori $ u_k $ al modulo \( n \) \[ u_k' = u_k \mod n \]
5. Calcolo il minimo residuo assoluto del quadrato di $ u_k $ \[ a_k = MRA(u_k^2, n) \]
6. Seleziono una base di fattorizzazione osservando i numeri primi piccoli che compaiono frequentemente
7. Costruisco una relazione del tipo \( b^2 \equiv c^2 \mod n \) con i numeri ottenuti
8. Utilizzo il massimo comune divisore \( MCD(b - c, n) \) per trovare un divisore di \( n \).

Nota. L'idea principale è trovare un valore di \( b \) tale che: \[ b^2 \equiv c^2 \mod n \] Questa relazione permette di trovare un divisore di \( n \) calcolando: \[ MCD(b - c, n) \] Se questo MCD è un numero maggiore di 1 e minore di \( n \), allora ho trovato un fattore non banale di \( n \), ottenendo così la fattorizzazione.

Questo metodo funziona perché i numeratori delle frazioni continue di \( \sqrt{n} \) tendono ad avere piccoli residui quadratici modulo \( n \).

Questo facilita la ricerca di una relazione del tipo \( b^2 \equiv c^2 \mod n \), che è la chiave per la fattorizzazione.

Nota. È particolarmente efficace per numeri semi-primi (prodotti di due primi di grandezza simile). Funziona bene quando \( n \) è grande ma non troppo grande (centinaia o poche migliaia di cifre).

È una delle idee fondamentali della teoria dei numeri computazionale.

Un esempio pratico

Provo a fattorizzare il numero intero $ n=2041 $

Calcolo la radice quadrata del numero e assegno la parte intera a $ a_0 $.

$$ a_0 = \lfloor \sqrt{n}  \rfloor = \lfloor \sqrt{2041} \rfloor = \lfloor 45.17 \rfloor = 45 $$

Sviluppo la frazione continua di \( \sqrt{2041} \) usando le seguenti equazioni ricorsive per ogni passo successivo \( k = 1, 2, 3, ... \):

\[ a_k = \lfloor \frac{a_0 + m_k}{d_k} \rfloor \]

Dove $ m_0 = 0 $ e $ d_0 = 1 $ poi i successivi valori vanno calcolati usando queste formule:

\[ m_k = d_{k-1} a_{k-1} - m_{k-1} \]

\[ d_k = \frac{n - m_k^2}{d_{k-1}} \]

Ecco lo sviuppo della frazione continua per i primi valori.

k	m_k	d_k	a_k
0	0	1	45
1	45	16	5
2	35	51	1
3	16	35	1
4	19	48	1
4	29	25	2
4	21	64	1

Spiegazione. Per $ k = 1 $ si ha: \[ m_1 = d_0 a_0 - m_0 = 1 \cdot 45 - 0 = 45 \] \[ d_1 = \frac{n - m_1^2}{d_0}  = \frac{2041 - 45^2}{1} = 2041 - 2025 = 16 \] \[ a_1 = \lfloor \frac{a_0 + m_1}{d_1} \rfloor = \lfloor \frac{45 + 45}{16} \rfloor =  \lfloor \frac{90}{16} \rfloor = 5  \] Per $ k = 2 $ si ha: \[ m_2 = d_1 a_1 - m_1 = 16 \cdot 5 - 45 = 80-45 = 35 \] \[ d_2 = \frac{n - m_2^2}{d_1}  = \frac{2041 - 35^2}{16} = \frac{2041 - 1225}{16} = \frac{816}{16} = 51 \] \[ a_2 = \lfloor \frac{a_0 + m_2}{d_2} \rfloor = \lfloor \frac{45 + 35}{51} \rfloor =  \lfloor \frac{80}{51} \rfloor = 1  \] E via dicendo.

Quindi, i primi valori della frazione continua sono:

$$ a_k = [ 45, 5, 1, 1, 1, 2, 1,  ... ] $$

Assegno i valori iniziali ai convergenti:

$$  u_0 = 1 $$

$$  u_1 = a_0 = 54 $$

$$ v_0 = 0 $$

$$  v_1 = 1 $$

Poi calcolo i valori successivi tramite queste formule ricorsive.

\[ u_k = a_k u_{k-1} + u_{k-2} \]

\[ v_k = a_k v_{k-1} + v_{k-2} \]

Ecco i primi risultati

\[
\begin{array}{c|ccccc}
k & 1 & 2 & 3 & 4 & 5 \\
\hline
u_k & 45 & 226 & 271 & 497 & 768 \\
v_k &  1 & 5 & 6 & 11 & 17 \\
\end{array}
\]

In questo modo posso trovare i convergenti $ C_k $ e i successivi valori di \( a_k \) con il metodo delle frazioni continue.

$$ C_k = \frac{u_k}{v_k} $$

Calcolo il resto dei numeratori divisi per $ n=2041 $ ossia $ u_k' = u_k \mod n $

\[ u_k' = u_k \mod 2041 \]

Calcolo il minimo residuo assoluto (MRA) del quadrato di $ u_k $

\[ M_k = MRA(u_k^2, 2041) \]

Ecco i risultati ottenuti

\[
\begin{array}{c|ccccc}
k & 1 & 2 & 3 & 4 & 5 \\
\hline
u_k' & 45 & 226 & 271 & 497 & -768 \\
M_k & -16 & 51 & -35 & 48 & -25 \\
\end{array}
\]

L'obiettivo è trovare un valore di $ M_k $ che sia un quadrato perfetto rispetto a una base di fattorizzazione.

Ad esempio, in questo caso ce ne sono due:

$$ M_1 = -16 = -1 \cdot 2^4  $$

$$ M_5 = -25 = -1 \cdot 5^2 $$

Una volta trovati, posso usarli per definire una base di fattorizzazione

$$ B = \{ 2, 5 \} $$

Quindi ragionevole scegliere \( B = \{2,5\} \) e prendere come B-numeri modulo \( n \) gli \( a_k \) per \( k = 1,5 \), che sono già quadrati.

$$ u'_1 = 45 $$

$$ u'_5 = -768 $$

Da questo punto in poi posso procedere con la costruzione della congruenza quadratica e la fattorizzazione.

$$ b^2 \equiv c^2 \pmod{n} $$

Dove $ b $ è il prodotto dei rispettivi due valori $ u'_k $ ossia $ u'_1 \cdot u'_5 $ nel modulo $ n=2041 $

$$ b= u'_1 \cdot u'_5  \mod 2041 = 45 \cdot (-768) \equiv 1904 \mod 2041  $$

mentre $ c $ è il prodotto nel modulo $ n=2041 $ delle rispettive basi dei quadrati perfetti $ M_1 = -16 =  (2^2)^2 $ e $ M_5 = -25 = -1 \cdot- 5^2 $ ossia $ 2^2 $ e $ 5 $.

$$ c = 2^2 \cdot 5 \equiv 20 \pmod{2041} $$

A questo punto ho trovato i valori $ b=1904 $ e $ c=20 $ e posso usarli nel metodo della congruenza quadratica $ b^2 \equiv c^2 \mod n $

$$ 1904^2 \equiv 20^2 \mod 2041 $$

Quindi, calcolo il massimo comune divisore \( MCD(b - c, n) \) per trovare un divisore di \( n \).

$$ MCD(1904 - 20, 2041) = MCD(1884,2041) = 157  $$

Nota. Se il risultato fosse stato un fattore banale (es. 1 o n=2041 stesso), avrei potuto provare con la somma \( MCD(b + c, n) \). $$ MCD(1904 + 20, 2041) = MCD(1924,2041) = 13  $$

Ho trovato uno dei fattori primi (157) del numero 2041.

Per trovare gli altri, divido 2041 per 157.

$$ \frac{2041}{157} = 13 $$

Pertanto, la fattorizzazione del numero 2041 è

$$ 2041 = 13 \times 157 $$

I fattori primi del numero sono 13 e 157.

Svantaggi del metodo

Il metodo delle frazioni continue per la fattorizzazione ha diversi punti deboli, per questa ragione oggi non è usato nei metodi più avanzati di fattorizzazione.

• Lentezza per numeri grandi
  Funziona decentemente per numeri con 30-40 cifre ma con numeri più grandi diventa un calvario. Il problema è che bisogna calcolare molte frazioni continue prima di trovare un \( b^2 \equiv c^2 \mod n \), e questo si porta dietro una complessità quadratica nel numero di cifre.
• Non garantisce sempre un fattore utile
  Anche se trovo una relazione quadratica, non è detto che trovo un divisore utile. Se il massimo comune divisore restituisce 1 o \( n \), ho solo perso tempo. Quindi, serve provare più convergenti, il che significa fare più calcoli e altra fatica.
• Funziona meglio su numeri con fattori di grandezza simile
  Se il numero \( n \) da fattorizzare è il prodotto di due numeri primi molto sbilanciati (tipo uno piccolo e uno molto grande), le frazioni continue spesso falliscono. I numeratori dei convergenti diventano troppo grandi troppo in fretta e il metodo si complica.
• La fase di pre-processing è molto laboriosa e luna
  Prima devo costruire la frazione continua. Poi devo trovare i convergenti. Poi devo trovare i minimi residui quadrati. Poi devo cercare una base di fattorizzazione buona. E solo dopo tutto questo lavoro, devo sperare di trovare la relazione quadratica giusta.

In conclusione, oggi questo metodo di fattorizzazione è obsoleto rispetto ad altri metodi moderni e si presta poco a lavorare sui supercomputer perché la procedura è troppo sequenziale e poco scalabile.

Nota. Altri metodi moderni come il Quadratic Sieve e il GNFS (General Number Field Sieve) sono più scalabili perché sfruttano la parallelizzazione e l'ottimizzazione su larga scala. In particolar modo il Quadratic Sierve è più scalabile e adatto per numeri medi mentre il GNFS è imbattibile per numeri giganteschi.

Note

Alcune note aggiuntive sul metodo di fattorizzazione delle frazioni continue

• Chi ha inventato questo metodo?
  Il metodo è basato su idee di Legendre e Gauss, ma è stato formalizzato nel contesto della fattorizzazione moderna da D. H. Lehmer e altri matematici. È simile al metodo di Dixon e alla quadratic sieve che sono metodi avanzati di fattorizzazione.
• Il metodo delle frazioni continue è obsoleto
  Oggi il metodo delle frazioni continue non è più usato, perché esistono algoritmi di calcolo più efficienti. Tuttavia, èuna base teorica necessaria per studiare metodi di fattorizzazione più avanzati come la Quadratic Sieve.

E così via.