Il metodo delle basi di fattorizzazione di Kraitchik

Il metodo di fattorizzazione di Kraitchik cerca due numeri interi distinti $ x \ne y $ tali che $x^2>n $ e $ x^2 \equiv y^2 \pmod{n} $. Una volta trovata questa coppia di interi, calcola il massimo comune divisore tra $ n $ e $ x - y $ (o $ x + y $) per ottenere un fattore non banale di $ n $.

Come funziona?

Ecco la procedura da seguire per fattorizzare il numero $ n $:

Scelgo il minimo valore di $ x $ tale che $ x^2 > n $
Trovo un intero $ y $ tale che $ x^2 \equiv y^2 \pmod{n} $ cioè i due quadrati devono essere congruenti modulo $ n $
Calcola $ x - y $ e $ x + y $
Determina il massimo comune divisore (MCD) tra $ n $ e uno di questi valori: \[ MCD(n, x - y) \quad \text{oppure} \quad MCD(n, x + y) \]
Se il MCD trovato è un fattore non banale di $ n $ (cioè non 1 o $ n $), allora ho ottenuto il primo fattore del numero. Per trovare gli altri basta dividere $ n $ per il fattore appena trovato.
Se il fattore trovato non è primo, continuo a scomporlo ulteriormente fino ad arrivare ai fattori primi.

Questa sequenza di passi permette di trovare una scomposizione di $ n $ in fattori primi.

Nota. E una generalizzazione del metodo di Fermat che anziché risolvere direttamente $ x^2 - y^2 = n $ si basa sull'equivalenza $ x^2 \equiv y^2 \pmod{n} $ ossia $ x^2 - y^2 \equiv 0 \pmod{n} $. Perché $ x^2 - y^2 $ si può riscrivere come $ (x - y)(x + y) $. Se trovo due numeri $ x $ e $ y $ distinti tra loro $ x \ne y $ tali che questa relazione sia valida modulo $ n $, allora $ n $ deve dividere il prodotto $ (x-y)(x+y) $. Questo significa che i fattori primi di $ n $ devono essere contenuti in $ x-y $ oppure in $ x+y $.

Un esempio pratico
Come trovare x e y con le basi di fattorizzazione
Note

Un esempio pratico

Voglio trovare i fattori primi di $ n = 1001 $ usando il metodo di Kraitchik.

Trovo due numeri $ x $ e $ y $ tali che

$$ x^2 \equiv y^2 \pmod{1001} $$

La radice quadrata di $ n=1001 $ è $ 31.6 $

$$ \sqrt{1001} \approx 31.6 $$

Quindi, devo cercare i valori interi a partire da $ x>31 $.

Ad esempio, il quadrato di $ x=71 $ ha come resto $ 36 $ nel modulo 1001 che è un quadrato perfetto ( $ \sqrt{36} = 6 $ ).

\[ 71^2 \equiv 36 \pmod{1001} \]

Come trovare i valori x e y? Per trovare i valori migliori di x e y posso cercare la base di fattorizzazione migliore. Rimando questa spiegazione al paragrafo seguente. Per il momento considero validi i valori x=71 e y=6 perché so già che sono validi. In questo modo posso spiegare meglio come funziona il metodo di Kraitchik.

Poiché $ 36 = 6^2 $ è un quadrato perfetto posso scegliere $ x $ e $ y $ in questo modo:

$$ x = 71 $$

$$ y = 6 $$

Questi valori soddisfano l'equivalenza del metodo

\[ x^2 \equiv y^2 \pmod{1001} \]

A questo punto posso calcolare il massimo comune divisore $ MCD(n, x - y) $:

\[ x - y = 71 - 6 = 65 \]

Trovo $ MCD(65, 1001) $ con l'algoritmo euclideo:

\[ 1001 = 65 \times 15 + 26 \]

\[ 65 = 26 \times 2 + 13 \]

\[ 26 = 13 \times 2 + 0 \]

L'ultimo resto non nullo è 13, quindi $ MCD(65, 1001) = 13 $, che è anche un fattore non banale di 1001.

\[ \frac{1001}{13} = 77 \]

Poiché $ 77 $ è un fattore composto, posso ulteriormente scomporlo.

\[ 77 = 7 \times 11 \]

Quindi la fattorizzazione completa è:

\[ 1001 = 13 \times 7 \times 11 \]

Nota. Anziché usare $ x-y $ avrei potuto usare anche $ x+y $. Ad esempio, con $ x=71 $ e $ y=6 $ $$ x+y= 71+6 = 77 $$ Una volta trovato il valore calcolo il MCD tra $ 77 $ e $ 1001 $. $$ MCD(77, 1001) = 11 $$ Ho così trovato il primo fattore non banale (ossia diverso da 1 e 1001) che in questo caso è $ 11 $. Per trovare gli altri non devo far altro che dividere il numero che voglio fattorizzare $ n=1001 $ per il fattore che ho appena trovato ( $ 11 $ ). $$ \frac{1001}{11} = 91 $$ Poiché che $ 91 $ è un fattore composto, posso ulteriormente scomporlo in fattori primi $ 91 = 7 \times 13 $ Quindi la fattorizzazione completa è: \[ 1001 = 13 \times 7 \times 11 \] Il risultato finale è sempre lo stesso.

Come trovare x e y con le basi di fattorizzazione

Per trovare la base di fattorizzazione posso usare la formula:

\[ b_k = \lfloor \sqrt{n \cdot k} \rfloor + 1, \quad k = 1, 2, 3, \dots \]

Questa formula genera alcuni valori di $ b_k $ da testare con il calcolo del quadrato modulo $ n $:

\[ b_k^2 \mod n \]

Una volta calcolato il quadrato, tenta di scomporre $ b_k^2 \mod n $ in fattori primi.

Se $ b_k^2 \mod n $ è un quadrato perfetto posso applicare il metodo di fattorizzazione di Kraitchik assegnando $ x=b_k $ e $ y= \sqrt{ b_k^2 \mod n } $.

E se non trovo un quadrato perfetto? Se non trovo un quadrato perfetto direttamente tra i valori di $ b_k^2 \mod n $, devo combinare più valori per ottenerlo, usando il metodo della riduzione modulo 2 sui $ B $-vettori.

Genera più valori $ b_k $ usando la formula: \[ b_k = \lfloor \sqrt{n \cdot k} \rfloor + 1 \]
Calcola $ b_k^2 \mod n $.
Scompongo ogni $ b_k^2 \mod n $ in fattori primi.
Seleziono una base $ B = \{p_1, p_2, \dots\} $ contenente solo i primi più piccoli.
Costruisco i $ B $-vettori e li riduco modulo 2. In altre parole, un esponente è pari lo sostituisco con 0, se è dispari con 1
Trovo una combinazione di vettori che si sommano a zero modulo 2. Se li trovo, vuol dire che il prodotto dei numeri corrispondenti è un quadrato perfetto.
Una volta ottenuto un quadrato modulo $ n $, calcola il massimo comune divisore $ MCD(n, b - c) $
Se il risultato è un fattore non banale di $ n $, ho trovato un fattore del numero. Se invece ottengo $ n $ o $ 1 $, ovvero dei fattori banali, devo riprovare con altre combinazioni.

Esempio

Considero il numero $ n = 1001 $ da fattorizzare.

La prima base da tentare con $ k = 1 $ è la seguente:

\[ b_1 = \lfloor \sqrt{1001 \cdot 1} \rfloor + 1 = 32 \]

Poi calcolo il quadrato $ b_1 $ nel modulo $ n=1001 $.

\[ 32^2 \equiv 23 \pmod{1001} \]

La scomposizione in fattori primi di $ 23 $ è sempre $ 23^1 $ perché è un fattore primo. Non è un quadrato perfetto.

Quindi passo a calcolare la base successiva con $ k=2 $

\[ b_2 = \lfloor \sqrt{1001 \cdot 2} \rfloor + 1 = 45 \]

Calcolo il quadrato $ b_1 $ nel modulo $ n=1001 $.

\[ 45^2 \equiv 23 \pmod{1001} \]

Il risultato è ancora $ 23^1 $ che non è un quadrato perfetto.

Calcolo la base successiva con $ k=3 $

\[ b_3 = \lfloor \sqrt{1001 \cdot 3} \rfloor + 1 = 55 \]

Verifico se è un quadrato perfetto

\[ 55^2 \equiv 22 \pmod{1001} \]

La scomposizione in fattori primi di $ 22 $ è $ 2^1 \cdot 11^1 $.

Calcolo la base successiva con $ k=4 $

\[ b_4 = \lfloor \sqrt{1001 \cdot 4} \rfloor + 1 = 64 \]

\[ 64^2 \equiv 92 \pmod{1001} \]

La scomposizione in fattori primi di $ 92 $ è $ 2^2 \cdot 23^1 $.

Calcolo la base successiva con $ k=5 $

\[ b_5 = \lfloor \sqrt{1001 \cdot 5} \rfloor + 1 = 71 \]

\[ 71^2 \equiv 36 \pmod{1001} \]

La scomposizione in fattori primi di $ 36 $ è $ 3^2 \times 2^2 = (3 \times 2)^2 = 6^2 $ ed è un quadrato perfetto.

Quando $ b_i $ è un quadrato perfetto, posso direttamente applicare il metodo di Kraitchik usando $ x=71 $ e $ y = 6 $

Calcolo la differenza $ x-y $

\[ x - y = 71 - 6 = 65 \]

Poi trovo $ MCD(n, x - y) $:

\[ MCD(1001, 65) = 13 \]

Il risultato è un fattore di $ n = 1001 $, Per trovare gli altri posso dividere il numero per il fattore appena trovato.

\[ \frac{1001}{13} = 77 = 7 \times 11 \]

Pertanto, i fattori primi del numero sono:

\[ 1001 = 13 \times 7 \times 11 \]

Esempio 2

Mettiamo che non trovi un quadrato perfetto, cosa posso fare? In questo caso devo costruire i B-vettori di ciascun tentativo.

Ad esempio, voglio fattorizzare il numero $ n =2183 $

b_k	b_k² mod 2183	Fattorizzazione
47	26	2¹ × 13¹
67	123	3¹ × 41¹
81	12	2² × 3¹
94	104	2³ × 13¹
105	110	2¹ × 5¹× 11¹
124	95	5¹× 19¹
133	225	3²× 5²
141	234	2¹× 3²× 13¹
148	74	2¹× 37¹
155	12	2² × 3¹
162	48	2⁴× 3¹
169	182	2¹× 7¹ × 13¹
175	63	3²× 7¹
181	16	2⁴

L'ultimo valore trovato è un quadrato perfetto (b_k=181) perché $ 181^1 \equiv 16 \mod 2183 $. Quindi, potrei usarlo direttamente col metodo di Kraitchik.

Esempio. Una volta trovato il quadrato perfetto, posso assegnare $ x=181 $ e $ y = \sqrt{16}=4 $ e risolvere il problema. Calcolo la differenza: \[ x - y = 181 - 4 = 177 \] Poi trovo $ MCD(n, x - y) $: \[ MCD(2183, 177) = 59 \] Ho trovato il primo fattore di 2183. Per trovare anche l'altro divido 2183 per 59. \[ \frac{2183}{59} = 77 = 7 \times 37 \] Quindi, la fattorizzazione del numero è $ 2183 = 37 \times 59 $

Tuttavia, in questo esempio voglio dimostrare che si può costruire indirettamente un quadrato perfetto anche usando le varie combinazioni degli altri valori b_k.

Questa procedura è molto utile quando non si trova direttamente un quadrato perfetto.

Per prima cosa noto che molti numeri hanno come fattori primi più piccoli 2 e 3. Quindi uso come base di fattorizzazione B(2,3).

Generalmente è sempre preferibile iniziare a usare i fattori più piccoli e ampliare la base man mano che si procede.

Poi calcolo i B-vettori modulo 2 dei valori bk che hanno solo 2 e/o 3 come fattori primi, escludendo gli altri.

b_k	b_k² mod 2183	Fattorizzazione	B-vettore	B-vettore ridotto modulo 2
47	26	2¹ × 13¹
67	123	3¹ × 41¹
81	12	2² × 3¹	(2² , 3¹)	(0 , 1)
94	104	2³ × 13¹
105	110	2¹ × 5¹× 11¹
124	95	5¹× 19¹
133	225	3²× 5²
141	234	2¹× 3²× 13¹
148	74	2¹× 37¹
155	12	2² × 3¹	(2² , 3¹)	(0 , 1)
162	48	2⁴× 3¹	(2⁴ , 3¹)	(0 , 1)
169	182	2¹× 7¹ × 13¹
175	63	3²× 7¹
181	16	2⁴	(2⁴ , 3⁰)	(0 , 0)

A questo punto cerco una combinazione dei vettori che si sommano a (0,0) modulo 2.

Esempio. Un quadrato perfetto come $ b=181 $ ha già un vettore composto solo da zeri (0,0) nella base B(2,3). Tuttavia, in questo caso, voglio usare una combinazione alternativa di b_k. Quindi, non lo considero.

Ad esempio, prendo i B-vettori dei valori 81 e 155 perché la loro somma vettoriale è nulla nel modulo 2.

$$ (0,1)_{81} + (0,1)_{155} \mod 2 = (0+0, 1+1)= (0,0) $$

Il prodotto corrispondente di questi valori (81×155) nel modulo 2 è 1640

$$ 81 \cdot 155 = 12555 \equiv 1640 \pmod{2183} $$

Il quadrato di $ 1640^2 \mod 2183 $ è un quadrato perfetto (144=12²)

$$ 1640^2 \equiv 144 \mod 2183 $$

Nota. Del resto bastava osservare che sia il quadrato 81² e di 155² sono entrambi equivalente a 12 nel modulo 2183. $$ 12 \cdot 12= ( 2^2 \times 3^1 ) \times ( 2^2 \times 3^1 ) = 2^4 \times 3^2 = 144 $$

Pertanto, posso provare a usare $ x=1640 $ e $ y= \sqrt{144} = 12 $ nel metodo di fattorizzazione

\[ MCD(2183, 1640-12) = MCD(2183, 1628) = 37 \]

In questo modo trovo un fattore primo del numero 2183 ossia 37.

Per trovare gli altri, mi basta dividere 2183 per 37

\[ \frac{2183}{37} = 59 \]

Quindi, la fattorizzazione del numero è

$$ 2183 = 37 \times 59 $$

Ho raggiunto lo stesso risultato ma in modo indiretto.

Cosa fare se non riesco a trovare un fattore non banale? In questi casi devo cercare un'altra combinazione di B-vettori ridotti al modulo 2. Eventualmente, se dopo aver analizzato molte combinazioni non trovo una soluzione, posso provare a generare altri numeri b_k. Se necessario, posso anche modificare la base di fattorizzazione B, includendo un altro numero primo.

Note

Alcune note e osservazioni su questo metodo.

Il metodo di Kraitchik fallisce se x ≡ ±y mod n
Può accadere che tutti i fattori primi di $ n $ dividono solo uno dei due termini $ x - y $ oppure $ x + y $. Se questo accade, significa che: \[ x \equiv \pm y \pmod{n} \] In questo caso, il metodo non fornisce alcuna informazione utile per la fattorizzazione, e devo cercare un'altra coppia di valori $ x, y $. Ad esempio, considero il numero composto $ 91 = 7 \times 13 $ e applico il metodo di Kraitchik dovrebbe trovare i suoi fattori primi. La coppia di interi $ x = 46, \quad y = 45 $ soddisfa la relazione \[ 46^2 \equiv 45^2 \pmod{91} \] Tuttavia, in questo caso si verifica il problema perché \[ 46 \equiv -45 \pmod{91} \] Poiché $ x \equiv -y \pmod{91} $, il metodo non mi aiuta a trovare un fattore di 91, perché restituisce solo fattori banali. \[ x - y = 46 - 45 = 1 \] Il MCD(91,1)=1 è un fattore banale di 91.

Come evitare il problema? Nella scelta dei valori $ x $ e $ y $, per trovare un fattore non banale di $ n $ è necessario soddisfare anche la condizione \[ x \not\equiv \pm y \pmod{n} \] In questo modo, almeno un fattore primo di $ n $ divide $ x - y $ e almeno un altro divide $ x + y $. Questa osservazione è fondamentale per applicare correttamente il metodo di Kraitchik.

E così via.