Shanksova kvadratická tvarová metoda

Shanksova metoda kvadratické formy je metoda faktorizace pro celá čísla založená na použití kvadratických forem , kterou vyvinul Daniel Shanks [1] v roce 1975 jako vývoj Fermatovy metody faktorizace .

U 32bitových počítačů jsou algoritmy založené na této metodě nesporným lídrem mezi faktorizačními algoritmy pro čísla od do a pravděpodobně tomu tak zůstane. [2] Tento algoritmus dokáže rozdělit téměř jakékoli 18místné složené číslo za méně než milisekundu. Algoritmus je velmi jednoduchý, krásný a efektivní. Kromě toho se metody založené na tomto algoritmu používají jako pomocné při rozšiřování dělitelů velkých čísel, jako jsou Fermatova čísla . $10^{{10}}$ $10^{18}$

Historie

Jiný název pro algoritmus je SQUFOF ( zkratka pro angličtinu je SQUare FORm Factorization), což znamená kvadratická tvarová faktorizace . Tento přístup byl v průběhu let poměrně úspěšný a v důsledku toho lze na toto téma v literatuře nalézt mnoho různých modifikací a implementací. [3] Většina metod je složitá a matoucí, zvláště když je třeba metodu implementovat na počítači. V důsledku toho mnoho variant algoritmů není vhodných pro implementaci. V roce 1975 však Daniel Shanks navrhl vytvořit algoritmus , který lze implementovat a používat nejen na počítači, ale také na jednoduchém mobilním telefonu.

Ačkoli Shanks popsal další algoritmy pro celočíselnou faktorizaci, na SQUFOF nic nepublikoval. Na toto téma přednášel a poměrně úzkému okruhu lidí vysvětlil základní podstatu své metody. Některé práce jiných vědců [4] [3] [5] [6] pojednávaly o algoritmu, ale žádná neobsahuje podrobnou analýzu. Zajímavé také je, že Shanks ve své metodě vyvozuje poměrně velké množství předpokladů [7] , které bohužel zůstaly bez důkazů. V [8] jsou uvedeny výsledky některých experimentů, které naznačují, že existuje mnoho předpokladů. Nakonec, na základě těchto zjednodušujících předpokladů, byl Shanks schopen vytvořit SQUFOF.

Pomocné definice

Abychom pochopili, jak je tento algoritmus implementován, je nutné znát minimum informací o matematických objektech používaných v této metodě, konkrétně o kvadratických formách . Binární kvadratická forma je polynom ve dvou proměnných a : $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}}.

Shanksova metoda používá pouze neurčité formy . Máme na mysli diskriminant kvadratické formy. Řekneme, že kvadratická forma představuje celé číslo , pokud existují celá čísla taková , že rovnost platí: . Pokud je rovnost pravdivá , pak se reprezentace nazývá primitivní . $\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$

Pro jakýkoli neurčitý kvadratický tvar lze operátor redukce definovat jako: $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}}

, kde je definováno jako celé číslo , jednoznačně určené podmínkami: [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 }}$

Výsledek jednorázového použití operátoru na formulář se zapíše jako . Operátor je také definován jako: $\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}}

, kde je definováno stejným způsobem jako v předchozím případě. Všimněte si, že v důsledku použití operátorů a na kvadratickou formu s diskriminantem budou mít výsledné kvadratické formy také diskriminant .

r(-b,c)

\rho ^{-1}

\rho

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

\Delta

\Delta

Metodu pro získání redukované formy ekvivalentní této metodě nalezl Carl Gauss a spočívá v postupné aplikaci redukčního operátoru, dokud se nezredukuje. $g=\rho (f)$ $F$

Teorém.

Každá forma je ekvivalentní nějaké redukované formě a jakákoli redukovaná forma for je rovna nějaké kladné . Je- li - sníženo, pak je rovněž sníženo. $F$ $F$ $\rho ^{k}(f)$ $k$ $F$ $\rho (f)$

Pro jasné pochopení všech operací s kvadratickými formami potřebujeme také koncepty čtvercových, sousedních a nejednoznačných kvadratických forem.

Možnosti

Myšlenkou Shanksovy metody je porovnat číslo , které se má rozložit, s kvadratickou binární formou s diskriminantem , se kterým se pak provede řada ekvivalentních transformací a přechod z formy do nejednoznačné formy . Potom bude dělitel . $n$ $F$ $D=4n$ $F$ $(a',b',c')$ $\gcd(a',b')$ $n$

První varianta pracuje s pozitivně-definitivními binárními kvadratickými formami daného negativního diskriminantu a ve skupině tříd forem najde ambigovou formu , která dává faktorizaci diskriminantu. Složitost první možnosti je podřízena pravdivosti rozšířené Riemannovy hypotézy . [9] $O(n^{1/5+\varepsilon })$

Druhou variantou je SQUFOF, která využívá třídní skupinu binárních kvadratických forem s kladným diskriminantem. Najde také ambigovou formu a faktorizuje diskriminant. Složitost SQUFOF se rovná aritmetickým operacím; algoritmus pracuje s celými čísly nepřesahujícími . Mezi faktorizačními algoritmy s exponenciální složitostí je SQUFOF považován za jeden z nejúčinnějších. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n))$

Skóre konvergence

Podle výpočtů provedených samotným Shanksem je počet iterací prvního a druhého cyklu algoritmu určen počtem faktorů čísla a je přibližně roven: $w$ $n$

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

kde je konstanta rovna přibližně 2,4 pro první cyklus iterací. [deset] $C$

Popis algoritmu

Podrobněji lze algoritmus zapsat následovně: [11]

Vstup: Liché složené číslo pro rozklad. Pokud nahradíme Now Poslední vlastnost je nutná k tomu, aby determinant kvadratického tvaru byl fundamentální, což zajišťuje konvergenci metody . $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Výstup: Netriviální dělitel . $n$

1. Definujte původní kvadratickou formu , s diskriminantem , kde .

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

D=4n

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

2. Proveďme cyklus zmenšení, dokud se tvar nestane čtvercovým.

f=\rho (f)

F

3. Vypočítejte druhou odmocninu z

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

4. Proveďme cyklus redukcí, dokud se hodnota druhého koeficientu nestabilizuje . Počet iterací této smyčky by se měl přibližně rovnat polovině počtu iterací první smyčky. Poslední hodnota bude dělit dělitel čísla (možná triviální).

p=\rho (g)

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

m

a^{\prime }

n

Implementace algoritmu

Nyní popíšeme algoritmus pro implementaci na počítači. [11] Všimněte si, že ačkoliv teoretická část algoritmu souvisí s ekvivalentními transformacemi kvadratických forem, praktická část algoritmu je založena na výpočtu koeficientů metody spojitého zlomku bez použití forem. Každá iterace smyčky odpovídá jedné operaci aplikace redukčního operátoru na odpovídající formulář. V případě potřeby můžete obnovit odpovídající formuláře pomocí vzorců: $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})$

Vstup: Složené číslo $n$

Výstup: Netriviální dělitel $n$

Inicializace algoritmu.
- Zkontrolujeme, zda je to dokonalý čtverec. Pokud ano, spočítejte a ukončete výpočet. Jinak přejděme k další položce. $n$ $d={\sqrt {n)),$
- Pokud pak nahradíme Define $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Určete počáteční hodnoty parametrů $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}}.$

První 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.$
- Pokračujeme ve výpočtu koeficientů , dokud nenajdeme Q_k, což je dokonalý čtverec. To by se mělo stát v nějakém Let pro celé číslo . Přejděme k dalšímu cyklu. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ $Q_{k}=d^{2}$ $d>0.$

Druhý cyklus.
- začněme cyklus výpočtu nových parametrů Vzorce pro realizaci druhého cyklu zůstanou stejné jako doposud. Změní se pouze počáteční hodnoty parametrů $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 }.$
- Výpočet by měl pokračovat, dokud se dvě po sobě jdoucí hodnoty nebudou rovnat. Hodnota pak dá požadovaný dělitel čísla Popis Shanksova algoritmu je dokončen. ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime ))$ $Q_{j}$ $n.$

Jak již bylo zmíněno, nejedná se o jedinou implementaci tohoto algoritmu. Implementaci algoritmu naleznete také zde [8]

Příklad rozkladu čísla na rozklad

Tuto metodu použijeme k rozkladu čísla [8] $N=22117019$

Cyklus #1
$F_{i}$
$i$	$(-1)^{i-1}Q_{i-1}$	$2\cdot P_{i}$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$jeden$
$jeden$	$jeden$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$čtyři$	${\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}$
$osm$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$deset$	$-4346$	$2\cdot 4331$	$773$
$jedenáct$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$čtrnáct$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$patnáct$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$osmnáct$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Cyklus #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$
$jeden$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$čtyři$	$-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$
$osm$	$-4451$	$2\cdot 4451$	$518$

Nyní můžete ve druhém cyklu vidět, že Proto to číslo $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Aplikace

Tento algoritmus se používá v mnoha implementacích NFS a QS k faktorizaci malých pomocných čísel, která vznikají při faktorizaci velkého celého čísla. V každém případě se SQUFOF používá hlavně jako pomocný algoritmus v výkonnějších faktorizačních algoritmech, a proto bude SQUFOF obecně používán k faktorizaci čísel o malé velikosti, která nemají malé prvočíselníky. Taková čísla jsou obvykle součinem malého počtu různých prvočísel. [8] .

Poznámky

↑ Více informací o historii této metody a jejím spojení s metodou pokračovacího zlomku naleznete v článku Govera a Wagstaffa (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , High Performance Data Mining: Scaling Algorithms, Applications and Systems.
↑ 1 2 Hans Riesel, 1994 , Prvočísla a počítačové metody faktorizace. Birkhauser, druhé vydání.
↑ Henri Cohen, 1996 , Kurz výpočetní algebraické teorie čísel.
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Kryptoanalýza čísel teoretických šifer.
↑ Například ve FAKTORIZÁCI ČTVRTNÝCH FOREM JASON E. GOWER A SAMUEL S. WAGSTAFF, JR. Předpoklad 4.12. na straně 20, Předpoklad 4.5 na straně 16, také při dokazování teorémů o složitosti algoritmu atd.
↑ 1 2 3 4 5 FAKTORIZACE ČTVRTNÝCH FOREM, 2003 , FAKTORIZACE ČTVRTNÝCH FOREM.
↑ 1 2 Vasilenko, 2003 , Číselné teoretické algoritmy v kryptografii.
↑ Ishmukhametov, 2011 , Faktorizační metody pro přirozená čísla: Učebnice.
↑ 1 2 Ishmukhametov, 2011 , Faktorizační metody pro přirozená čísla: Učebnice s. 79-80.

Literatura

Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - Moskva: MTSNMO, 2003. - S. 75 - 76. - 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Ishmukhametov Sh. T. Metody rozkladu přirozených čísel: Učebnice . - Kazaň: Kazaňská univerzita, 2011. - S. 74 - 82. - 190 s.
D.A. Buell. Binární kvadratické formy (neopr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 s. - ISBN 0-387-97037-1 .
Hans Riesel. Prvočísla a počítačové metody faktorizace. Birkhauser, druhé vydání . - Švédsko: Birkhauser, 1994. - S. s. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. Kurz výpočetní algebraické teorie čísel . - Springer-Verlag , 1996. - S. 433 - 437. - 534 s. — ISBN 3-540-55640-0 .
Jason E. Gower a Samuel S. Wagstaff, JR. FAKTORIZACE ČTVERCOVÝCH FOREM . - Moskva: MTSNMO, 2003. - S. 1-16, 35-36. — 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Kryptoanalýza číselných teoretických šifer . - CRC Press , 2003. - 318 s. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. Vysoce výkonné dolování dat : Škálovací algoritmy, aplikace a systémy . - Kluwer Academic Publishers , 1999. - S. 111. - ISBN 0-7923-7745-1 .

Viz také

Faktorizace celých čísel

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin