Shanks másodfokú forma módszer

A Shanks kvadratikus alakmódszer egy négyzetes alakok használatán alapuló egész számok faktorizációs módszere , amelyet Daniel Shanks [1] dolgozott ki 1975 -ben a Fermat-féle faktorizációs módszer továbbfejlesztéseként .

A 32 bites számítógépek esetében az ezen a módszeren alapuló algoritmusok vitathatatlanul vezető szerepet töltenek be a től ig terjedő számok faktorizációs algoritmusai között , és valószínűleg azok is maradnak. [2] Ez az algoritmus szinte bármilyen 18 jegyű összetett számot képes felosztani kevesebb mint egy ezredmásodperc alatt. Az algoritmus rendkívül egyszerű, gyönyörű és hatékony. Ezenkívül az ezen az algoritmuson alapuló módszereket segédeszközként használják nagy számok osztóinak, például Fermat-számoknak a kiterjesztésében . $10^{{10}}$ $10^{18}$

Történelem

Az algoritmus másik neve SQUFOF ( az angol mozaikszó : SQUARE FORm Factorization), ami négyzetes alakfaktorizációt jelent . Ez a megközelítés az évek során meglehetősen sikeresnek bizonyult, és ennek eredményeként a szakirodalomban számos különféle módosítás és megvalósítás található ebben a témában. [3] A legtöbb módszer bonyolult és zavaros, különösen akkor, ha a módszert számítógépen kell megvalósítani. Ennek eredményeként az algoritmusok számos változata nem alkalmas a megvalósításra. 1975-ben azonban Daniel Shanks egy olyan algoritmus létrehozását javasolta, amely nemcsak számítógépen, hanem egyszerű mobiltelefonon is megvalósítható és használható.

Bár Shanks más algoritmusokat is leírt az egész számok faktorizálására, nem tett közzé semmit az SQUFOF-on. A témában előadásokat tartott, módszerének alapvető lényegét egy meglehetősen szűk körben ismertette. Más tudósok egyes tanulmányai [4] [3] [5] [6] tárgyalták az algoritmust, de egyik sem tartalmaz részletes elemzést. Az is érdekes, hogy módszerében Shanks elég sok feltételezést fogalmaz meg [7] , amelyek sajnos bizonyítás nélkül maradtak. A [8] -ban néhány kísérlet eredményét mutatják be, amelyek arra utalnak, hogy sok feltételezés áll fenn. Végül ezekre az egyszerűsítő feltételezésekre alapozva Shanks létrehozta a SQUFOF-ot.

Segéddefiníciók

Ahhoz, hogy megértsük, hogyan valósul meg ez az algoritmus, ismerni kell a minimális információt az ebben a módszerben használt matematikai objektumokról, nevezetesen a másodfokú formákról . A bináris másodfokú forma egy polinom két változóból és : $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}}.

A Shanks metódus csak határozatlan formákat használ . A másodfokú forma diszkriminánsát értjük. Azt mondjuk, hogy a másodfokú alak egész számot jelent, ha vannak olyan egészek, amelyekre az egyenlőség igaz: . Ha az egyenlőség igaz , akkor a reprezentációt primitívnek nevezzük . $\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$

Bármilyen határozatlan négyzetes alak esetében a redukciós operátor a következőképpen definiálható : $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}}

, ahol egész számként van definiálva, amelyet a feltételek egyedileg határoznak meg: [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 }}$

Ha az operátort egyszer alkalmazzuk az űrlapra , az eredményt a következőképpen írjuk le . Az operátor a következőképpen is meghatározható : $\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{pmátrix}}

, ahol ugyanúgy definiálható, mint az előző esetben. Vegyük észre, hogy az operátorok és másodfokú alakzat diszkriminancia alkalmazása eredményeként a kapott másodfokú alakoknak is lesz diszkriminánsa .

r(-b,c)

\rho ^{-1}

\rho

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

\Delta

\Delta

Az ezzel egyenértékű redukált forma előállításának módszerét Carl Gauss találta meg, és a redukciós operátor egymás utáni alkalmazásából áll, amíg redukálódik. $g=\rho (f)$ $f$

Tétel.

Mindegyik alak egyenértékű valamilyen redukált formával, és bármely redukált alakja egyenlő valamilyen pozitív formával . Ha - csökken, akkor az is csökken. $f$ $f$ $\rho ^{k}(f)$ $k$ $f$ $\rho (f)$

Ezenkívül a másodfokú alakokkal végzett műveletek világos megértéséhez szükségünk van a négyzet, a szomszédos és a kétértelmű másodfokú formák fogalmára.

Opciók

A Shanks módszer ötlete az, hogy összehasonlítja a felbontandó számot egy másodfokú bináris formával egy diszkriminánssal , amellyel egy sor ekvivalens transzformációt hajtanak végre, és az átmenetet a formából a kétértelmű formába . Akkor egy osztó lesz . $n$ $f$ $D=4n$ $f$ ${\megjelenítési stílus (a',b',c')}$ $\gcd(a',b')$ $n$

Az első változat egy adott negatív diszkrimináns pozitív-definit bináris másodfokú alakjaival dolgozik, az alakosztálycsoportban pedig egy ambig alakot talál , ami a diszkrimináns faktorizációját adja. Az első lehetőség összetettsége a kiterjesztett Riemann-hipotézis igazságától függ . [9] $O(n^{1/5+\varepsilon })$

A második változat a SQUFOF, amely bináris másodfokú formák osztálycsoportját használja pozitív diszkriminánssal. Megtalálja az ambig formát és faktorizálja a diszkriminánst. A SQUFOF összetettsége aritmetikai műveletek; az algoritmus legfeljebb . Az exponenciális összetettségű faktorizációs algoritmusok közül az SQUFOF tekinthető az egyik leghatékonyabbnak. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n))$

Konvergencia pontszám

A Shanks által végzett számítások szerint az algoritmus első és második ciklusának iterációinak számát a szám tényezőinek száma határozza meg, és megközelítőleg egyenlő: $w$ $n$

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

ahol egy konstans körülbelül 2,4 az első iterációs ciklusban. [tíz] $C$

Az algoritmus leírása

Részletesebben az algoritmus a következőképpen írható fel: [11]

Bemenet: Páratlan összetett szám a faktorizáláshoz. Ha a Most -ra cseréljük Az utolsó tulajdonság szükséges ahhoz, hogy a másodfokú forma determinánsa fundamentális legyen, ami biztosítja a módszer konvergenciáját. $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Kimenet: Nem triviális osztó . $n$

1. Határozza meg az eredeti másodfokú alakot diszkriminánssal , ahol .

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

D=4n

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

2. Végezzük el a kicsinyítési ciklust, amíg az alakzat négyzet alakú lesz.

f=\rho (f)

f

3. Számítsa ki a négyzetgyökét!

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

4. Végezzük el a csökkentési ciklust addig, amíg a második együttható értéke stabilizálódik . A ciklus iterációinak számának körülbelül fele kell lennie az első ciklus iterációinak számának. Az utolsó érték adja a szám osztóját (esetleg triviális).

p=\rho (g)

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

m

{\displaystyle a^{\prime ))

n

Az algoritmus megvalósítása

Most leírjuk a számítógépen való megvalósítás algoritmusát. [11] Megjegyzendő, hogy bár az algoritmus elméleti része másodfokú formák ekvivalens transzformációira vonatkozik, az algoritmus gyakorlati része a folytonos tört módszer együtthatóinak kiszámításán alapul, az alakok igénybevétele nélkül. A ciklus minden iterációja megfelel a redukciós operátor megfelelő űrlapra történő alkalmazásának egy műveletének. Ha szükséges, visszaállíthatja a megfelelő űrlapokat a képletekkel: $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})$

Bevitel: Összetett szám $n$

Kimenet: Nem triviális osztó $n$

Algoritmus inicializálása.
- Nézzük meg, hogy tökéletes-e a négyzet. Ha igen, akkor számítsa ki és fejezze be a számítást. Ellenkező esetben térjünk át a következő tételre. $n$ $d={\sqrt {n)),$
- Ha majd a Define -re cseréljük $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Határozza meg a paraméterek kezdeti értékeit $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}}.$

Első ciklus
- $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.$
- Addig folytatjuk az együtthatók számítását , amíg meg nem találjuk a Q_k értéket, ami egy tökéletes négyzet. Ennek meg kell történnie valami Let -nél egy egész számra . Térjünk át a következő ciklusra. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ ${\displaystyle Q_{k}=d^{2))$ $d>0.$

Második ciklus.
- kezdjük el az új paraméterek számítási ciklusát A második ciklus megvalósításának képletei ugyanazok maradnak, mint korábban. Csak a paraméterek kezdeti értékei változnak $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 }}}{\ matematikai {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 }.$
- A számítást addig kell folytatni, amíg két egymást követő érték egyenlő nem lesz. Ekkor az érték megadja a szám kívánt osztóját.. A Shanks algoritmus leírása elkészült. ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime ))$ $Q_{j}$ $n.$

Mint már említettük, ennek az algoritmusnak nem ez az egyetlen megvalósítása. Az algoritmus megvalósítását itt is megtalálod [8]

Példa egy szám faktorizálására

Ezt a módszert alkalmazzuk a szám faktorizálására [8] $N=22117019$

Ciklus #1
$F_{i}$
$én$	$(-1)^{i-1}Q_{i-1}$	$2\cdot P_{i}$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$egy$
$egy$	$egy$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$négy$	${\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}$
$nyolc$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$tíz$	$-4346$	$2\cdot 4331$	$773$
$tizenegy$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$tizennégy$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$tizenöt$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$tizennyolc$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Ciklus #2
$GI}$
$én$	${\displaystyle (-1)^{i-1}Q_{i-1}^{\prime ))$	${\displaystyle 2\cdot P_{i}^{\prime ))$	$(-1)^{i}Q_{i}^{\prime }$
$0$	$-55$	$2\cdot 4652$	$8653$
$egy$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$négy$	$-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$
$nyolc$	$-4451$	$2\cdot 4451$	$518$

Most a második ciklusban láthatja, hogy Innen a szám $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Alkalmazások

Ezt az algoritmust az NFS és QS számos megvalósításában használják a kis segédszámok faktorizálására, amelyek nagy egész számok faktorálásakor keletkeznek. Mindenesetre az SQUFOF-ot főként segédalgoritmusként használják erősebb faktorizációs algoritmusokban, ezért az SQUFOF-ot általában olyan szerény méretű számok faktorizálására használják, amelyek nem rendelkeznek kis prímosztókkal. Az ilyen számok általában kis számú különböző prímszám szorzata. [8] .

Jegyzetek

↑ A módszer történetéről és a folyamatos tört módszerrel való kapcsolatáról bővebben Gover és Wagstaff (J. Gover, SS Wagstaff) cikkében olvashat.
↑ Yike Guo, 1999 , Nagy teljesítményű adatbányászat: skálázási algoritmusok, alkalmazások és rendszerek.
↑ 1 2 Hans Riesel, 1994 , Prímszámok és számítógépes módszerek a faktorizáláshoz. Birkhauser, második kiadás.
↑ Henri Cohen, 1996 , Számítási algebrai számelmélet tanfolyam.
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Számelméleti rejtjelek kriptanalízise.
↑ Például a SQUARE FORM FACTORIZATION-ban JASON E. GOWER ÉS SAMUEL S. WAGSTAFF, JR. 4.12. feltételezés. a 20. oldalon, a 4.5. feltevést a 16. oldalon, az algoritmus bonyolultsági tételeinek bizonyításakor is stb.
↑ 1 2 3 4 5 SZÖVEG FORMA TÉNYEZÉS, 2003 , SZÖVEG FORMA TÉNYEZÉS.
↑ 1 2 Vasilenko, 2003 , Számelméleti algoritmusok a kriptográfiában.
↑ Ishmukhametov, 2011 , Faktorizációs módszerek természetes számokhoz: Tankönyv.
↑ 1 2 Ishmukhametov, 2011 , Faktorizációs módszerek természetes számokhoz: Tankönyv 79-80.

Irodalom

Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában . - Moszkva: MTSNMO, 2003. - S. 75 - 76. - 328 p. — ISBN 5-94057-103-4 . Archiválva 2007. január 27-én a Wayback Machine -nél
Ishmukhametov Sh. T. A természetes számok faktorizálásának módszerei: Tankönyv . - Kazan: Kazan University, 2011. - P. 74 - 82. - 190 p.
D.A. Buell. Bináris másodfokú formák (neopr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 p. - ISBN 0-387-97037-1 .
Hans Riesel. Prímszámok és számítógépes módszerek a faktorizáláshoz. Birkhauser, második kiadás . - Svédország: Birkhauser, 1994. - P. 186-192. o. - ISBN 978-0-8176-8297-2 .
Henri Cohen. Számítási algebrai számelmélet tanfolyam . - Springer-Verlag , 1996. - P. 433 - 437. - 534 p. — ISBN 3-540-55640-0 .
Jason E. Gower és Samuel S. Wagstaff, JR. NÉGYEDET FORMA TÉNYEZÉS . - Moszkva: MTSNMO, 2003. - S. 1-16, 35-36. — 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Számelméleti rejtjelek kriptanalízise . - CRC Press , 2003. - 318 p. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. Nagy teljesítményű adatbányászat : skálázási algoritmusok, alkalmazások és rendszerek . - Kluwer Academic Publishers , 1999. - P. 111. - ISBN 0-7923-7745-1 .

Lásd még

Egész számok faktorizálása

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus