Il metodo di fattorizzazione di Dixon - Dixon's factorization method

Nella teoria dei numeri , il metodo di fattorizzazione di Dixon (anche il metodo dei quadrati casuali di Dixon o l'algoritmo di Dixon ) è un algoritmo di fattorizzazione di interi di uso generale ; è il metodo di base dei fattori prototipico . A differenza di altri metodi di base dei fattori, il suo limite di runtime viene fornito con una dimostrazione rigorosa che non si basa su congetture sulle proprietà di levigatezza dei valori presi dal polinomio.

L'algoritmo è stato progettato da John D. Dixon , un matematico alla Carleton University , ed è stato pubblicato nel 1981.

Idea base

Il metodo di Dixon si basa sul trovare una congruenza dei quadrati modulo l'intero N che si intende fattorizzare. Il metodo di fattorizzazione di Fermat trova una tale congruenza selezionando valori x casuali o pseudocasuali e sperando che l'intero x ² mod N sia un quadrato perfetto (negli interi):

{\ displaystyle x ^ {2} \ equiv y ^ {2} \ quad ({\ hbox {mod}} N), \ qquad x \ not \ equiv \ pm y \ quad ({\ hbox {mod}} N) .}

Ad esempio, se N = 84923 , (partendo da 292, il primo numero maggiore di √ N e contando) il 505 ² mod 84923 è 256, il quadrato di 16. Quindi (505 - 16) (505 + 16) = 0 mod 84923 . Il calcolo del massimo comun divisore di 505-16 e N utilizzando l'algoritmo di Euclide dà 163, che è un fattore di N .

In pratica, la selezione casuale di x valori vorrà un tempo impraticabile a lungo per trovare una congruenza di piazze, dal momento che ci sono solo √ N piazze meno di N .

Il metodo di Dixon sostituisce la condizione "è il quadrato di un intero" con quella molto più debole "ha solo piccoli fattori primi"; ad esempio, ci sono 292 quadrati più piccoli di 84923; 662 numeri inferiori a 84923 i cui fattori primi sono solo 2,3,5 o 7; e 4767 i cui fattori primi sono tutti inferiori a 30 (tali numeri sono chiamati B-smooth rispetto a qualche B legato ).

Se ci sono molti numeri i cui quadrati possono essere fattorizzati come per un insieme fisso di piccoli primi, l'algebra lineare modulo 2 sulla matrice darà un sottoinsieme dei cui quadrati si combinano a un prodotto di piccoli numeri primi a una potenza pari - cioè, un sottoinsieme dei cui quadrati si moltiplicano per il quadrato di un numero (si spera diverso) mod N. ${\ displaystyle a_ {1} \ ldots a_ {n}}$ ${\ displaystyle a_ {i} ^ {2} \ mod N = \ prod _ {j = 1} ^ {m} b_ {j} ^ {e_ {ij}}}$ ${\ displaystyle b_ {1} \ ldots b_ {m}}$ ${\ displaystyle e_ {ij}}$ ${\ displaystyle a_ {i}}$ ${\ displaystyle a_ {i}}$

Metodo

Supponiamo che il numero composto N venga scomposto. Legato B è scelto, e la base di fattore viene identificato (che è chiamato P ), l'insieme di tutti i primi inferiore o uguale a B . Successivamente, si cercano interi positivi z tali che z ² mod N sia B- liscio. Quindi si può scrivere, per opportuni esponenti a _i ,

{\ displaystyle z ^ {2} {\ text {mod}} N = \ prod _ {p_ {i} \ in P} p_ {i} ^ {a_ {i}}}

Quando un numero sufficiente di queste relazioni è stato generato (è generalmente sufficiente che il numero di relazioni sia di poco superiore alla dimensione di P ), si possono utilizzare i metodi dell'algebra lineare (ad esempio, eliminazione gaussiana ) per moltiplicare insieme queste varie relazioni in modo tale che gli esponenti dei numeri primi a destra siano tutti pari:

{\ displaystyle {z_ {1} ^ {2} z_ {2} ^ {2} \ cdots z_ {k} ^ {2} \ equiv \ prod _ {p_ {i} \ in P} p_ {i} ^ { a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k}} \ {\ pmod {N}} \ quad ({\ text {where}} a_ {i, 1} + a_ {i, 2} + \ cdots + a_ {i, k} \ equiv 0 {\ pmod {2}})}}

Ciò fornisce una congruenza dei quadrati della forma a ² ≡ b ² (mod N ), che può essere trasformata in una fattorizzazione di N , N = mcd ( a + b , N ) × ( N / mcd ( a + b , N )). Questa fattorizzazione potrebbe risultare banale (es. N = N × 1 ), cosa che può avvenire solo se a ≡ ± b (mod N ), nel qual caso si dovrà fare un altro tentativo con una diversa combinazione di relazioni; ma una coppia non banale di fattori di N può essere raggiunta e l'algoritmo terminerà.

Pseudocodice

input: positive integer  ${\textstyle N}$ 
output: non-trivial factor of  ${\textstyle N}$ 

Choose bound  ${\textstyle B}$ 
Let  ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$  be all primes  ${\textstyle \leq B}$ 

repeat
    for  ${\textstyle i=1}$  to  ${\textstyle k+1}$  do
        Choose  ${\textstyle 0<z_{i}<N}$  such that  ${\textstyle z_{i}^{2}{\text{ mod }}N}$  is  ${\textstyle B}$ -smooth
        Let  ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$  such that  ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$ 
    end for

    Find non-empty  ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$  such that  ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$ 
    Let  ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$ 
         ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$ 
while  ${\textstyle x\equiv \pm y{\pmod {N}}}$  

return  ${\textstyle \gcd(x+y,N)}$

Esempio

Questo esempio proverà a fattorizzare N = 84923 utilizzando il limite B = 7. La base del fattore è quindi P = {2, 3, 5, 7}. È possibile cercare interi compresi tra e N i cui quadrati mod N sono B- regolari . Supponiamo che due dei numeri trovati siano 513 e 537: ${\ displaystyle \ left \ lceil {\ sqrt {84923}} \ right \ rceil = 292}$

{\ displaystyle 513 ^ {2} \ mod 84923 = 8400 = 2 ^ {4} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}

{\ displaystyle 537 ^ {2} \ mod 84923 = 33600 = 2 ^ {6} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7}

Così

{\ displaystyle (513 \ cdot 537) ^ {2} \ mod 84923 = 2 ^ {10} \ cdot 3 ^ {2} \ cdot 5 ^ {4} \ cdot 7 ^ {2} \ mod 84923}

Poi

${\ displaystyle {\ begin {align} & {} (513 \ cdot 537) ^ {2} \ mod 84923 \\ & = (275481) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3 + 20712 ) ^ {2} \ mod 84923 \\ & = (84923 \ cdot 3) ^ {2} +2 \ cdot (84923 \ cdot 3 \ cdot 20712) + 20712 ^ {2} \ mod 84923 \\ & = 0+ 0 + 20712 ^ {2} \ mod 84923 \ end {align}}}$

Questo è, ${\ displaystyle 20712 ^ {2} \ mod 84923 = (2 ^ {5} \ cdot 3 \ cdot 5 ^ {2} \ cdot 7) ^ {2} \ mod 84923 = 16800 ^ {2} \ mod 84923.}$

La scomposizione in fattori risultante è 84923 = mcd (20712 - 16800, 84923) × mcd (20712 + 16800, 84923) = 163 × 521.

Ottimizzazioni

Il setaccio quadratico è un'ottimizzazione del metodo di Dixon. Seleziona i valori di x vicini alla radice quadrata di N in modo tale che x ² modulo N sia piccolo, aumentando così notevolmente la possibilità di ottenere un numero regolare.

Altri modi per ottimizzare il metodo di Dixon includono l'utilizzo di un algoritmo migliore per risolvere l'equazione della matrice, sfruttando la scarsità della matrice: un numero z non può avere più di fattori, quindi ogni riga della matrice è quasi tutti zeri. In pratica viene spesso utilizzato l'algoritmo di blocco Lanczos . Inoltre, la dimensione della base fattoriale deve essere scelta con attenzione: se è troppo piccola, sarà difficile trovare numeri che la fattorizzino completamente, e se è troppo grande, dovranno essere raccolte più relazioni. ${\ displaystyle \ log _ {2} z}$

Un'analisi più sofisticata, utilizzando l'approssimazione secondo cui un numero ha tutti i suoi fattori primi inferiori rispetto alla probabilità circa (un'approssimazione alla funzione di Dickman-de Bruijn ), indica che scegliere una base di fattori troppo piccola è molto peggio che troppo grande, e che la dimensione di base del fattore ideale è una certa potenza di . ${\ displaystyle N ^ {1 / a}}$ ${\ displaystyle a ^ {- a}}$ ${\ displaystyle \ exp \ left ({\ sqrt {\ log N \ log \ log N}} \ right)}$