Shanks kvadratisk form metod

Shanks kvadratiska formmetoden är en faktoriseringsmetod för heltal baserad på användningen av kvadratiska former , utvecklad av Daniel Shanks [1] 1975 , som en utveckling av Fermats faktoriseringsmetod .

För 32-bitars datorer är algoritmer baserade på denna metod de obestridda ledande bland faktoriseringsalgoritmer för siffror från till och kommer förmodligen att förbli så. [2] Denna algoritm kan dela nästan alla 18-siffriga sammansatta tal på mindre än en millisekund. Algoritmen är extremt enkel, vacker och effektiv. Dessutom används metoder baserade på denna algoritm som hjälpmedel vid expansionen av divisorer för stora tal som Fermat-tal . $10^{{10}}$ $10^{18}$

Historik

Ett annat namn för algoritmen är SQUFOF ( en akronym för engelska är SQUAre FORm Factorization), vilket betyder kvadratisk formfaktorisering . Detta tillvägagångssätt har varit ganska framgångsrikt under åren och som ett resultat kan en hel del olika modifieringar och implementeringar hittas på detta ämne i litteraturen. [3] De flesta av metoderna är komplexa och förvirrande, särskilt när metoden behöver implementeras på en dator. Som ett resultat är många varianter av algoritmer inte lämpliga för implementering. Men 1975 föreslog Daniel Shanks att skapa en algoritm som kan implementeras och användas inte bara på en dator utan också på en enkel mobiltelefon.

Även om Shanks har beskrivit andra algoritmer för heltalsfaktorisering har han inte publicerat något på SQUFOF. Han höll föreläsningar i ämnet och förklarade den grundläggande essensen av sin metod för en ganska liten krets av människor. Vissa artiklar av andra forskare [4] [3] [5] [6] diskuterade algoritmen, men ingen innehåller en detaljerad analys. Det är också intressant att Shanks i sin metod gör en hel del antaganden [7] , som tyvärr förblev utan bevis. I [8] presenteras resultaten av några experiment, som tyder på att många antaganden är på plats. Till slut, baserat på dessa förenklade antaganden, kunde Shanks skapa SQUFOF.

Hjälpdefinitioner

För att förstå hur denna algoritm implementeras är det nödvändigt att känna till den minsta informationen om de matematiska objekten som används i denna metod, nämligen kvadratiska former . En binär kvadratisk form är ett polynom i två variabler och : $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}}.

Shanks - metoden använder endast obestämda former . Med vi menar diskriminanten av en kvadratisk form. Vi kommer att säga att den kvadratiska formen representerar ett heltal om det finns heltal så att likheten är sann: . Om likheten är sann , så kallas representationen 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$

För alla obestämda kvadratiska former kan reduktionsoperatorn definieras som: $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}}

, där definieras som ett heltal , unikt bestämt av villkoren: [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 }}$

Resultatet av att tillämpa operatorn på formuläret en gång skrivs som . Operatören definieras också som: $\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}}

, där definieras på samma sätt som i föregående fall. Observera att som ett resultat av att tillämpa operatorerna och på en kvadratisk form med diskriminant , kommer de resulterande kvadratiska formerna också att ha diskriminant .

r(-b,c)

\rho ^{-1}

\rho

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

\Delta

\Delta

Metoden för att erhålla en reducerad form motsvarande denna hittades av Carl Gauss och består i att successivt applicera reduktionsoperatorn tills den reduceras. $g=\rho (f)$ $f$

Sats.

Varje form är likvärdig med någon reducerad form, och varje reducerad form för är lika med någon positiv . Om - reduceras, så reduceras det också. $f$ $f$ $\rho ^{k}(f)$ $k$ $f$ $\rho (f)$

För en tydlig förståelse av alla operationer med kvadratiska former behöver vi också begreppen kvadratiska, intilliggande och tvetydiga kvadratiska former

Alternativ

Tanken med Shanks-metoden är att jämföra talet som ska dekomponeras med en kvadratisk binär form med en diskriminant , med vilken en serie ekvivalenta transformationer sedan utförs och övergången från formen till den tvetydiga formen . Då kommer att vara en divisor . $n$ $f$ $D=4n$ $f$ $(a',b',c')$ $\gcd(a',b')$ $n$

Den första varianten fungerar med positiv-definita binära kvadratiska former av en given negativ diskriminant, och i formklassgruppen finner den en ambig form , vilket ger en faktorisering av diskriminanten. Komplexiteten i det första alternativet är föremål för sanningen i den utökade Riemann-hypotesen . [9] $O(n^{1/5+\varepsilon })$

Den andra varianten är SQUFOF, som använder en klassgrupp av binära kvadratiska former med en positiv diskriminant. Den hittar också den tvetydiga formen och faktoriserar diskriminanten. Komplexiteten i SQUFOF uppgår till aritmetiska operationer; Algoritmen fungerar med heltal som inte överstiger . Bland faktoriseringsalgoritmer med exponentiell komplexitet anses SQUFOF vara en av de mest effektiva. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n))$

Konvergenspoäng

Enligt beräkningarna utförda av Shanks själv bestäms antalet iterationer av den första och andra cykeln av algoritmen av antalet faktorer för numret och är ungefär lika med: $w$ $n$

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

där är en konstant lika med ungefär 2,4 för den första cykeln av iterationer. [tio] $C$

Beskrivning av algoritmen

Mer detaljerat kan algoritmen skrivas enligt följande: [11]

Inmatning: Ett udda sammansatt tal att faktorisera. Om vi ersätter med Nu Den sista egenskapen är nödvändig för att bestämningsfaktorn för den kvadratiska formen ska vara fundamental, vilket säkerställer metodens konvergens. $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Utgång: Icke-trivial divisor . $n$

1. Definiera den ursprungliga kvadratiska formen , med diskriminant , där .

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

D=4n

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

2. Låt oss köra reduktionscykeln tills formen blir kvadratisk.

f=\rho (f)

f

3. Beräkna kvadratroten ur

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

4. Låt oss köra reduktionscykeln tills värdet på den andra koefficienten stabiliseras . Antalet iterationer av denna slinga bör vara ungefär lika med hälften av antalet iterationer av den första slingan. Det sista värdet kommer att ge talets divisor (eventuellt trivialt).

p=\rho (g)

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

m

{\displaystyle a^{\prime ))

n

Implementering av algoritmen

Nu beskriver vi algoritmen för implementering på en dator. [11] Observera att även om den teoretiska delen av algoritmen är relaterad till ekvivalenta transformationer av kvadratiska former, så bygger den praktiska delen av algoritmen på att beräkna koefficienterna för den fortsatta bråkmetoden utan att tillgripa formerna. Varje iteration av slingan motsvarar en operation för att applicera reduktionsoperatorn på motsvarande form. Om det behövs kan du återställa motsvarande formulär med formlerna: $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})$

Inmatning: Sammansatt nummer $n$

Utgång: Icke-trivial divisor $n$

Algoritminitiering.
- Låt oss kolla om det är en perfekt fyrkant. Om ja, beräkna och avsluta beräkningen. Annars, låt oss gå vidare till nästa punkt. $n$ $d={\sqrt {n)),$
- Om då vi ersätter med Define $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Bestäm de initiala värdena för parametrarna $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}}.$

Första cykeln
- $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.$
- Vi fortsätter att beräkna koefficienterna tills vi hittar Q_k, som är en perfekt kvadrat. Detta bör ske vid något Let för ett heltal . Låt oss gå vidare till nästa cykel. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ ${\displaystyle Q_{k}=d^{2))$ $d>0.$

Andra cykeln.
- låt oss starta en cykel för att beräkna nya parametrar Formlerna för implementeringen av den andra cykeln kommer att förbli desamma som tidigare. Endast de initiala värdena för parametrarna kommer att ändras $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 }.$
- Beräkningen bör fortsätta tills två på varandra följande värden är lika. Då kommer värdet att ge den önskade divisorn för talet. Beskrivningen av Shanks-algoritmen är klar. ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime ))$ $Q_{j}$ $n.$

Som redan nämnts är detta inte den enda implementeringen av denna algoritm. Du kan också hitta implementeringen av algoritmen här [8]

Ett exempel på faktorisering av ett tal

Vi använder denna metod för att faktorisera talet [8] $N=22117019$

Cykel #1
$F_{i}$
$i$	$(-1)^{i-1}Q_{i-1}$	${\displaystyle 2\cdot P_{i))$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$ett$
$ett$	$ett$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$fyra$	${\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}$
$åtta$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$tio$	$-4346$	$2\cdot 4331$	$773$
$elva$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$fjorton$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$femton$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$arton$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Cykel #2
$G_{i}$
$i$	$(-1)^{i-1}Q_{i-1}^{\prime }$	${\displaystyle 2\cdot P_{i}^{\prime ))$	$(-1)^{i}Q_{i}^{\prime }$
$0$	$-55$	$2\cdot 4652$	$8653$
$ett$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$fyra$	$-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$
$åtta$	$-4451$	$2\cdot 4451$	$518$

Nu kan du se i den andra cykeln att Därav siffran $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Applikationer

Denna algoritm används i många implementeringar av NFS och QS för att faktorisera små hjälptal som uppstår vid faktorisering av ett stort heltal. I vilket fall som helst används SQUFOF huvudsakligen som en hjälpalgoritm i mer kraftfulla faktoriseringsalgoritmer och därför kommer SQUFOF i allmänhet att användas för att faktorisera tal av blygsam storlek som inte har små primtalsdelare. Sådana tal är vanligtvis produkten av ett litet antal olika primtal. [8] .

Anteckningar

↑ För mer information om denna metods historia och dess samband med den fortsatta bråkmetoden, se artikeln av Gover och Wagstaff (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , High Performance Data Mining: Scaling Algorithms, Applications and Systems..
↑ 1 2 Hans Riesel, 1994 , primtal och datormetoder för faktorisering. Birkhauser, andra upplagan.
↑ Henri Cohen, 1996 , A Course in Computational Algebraic Number Theory..
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Krypteringsanalys av nummerteoretiska chiffer.
↑ Till exempel i KVADRATFORM FACTORISATION JASON E. GOWER AND SAMUEL S. WAGSTAFF, JR. Antagande 4.12. på sidan 20, Antagande 4.5 på sidan 16, även vid bevisning av algoritmkomplexitetssatser m.m.
↑ 1 2 3 4 5 KVADRATFORMFAKTORISERING, 2003 , KVADRATFORMFAKTORISERING.
↑ 1 2 Vasilenko, 2003 , Talteoretiska algoritmer i kryptografi.
↑ Ishmukhametov, 2011 , Faktoriseringsmetoder för naturliga tal: Lärobok.
↑ 1 2 Ishmukhametov, 2011 , Faktoriseringsmetoder för naturliga tal: Lärobok s. 79-80.

Litteratur

Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - Moskva: MTSNMO, 2003. - S. 75 - 76. - 328 sid. — ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Ishmukhametov Sh. T. Metoder för faktorisering av naturliga tal: Lärobok . - Kazan: Kazan University, 2011. - S. 74 - 82. - 190 s.
D.A. Buell. Binära kvadratiska former (neopr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 sid. - ISBN 0-387-97037-1 .
Hans Riesel. Primtal och datormetoder för faktorisering. Birkhauser, andra upplagan . - Sverige: Birkhauser, 1994. - S. s. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. En kurs i beräkningsalgebraisk talteori . - Springer-Verlag , 1996. - S. 433 - 437. - 534 sid. — ISBN 3-540-55640-0 .
Jason E. Gower och Samuel S. Wagstaff, JR. KVADRATISK FORM FAKTORISERING . - Moskva: MTSNMO, 2003. - S. 1-16, 35-36. — 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Kryptanalys av talteoretiska chiffer . - CRC Press , 2003. - 318 sid. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. High Performance Data Mining : Skalningsalgoritmer, applikationer och system . - Kluwer Academic Publishers , 1999. - P. 111. - ISBN 0-7923-7745-1 .

Se även

Faktorisering av heltal

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm