Sită quadratică

Sita pătratică este un algoritm de factorizare creat de Carl Pomerance . Acest algoritm este deosebit de renumit deoarece în 1994 a luat în calcul numărul RSA-129 , care este format din 129 de zece cifre.

Algoritm

Algoritmul constă din 8 pași:

Numărul natural impar este dat ca intrare $n>1$ ${\ displaystyle n> 1}$ $n> 1$ .
Tu alegi un natural $k>0$ ${\ displaystyle k> 0}$ $k> 0$ .
Toate primele sunt examinate $p\leq k$ ${\ displaystyle p \ leq k}$ ${\ displaystyle p \ leq k}$ și toate primele ciudate sunt eliminate astfel încât $\left({\frac {n}{p}}\right)\neq 1$ ${\ displaystyle \ left ({\ frac {n} {p}} \ right) \ neq 1}$ ${\ displaystyle \ left ({\ frac {n} {p}} \ right) \ neq 1}$ , unde cu $\left({\frac {n}{p}}\right)$ ${\ displaystyle \ left ({\ frac {n} {p}} \ right)}$ ${\ displaystyle \ left ({\ frac {n} {p}} \ right)}$ ne referim la simbolul lui Legendre și astfel obținem baza factorilor $B=\{p_{1},p_{2},\dots ,p_{t}\}$ ${\ displaystyle B = \ {p_ {1}, p_ {2}, \ dots, p_ {t} \}}$ ${\ displaystyle B = \ {p_ {1}, p_ {2}, \ dots, p_ {t} \}}$ .
Prin realizarea de reclame $r$ ${\ displaystyle r}$ $r$ valori întregi ulterioare $\lfloor {\sqrt {n}}\rfloor$ ${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$ ${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$ , se găsesc cel puțin $t+1$ ${\ displaystyle t + 1}$ ${\ displaystyle t + 1}$ valori $y=r^{2}-n$ ${\ displaystyle y = r ^ {2} -n}$ ${\ displaystyle y = r ^ {2} -n}$ care au toți factorii lor primari în $B.$ ${\ displaystyle B}$ $B.$ .
Pentru fiecare dintre valori $y_{1},y_{2},\dots ,y_{t+1}$ ${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {t + 1}}$ ${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {t + 1}}$ calculăm vectorul în $(\mathbb {Z} /2\mathbb {Z} )^{t}:v_{2}(y_{i})=(e_{1},e_{2},\dots ,e_{t})$ ${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {t}: v_ {2} (y_ {i}) = (e_ {1}, e_ {2}, \ dots, e_ {t })}$ ${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {t}: v_ {2} (y_ {i}) = (e_ {1}, e_ {2}, \ dots, e_ {t })}$ unde este $e_{i}$ ${\ displaystyle e_ {i}}$ $e_ {i}$ este reducerea modulului $2$ ${\ displaystyle 2}$ $2$ a exponentului de $p_{i}$ ${\ displaystyle p_ {i}}$ $p_ {i}$ în factorizarea $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ .
Unii dintre vectori sunt determinați cu metoda de eliminare gaussiană $v_{2}(y_{i})$ ${\ displaystyle v_ {2} (y_ {i})}$ ${\ displaystyle v_ {2} (y_ {i})}$ care dau suma egală cu vectorul nul.
Se ridică $X$ ${\ displaystyle x}$ $X$ egal cu produsul de $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ corespunde $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ găsit în pasul 6) și apare $y$ ${\ displaystyle y}$ $y$ egal cu produsul puterilor de $p_{1},p_{2},\dots ,p_{t}$ ${\ displaystyle p_ {1}, p_ {2}, \ dots, p_ {t}}$ ${\ displaystyle p_ {1}, p_ {2}, \ dots, p_ {t}}$ cu exponenți egali cu suma pe jumătate a exponenților factorizării aceluiași $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ .
Se calculează $d=\mathrm {mcd} (x-y,n)$ ${\ displaystyle d = \ mathrm {mcd} (xy, n)}$ ${\ displaystyle d = \ mathrm {mcd} (x-y, n)}$ si daca $1<d<n$ ${\ displaystyle 1 <d <n}$ ${\ displaystyle 1 <d <n}$ asa de $d$ ${\ displaystyle d}$ $d$ este divizorul non-banal al $n$ ${\ displaystyle n}$ $n$ , altfel reveniți la pasul 2) cu o alegere de $k$ ${\ displaystyle k}$ $k$ mai mare.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică