Shanks kvadratisk form metode

Shanks andengradsformmetoden er en faktoriseringsmetode for heltal baseret på brugen af kvadratiske former , udviklet af Daniel Shanks [1] i 1975 , som en udvikling af Fermats faktoriseringsmetode .

For 32-bit computere er algoritmer baseret på denne metode de ubestridte førende blandt faktoriseringsalgoritmer for tal fra til og vil sandsynligvis forblive det. [2] Denne algoritme kan opdele næsten ethvert 18-cifret sammensat tal på mindre end et millisekund. Algoritmen er ekstremt enkel, smuk og effektiv. Derudover bruges metoder baseret på denne algoritme som hjælpemidler i udvidelsen af divisorer af store tal, såsom Fermat-tal . $10^{{10}}$ $10^{18}$

Historie

Et andet navn for algoritmen er SQUFOF ( et akronym for engelsk er SQUAre FORM Factorization), hvilket betyder kvadratisk formfaktorisering . Denne tilgang har været ganske vellykket gennem årene, og som et resultat kan der findes en del forskellige modifikationer og implementeringer om dette emne i litteraturen. [3] De fleste af metoderne er komplekse og forvirrende, især når metoden skal implementeres på en computer. Som et resultat er mange varianter af algoritmer ikke egnede til implementering. Men i 1975 foreslog Daniel Shanks at skabe en algoritme , der kan implementeres og bruges ikke kun på en computer, men også på en simpel mobiltelefon.

Selvom Shanks har beskrevet andre algoritmer til heltalsfaktorisering, har han ikke publiceret noget på SQUFOF. Han holdt foredrag om emnet og forklarede den grundlæggende essens af sin metode for en ret lille kreds af mennesker. Nogle artikler fra andre videnskabsmænd [4] [3] [5] [6] diskuterede algoritmen, men ingen indeholder en detaljeret analyse. Det er også interessant, at Shanks i sin metode gør en del antagelser [7] , som desværre forblev uden bevis. I [8] præsenteres resultaterne af nogle forsøg, som indikerer, at mange antagelser er på plads. I sidste ende, baseret på disse forenklede antagelser, var Shanks i stand til at skabe SQUFOF.

Hjælpedefinitioner

For at forstå, hvordan denne algoritme implementeres, er det nødvendigt at kende minimumsinformationen om de matematiske objekter, der bruges i denne metode, nemlig kvadratiske former . En binær kvadratisk form er et polynomium i to variable og : $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 bruger kun ubestemte former . Med vi mener diskriminanten af en kvadratisk form. Vi vil sige, at den kvadratiske form repræsenterer et heltal , hvis der er heltal, således at ligheden er sand: . Hvis ligheden er sand , kaldes repræsentationen primitiv . $\Delta$ $f$ $m\in \mathbb {Z}$ $x_{0},y_{0}$ $f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2}$ $\gcd(x_{0},y_{0})=1$

For enhver ubestemt kvadratisk form kan reduktionsoperatoren defineres 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}}

, hvor er defineret som et heltal , entydigt bestemt af betingelserne: [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 af at anvende operatoren på formularen én gang skrives som . Operatøren er også defineret 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}}

, hvor er defineret på samme måde som i det foregående tilfælde. Bemærk, at som et resultat af at anvende operatorerne og på en kvadratisk form med diskriminant , vil de resulterende kvadratiske former også have diskriminant .

r(-b,c)

\rho ^{-1}

\rho

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

\Delta

\Delta

Metoden til at opnå en reduceret form svarende til denne blev fundet af Carl Gauss og består i successiv anvendelse af reduktionsoperatoren, indtil den bliver reduceret. $g=\rho (f)$ $f$

Sætning.

Hver form svarer til en reduceret form, og enhver reduceret form for er lig med en positiv . Hvis - er reduceret, så reduceres det også. $f$ $f$ $\rho ^{k}(f)$ $k$ $f$ $\rho (f)$

For en klar forståelse af alle operationer med kvadratiske former har vi også brug for begreberne kvadratiske, tilstødende og tvetydige kvadratiske former

Indstillinger

Ideen med Shanks-metoden er at sammenligne det tal , der skal dekomponeres, med en kvadratisk binær form med en diskriminant , hvormed en række ækvivalente transformationer derefter udføres og overgangen fra formen til den flertydige form . Så vil være en divisor . $n$ $f$ $D=4n$ $f$ $(a',b',c')$ $\gcd(a',b')$ $n$

Den første variant arbejder med positiv-bestemte binære kvadratiske former af en given negativ diskriminant, og i formklassegruppen finder den en ambig form , som giver en faktorisering af diskriminanten. Kompleksiteten af den første mulighed er underlagt sandheden i den udvidede Riemann-hypotese . [9] $O(n^{1/5+\varepsilon })$

Den anden variant er SQUFOF, som bruger en klassegruppe af binære kvadratiske former med en positiv diskriminant. Den finder også den flertydige form og faktoriserer diskriminanten. Kompleksiteten af SQUFOF svarer til aritmetiske operationer; Algoritmen fungerer med heltal, der ikke overstiger . Blandt faktoriseringsalgoritmer med eksponentiel kompleksitet anses SQUFOF for at være en af de mest effektive. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n))$

Konvergensscore

Ifølge beregningerne udført af Shanks selv bestemmes antallet af iterationer af den første og anden cyklus af algoritmen af antallet af faktorer i tallet og er omtrent lig med: $w$ $n$

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

hvor er en konstant lig med ca. 2,4 for den første cyklus af iterationer. [ti] $C$

Beskrivelse af algoritmen

Mere detaljeret kan algoritmen skrives som følger: [11]

Input: Et ulige sammensat tal , der skal faktoriseres. Hvis vi erstatter med Nu Den sidste egenskab er nødvendig for at determinanten for den kvadratiske form er fundamental, hvilket sikrer metodens konvergens. $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Output: Ikke-trivial divisor . $n$

1. Definer den oprindelige kvadratiske form , med diskriminant , hvor .

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

D=4n

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

2. Lad os udføre reduktionscyklussen, indtil formen bliver firkantet.

f=\rho (f)

f

3. Beregn kvadratroden af

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

4. Lad os udføre reduktionscyklussen, indtil værdien af den anden koefficient stabiliserer sig . Antallet af iterationer af denne løkke skal være omtrent lig med halvdelen af antallet af iterationer i den første løkke. Den sidste værdi vil give tallets divisor (muligvis trivielt).

p=\rho (g)

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

m

a^{\prime }

n

Implementering af algoritmen

Nu beskriver vi algoritmen til implementering på en computer. [11] Bemærk, at selvom den teoretiske del af algoritmen er relateret til ækvivalente transformationer af kvadratiske former, er den praktiske del af algoritmen baseret på at beregne koefficienterne for den fortsatte fraktionmetode uden at ty til formerne. Hver iteration af sløjfen svarer til én operation med at anvende reduktionsoperatoren på den tilsvarende form. Om nødvendigt kan du gendanne de tilsvarende formularer ved hjælp af formlerne: $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})$

Input: Sammensat nummer $n$

Output: Ikke-triviel divisor $n$

Algoritme initialisering.
- Lad os tjekke, om det er en perfekt firkant. Hvis ja, så udregn og afslut beregningen. Ellers, lad os gå videre til næste punkt. $n$ $d={\sqrt {n)),$
- Hvis så vi erstatter med Define $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Bestem startværdierne for parametrene $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ørste cyklus
- $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 med at beregne koefficienterne, indtil vi finder Q_k, som er et perfekt kvadrat. Dette skulle ske på et eller andet tidspunkt for et heltal Lad os gå videre til næste cyklus. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ $Q_{k}=d^{2}$ $d>0.$

Anden cyklus.
- lad os starte en cyklus med beregning af nye parametre Formlerne for implementering af anden cyklus forbliver de samme som før. Kun de indledende værdier af parametrene ændres $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 }}}{\ matematisk {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 }.$
- Beregningen skal fortsættes, indtil to på hinanden følgende værdier er ens. Derefter vil værdien give den ønskede divisor af tallet. Beskrivelsen af Shanks-algoritmen er færdig. ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime ))$ $Q_{j}$ $n.$

Som allerede nævnt er dette ikke den eneste implementering af denne algoritme. Du kan også finde implementeringen af algoritmen her [8]

Et eksempel på faktorisering af et tal

Vi anvender denne metode til at faktorisere tallet [8] $N=22117019$

Cyklus #1
$F_{i}$
$jeg$	$(-1)^{i-1}Q_{i-1}$	$2\cdot P_{i}$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$en$
$en$	$en$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$fire$	${\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}$
$otte$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$ti$	$-4346$	$2\cdot 4331$	$773$
$elleve$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$fjorten$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$femten$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$atten$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Cyklus #2
$G_{i}$
$jeg$	$(-1)^{i-1}Q_{i-1}^{\prime }$	${\displaystyle 2\cdot P_{i}^{\prime ))$	${\displaystyle (-1)^{i}Q_{i}^{\prime ))$
$0$	$-55$	$2\cdot 4652$	$8653$
$en$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$fire$	$-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$
$otte$	$-4451$	$2\cdot 4451$	$518$

Nu kan du se i anden cyklus, at Deraf tallet $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Ansøgninger

Denne algoritme bruges i mange implementeringer af NFS og QS til at faktorisere små hjælpenumre, der opstår ved faktorisering af et stort heltal. Under alle omstændigheder bruges SQUFOF hovedsageligt som en hjælpealgoritme i mere kraftfulde faktoriseringsalgoritmer, og derfor vil SQUFOF generelt blive brugt til at faktorisere tal af beskeden størrelse, der ikke har små primtal divisorer. Sådanne tal er normalt produktet af et lille antal forskellige primtal. [8] .

Noter

↑ For mere information om denne metodes historie og dens sammenhæng med den fortsatte fraktionmetode, se artiklen af Gover og Wagstaff (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , High Performance Data Mining: Scaling Algorithms, Applications and Systems..
↑ 1 2 Hans Riesel, 1994 , primtal og computermetoder til faktorisering. Birkhauser, anden udgave.
↑ Henri Cohen, 1996 , A Course in Computational Algebraic Number Theory..
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Cryptanalysis of Number Theoretic Ciphers.
↑ For eksempel i KVADRATFORM FACTORISATION JASON E. GOWER OG SAMUEL S. WAGSTAFF, JR. Antagelse 4.12. på side 20, Antagelse 4.5 på side 16, også ved bevisførelse af algoritmekompleksitetsteoremer mv.
↑ 1 2 3 4 5 KVADRATFORMFAKTORISERING, 2003 , KVADRATFORMFAKTORISERING.
↑ 1 2 Vasilenko, 2003 , Talteoretiske algoritmer i kryptografi.
↑ Ishmukhametov, 2011 , Faktoriseringsmetoder for naturlige tal: Lærebog.
↑ 1 2 Ishmukhametov, 2011 , Faktoriseringsmetoder for naturlige tal: Lærebog s. 79-80.

Litteratur

Vasilenko O. N. Talteoretiske algoritmer i kryptografi . - Moskva: MTSNMO, 2003. - S. 75 - 76. - 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Ishmukhametov Sh. T. Metoder til faktorisering af naturlige tal: Lærebog . - Kazan: Kazan University, 2011. - S. 74 - 82. - 190 s.
D.A. Buell. Binære kvadratiske former (neopr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 s. - ISBN 0-387-97037-1 .
Hans Riesel. Primtal og computermetoder til faktorisering. Birkhauser, anden udgave . - Sverige: Birkhauser, 1994. - S. s. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. Et kursus i beregningsmæssig algebraisk talteori . - Springer-Verlag , 1996. - S. 433 - 437. - 534 s. — ISBN 3-540-55640-0 .
Jason E. Gower og Samuel S. Wagstaff, JR. KVADRATFORMFAKTORISERING . - Moskva: MTSNMO, 2003. - S. 1-16, 35-36. — 38 sek. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Krypteringsanalyse af talteoretiske cifre . - CRC Press , 2003. - 318 s. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. High Performance Data Mining : Skaleringsalgoritmer, applikationer og systemer . - Kluwer Academic Publishers , 1999. - S. 111. - ISBN 0-7923-7745-1 .

Se også

Faktorisering af heltal

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme