Metoda formei pătratice Shanks

Metoda formei pătratice Shanks este o metodă de factorizare a numerelor întregi bazată pe utilizarea formelor pătratice , dezvoltată de Daniel Shanks [1] în 1975 , ca o dezvoltare a metodei de factorizare a lui Fermat .

Pentru computerele pe 32 de biți, algoritmii bazați pe această metodă sunt liderii incontestabil printre algoritmii de factorizare pentru numere de la până și probabil vor rămâne așa. [2] Acest algoritm poate împărți aproape orice număr compus de 18 cifre în mai puțin de o milisecundă. Algoritmul este extrem de simplu, frumos și eficient. În plus, metodele bazate pe acest algoritm sunt folosite ca auxiliare în extinderea divizorilor numerelor mari, cum ar fi numerele Fermat . $10^{{10}}$ $10^{18}$

Istorie

Un alt nume pentru algoritm este SQUFOF ( un acronim pentru engleză este SQUare FORm Factorization), ceea ce înseamnă factorizare de formă pătratică . Această abordare a avut un succes destul de mare de-a lungul anilor și, ca urmare, destul de multe modificări și implementări diferite pot fi găsite pe acest subiect în literatură. [3] Majoritatea metodelor sunt complexe și confuze, mai ales atunci când metoda trebuie implementată pe un computer. Ca urmare, multe variante de algoritmi nu sunt potrivite pentru implementare. Cu toate acestea, în 1975, Daniel Shanks a propus să creeze un algoritm care poate fi implementat și utilizat nu numai pe un computer, ci și pe un simplu telefon mobil.

Deși Shanks a descris alți algoritmi pentru factorizarea întregilor, el nu a publicat nimic pe SQUFOF. A ținut prelegeri pe această temă și a explicat esența de bază a metodei sale unui cerc destul de restrâns de oameni. Unele lucrări ale altor oameni de știință [4] [3] [5] [6] au discutat despre algoritm, dar niciuna nu conține o analiză detaliată. De asemenea, este interesant că în metoda sa, Shanks face un număr destul de mare de presupuneri [7] , care, din păcate, au rămas fără dovezi. În [8] , sunt prezentate rezultatele unor experimente, care indică faptul că există multe ipoteze. În cele din urmă, pe baza acestor ipoteze simplificatoare, Shanks a reușit să creeze SQUFOF.

Definiții auxiliare

Pentru a înțelege modul în care este implementat acest algoritm, este necesar să se cunoască informațiile minime despre obiectele matematice utilizate în această metodă, și anume formele pătratice . O formă binară pătratică este un polinom în două variabile și : $X$ $y$

f(x,y)=ax^{2}+bxy+cy^{2}={\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}a&b\\0&c\end{ pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}.

Metoda Shanks folosește doar forme nedefinite . Prin noi înțelegem discriminantul unei forme pătratice. Vom spune că forma pătratică reprezintă un întreg dacă există numere întregi astfel încât egalitatea este adevărată: . Dacă egalitatea este adevărată , atunci reprezentarea se numește primitivă . $\Delta$ $f$ $m\in \mathbb {Z}$ $x_{0},y_{0}$ ${\displaystyle f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2))$ $\gcd(x_{0},y_{0})=1$

Pentru orice formă pătratică nedefinită , operatorul de reducere poate fi definit ca: $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$

\rho {\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}c,&r(-b,c),&{\frac {r(-b,c )^{2}-\Delta }{4c}}\end{pmatrix}}

, unde este definit ca un număr întreg , determinat în mod unic de condițiile: [8]

r(-b,c)

r

$r+b\equiv 0\mod (2c)$
$-|c|<r<|c|,\quad if\quad {\sqrt {\Delta }}<|c|$
${\sqrt {\Delta }}-2|c|<r<{\sqrt {\Delta }},\quad if\quad |c|<{\sqrt {\Delta }}$

Rezultatul aplicării operatorului la formular se scrie ca . Operatorul este, de asemenea, definit ca: $\rho$ $f$ $n$ $\rho ^{n}(f)$ $\rho ^{-1}$

\rho ^{-1}{\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}{\frac {r(-b,c)^{2}- \Delta }{4c}},&r(-b,c),&c\end{pmatrix}}

, unde este definit în același mod ca în cazul precedent. Rețineți că, ca urmare a aplicării operatorilor și la o formă pătratică cu discriminant , formele pătratice rezultate vor avea și discriminant .

r(-b,c)

\rho ^{-1}

\rho

f={\begin{pmatrix}a,&b,&c\end{pmatrix}}

\Delta

\Delta

Metoda de obținere a unei forme reduse echivalentă cu aceasta a fost găsită de Carl Gauss și constă în aplicarea succesivă a operatorului de reducere până când acesta devine redus. $g=\rho (f)$ $f$

Teorema.

Fiecare formă este echivalentă cu o formă redusă, iar orice formă redusă pentru este egală cu o formă pozitivă . Dacă - este redus, atunci este și el redus. $f$ $f$ $\rho ^{k}(f)$ $k$ $f$ $\rho (f)$

De asemenea, pentru o înțelegere clară a tuturor operațiilor cu forme pătratice, avem nevoie de conceptele de forme pătratice, adiacente și ambigue.

Opțiuni

Ideea metodei Shanks este de a compara numărul de descompus cu o formă binară pătratică cu un discriminant , cu care se efectuează apoi o serie de transformări echivalente și trecerea de la formă la forma ambiguă . Apoi, va fi un divizor . $n$ $f$ $D=4n$ $f$ $(a',b',c')$ $\gcd(a',b')$ $n$

Prima variantă funcționează cu forme patratice binare pozitiv-definite ale unui discriminant negativ dat, iar în grupul clasei de formă găsește o formă ambig , care dă o factorizare a discriminantului. Complexitatea primei opțiuni este supusă adevărului ipotezei Riemann extinse . [9] $O(n^{1/5+\varepsilon })$

A doua variantă este SQUFOF, care utilizează un grup de clasă de forme pătratice binare cu un discriminant pozitiv. De asemenea, găsește forma ambig și factorizează discriminantul. Complexitatea SQUFOF echivalează cu operații aritmetice; algoritmul funcționează cu numere întregi care nu depășesc . Dintre algoritmii de factorizare cu complexitate exponențială, SQUFOF este considerat unul dintre cei mai eficienți. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n)}$

Scorul de convergență

Conform calculelor efectuate de Shanks însuși, numărul de iterații ale primului și celui de-al doilea ciclu al algoritmului este determinat de numărul de factori ai numărului și este aproximativ egal cu: $w$ $n$

${\frac {C}{2^{w}-2}}\cdot n^{1/4},$

unde este o constantă egală cu aproximativ 2,4 pentru primul ciclu de iterații. [zece] $C$

Descrierea algoritmului

Mai detaliat, algoritmul poate fi scris astfel: [11]

Intrare: un număr compus impar de factorizat. Dacă înlocuim cu Acum Ultima proprietate este necesară pentru ca determinantul formei pătratice să fie fundamental, ceea ce asigură convergența metodei. $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Ieșire: divizor non-trivial . $n$

1. Definiți forma pătratică originală , cu discriminant , unde .

f=(1,2b,b^{2}-D)

D=4n

b={\mathcal {b}}{\sqrt {n}}{\mathcal {c}}

2. Să executăm ciclul reducerilor până când forma devine pătrată.

f=\rho (f)

f

3. Calculați rădăcina pătrată a

f:~g=(a^{\prime },b^{\prime },c^{\prime })=f^{1/2)

4. Să executăm ciclul reducerilor până când valoarea celui de-al doilea coeficient se stabilizează . Numărul de iterații ale acestei bucle ar trebui să fie aproximativ egal cu jumătate din numărul de iterații ale primei bucle. Ultima valoare va da divizorul numărului (posibil banal).

p=\rho (g)

b_{i+1}'=b_{i}'

m

a^{\prime )

n

Implementarea algoritmului

Acum descriem algoritmul de implementare pe un computer. [11] Rețineți că, deși partea teoretică a algoritmului este legată de transformări echivalente ale formelor pătratice, partea practică a algoritmului se bazează pe calcularea coeficienților metodei fracțiunii continue fără a recurge la forme. Fiecare iterație a buclei corespunde unei operații de aplicare a operatorului de reducere la forma corespunzătoare. Dacă este necesar, puteți restaura formularele corespunzătoare folosind formulele: $P,Q,r$ $f_{k}=(a_{k},b_{k},c_{k})$ $(a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k }Q_{k})$

Intrare: număr compus $n$

Ieșire: divizor non-trivial $n$

Inițializarea algoritmului.
- Să verificăm dacă este un pătrat perfect. Dacă da, atunci calculați și terminați calculul. În caz contrar, să trecem la următorul articol. $n$ $d={\sqrt {n)),$
- Dacă atunci înlocuim cu Define $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Determinați valorile inițiale ale parametrilor $P,Q,r:$

$P_{0}=0,~Q_{0}=1,~r_{0}=P_{1}={\mathcal {b}}{\sqrt {n}}{\mathcal {c}} ,~Q_{1}=n-r_{0}^{2},r_{1}={\mathcal {b}}2r_{0}/Q_{1}{\mathcal {c}}.$

Primul ciclu
- $P_{k}=r_{k-1}\cdot Q_{k-1}-P_{k-1},~Q_{k}=Q_{k-2}+(P_{k-1} -P_{k})\cdot r_{k-1},r_{k}={\mathcal {b}}{\frac {P_{k}+{\mathcal {b}}{\sqrt {n}} {\mathcal {c}}}{Q_{k}}}{\mathcal {c}},~k\geq 2.$
- Continuăm să calculăm coeficienții până când găsim Q_k, care este un pătrat perfect. Acest lucru ar trebui să se întâmple la unele Let pentru un întreg Să trecem la următorul ciclu. $P_{k},~Q_{k}~r_{k)$ $k.$ $Q_{k}=d^{2)$ $d>0.$

Al doilea ciclu.
- haideti sa incepem un ciclu de calcul de noi parametri.Formulele pentru implementarea celui de-al doilea ciclu vor ramane aceleasi ca inainte. Doar valorile inițiale ale parametrilor se vor schimba $P_{j}^{\prime },~Q_{j}^{\prime },~r_{j}^{\prime }.$ $P^{\prime },~Q^{\prime },~r^{\prime }:$
- $P_{0}^{\prime }=-P_{k},~Q_{0}^{\prime }=d,~r_{0}^{\prime }={\mathcal {b)} {\frac {P_{0}^{\prime }+{\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}{Q_{0}^{\prime }}}{\ mathcal {c)),~P_{1}^{\prime }=r_{0}^{\prime }\cdot Q_{0}^{\prime }-P_{0}^{\prime },~Q_ {1}^{\prime }=(N-P_{1}^{\prime 2})/Q_{0}^{\prime }.$
- Calculul trebuie continuat până când două valori succesive sunt egale. Apoi, valoarea va da divizorul dorit al numărului.Descrierea algoritmului Shanks este finalizată. $P_{j}^{\prime },~P_{j+1}^{\prime )$ $Q_{j}$ $n.$

După cum am menționat deja, aceasta nu este singura implementare a acestui algoritm. De asemenea, puteți găsi implementarea algoritmului aici [8]

Un exemplu de factorizare a unui număr

Aplicam aceasta metoda pentru factorizarea numarului [8] $N=22117019$

Ciclul #1
$F_{i}$
$i$	$(-1)^{i-1}Q_{i-1}$	$2\cdot P_{i)$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$unu$
$unu$	$unu$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$patru$	${\displaystyle-7531}$	$2\cdot 3904$	$913$
$5$	$913$	$2\cdot 4313$	$-3850$
$6$	$-3850$	$2\cdot 3387$	$2765$
$7$	$2765$	$2\cdot 2143$	${\displaystyle-6338}$
$opt$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$zece$	$-4346$	$2\cdot 4331$	$773$
$unsprezece$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$paisprezece$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$cincisprezece$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$optsprezece$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Ciclul #2
$G_{i}$
$i$	$(-1)^{i-1}Q_{i-1}^{\prime }$	$2\cdot P_{i}^{\prime )$	$(-1)^{i}Q_{i}^{\prime }$
$0$	$-55$	$2\cdot 4652$	$8653$
$unu$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$patru$	$-415$	$2\cdot 4562$	$3145$
$5$	$3145$	$2\cdot 1728$	${\displaystyle-6083}$
$6$	${\displaystyle-6083}$	$2\cdot 4355$	$518$
$7$	$518$	$2\cdot 4451$	$-4451$
$opt$	$-4451$	$2\cdot 4451$	$518$

Acum puteți vedea în al doilea ciclu că De aici numărul $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Aplicații

Acest algoritm este utilizat în multe implementări ale NFS și QS pentru a factoriza numere auxiliare mici care apar la factorizarea unui întreg mare. În orice caz, SQUFOF este folosit în principal ca algoritm de ajutor în algoritmi de factorizare mai puternici și, prin urmare, SQUFOF va fi utilizat în general pentru a factoriza numere de dimensiuni modeste care nu au divizori primi mici. Astfel de numere sunt de obicei produsul unui număr mic de numere prime diferite. [8] .

Note

↑ Pentru mai multe informații despre istoria acestei metode și legătura ei cu metoda fracției continue, vezi articolul lui Gover și Wagstaff (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , High Performance Data Mining: Scaling Algorithms, Applications and Systems..
↑ 1 2 Hans Riesel, 1994 , Numerele prime și metodele computerizate pentru factorizare. Birkhauser, ediția a doua.
↑ Henri Cohen, 1996 , A Course in Computational Algebric Number Theory..
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
^ Samuel S. Wagstaff Jr., 2003 , Criptanalysis of Number Theoretic Ciphers.
↑ De exemplu, în FACTORIZARE FORMĂ PATRATĂ JASON E. GOWER ȘI SAMUEL S. WAGSTAFF, JR. Ipoteza 4.12. la pagina 20, Ipoteza 4.5 la pagina 16, de asemenea la demonstrarea teoremelor de complexitate a algoritmului etc.
↑ 1 2 3 4 5 FACTORIZARE FORMĂ PATRATĂ, 2003 , FACTORIZARE FORMĂ PATRATĂ.
↑ 1 2 Vasilenko, 2003 , Number-theoretic algorithms in cryptography.
↑ Ishmukhametov, 2011 , Metode de factorizare pentru numere naturale: Manual.
↑ 1 2 Ishmukhametov, 2011 , Metode de factorizare pentru numere naturale: Manual p. 79-80.

Literatură

Vasilenko O. N. Algoritmi teoretici numeric în criptografie . - Moscova: MTSNMO, 2003. - S. 75 - 76. - 328 p. — ISBN 5-94057-103-4 . Arhivat pe 27 ianuarie 2007 la Wayback Machine
Ishmukhametov Sh. T. Metode de factorizare a numerelor naturale: Manual . - Kazan: Universitatea din Kazan, 2011. - P. 74 - 82. - 190 p.
D.A. Buell. Forme cuadratice binare (neopr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 p. - ISBN 0-387-97037-1 .
Hans Riesel. Numerele prime și metodele computerizate pentru factorizare. Birkhauser, ediția a doua . - Suedia: Birkhauser, 1994. - P. p. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. Un curs în teoria numerelor algebrice computaționale . - Springer-Verlag , 1996. - P. 433 - 437. - 534 p. — ISBN 3-540-55640-0 .
Jason E. Gower și Samuel S. Wagstaff, JR. FACTORIZARE FORMĂ PATRATĂ . - Moscova: MTSNMO, 2003. - S. 1-16, 35-36. — 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Criptanaliză a cifrelor teoretice de numere . - CRC Press , 2003. - 318 p. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. Mining de date de înaltă performanță : algoritmi de scalare, aplicații și sisteme . - Kluwer Academic Publishers , 1999. - P. 111. - ISBN 0-7923-7745-1 .

Vezi și

Factorizarea numerelor întregi

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin