Factorisointi jatkuvilla murtoluvuilla

Lukuteoriassa jatkuva murtolukujen laskenta ( CFRAC ) on algoritmi kokonaislukujen laskemiseen alkutekijöiksi . Tämä on yleinen algoritmi, joka sopii mielivaltaisen kokonaisluvun kertoimiin . $m$

Jatkuva murtolukumenetelmä perustuu Krajczykin algoritmiin ja käyttää jatkuvaa murtolukua , joka konvergoi jollekin positiiviselle kokonaisluvulle . Jatkettujen jakeiden menetelmän pohjalta rakennettiin Dixon-algoritmi , jonka kaavion mukaan sitten kehitettiin neliöllinen seulamenetelmä [1] . ${\sqrt {km}}$ $k$

Algoritmilla on monimutkaisuus O- ja L - merkinnöissä [2] . $O\left(e^{\sqrt {2\log m\log \log m))\right)=L_{m}\left[{\frac {1}{2)),{\sqrt { 2}}\oikea]$

Historia

Jatkettua fraktiomenetelmää ehdottivat D. G. Lehmer ja R. E. Powers vuonna 1931 [3] . Tämä menetelmä perustui Legendren ja Krajczyk ideoihin ja sen tarkoituksena oli hajottaa suuria lukuja, jotka sisältävät 30 tai enemmän desimaaleja . Saatua menetelmää ei kuitenkaan sovellettu sen toteuttamiseen liittyvien vaikeuksien vuoksi työpöydän lisäyskoneilla [4] .

1960-luvun lopulla John Brillhart huomasi tämän menetelmän soveltuvan hyvin tietokoneohjelmointiin , ja yhdessä Michael A. Morrisonin kanssa työskenteli tämä algoritmi tietokoneille vuonna 1975 [5] .

1970 -luvulla jatketusta murto-osien tekijöiden laskenta-algoritmista tuli paras tapa laskea alkutekijöitä käyttämällä usean tarkkuuden muotoa. Morrisonin ja Brillhartin IBM 360/91 -tietokoneella kirjoittama ohjelma käsitteli mielivaltaisia 25-numeroisia lukuja 30 sekunnissa ja 40-numeroisia lukuja 50 minuutissa. Vuonna 1970 tämän algoritmin avulla tehtiin seitsemännen Fermat-luvun faktorointi [4] :

2^{2^{7}}+1=59649589127497217\cdot 5704689200685129054721.

Menetelmä pysyi suosittuna 1980-luvun alkuun asti , jolloin neliöllinen seulamenetelmä syntyi . Sen jälkeen jatkettujen jakeiden kertoimien menetelmä osoittautui kilpailukyvyttömäksi [6] .

Algoritmin kuvaus

Lehmerin ja Powersin menetelmä

Vuonna 1643 Pierre Fermat ehdotti algoritmia parittoman kokonaisluvun laskemiseksi . Lyhyesti sanottuna tämä algoritmi voidaan kuvata seuraavasti: anna . Sitten voi kirjoittaa $m$ $m=ab$

ab=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {ab}{2}}\right)^{2}=x ^{2}-y^{2}=m

missä . $x={\frac {a+b}{2)),\quad y={\frac {ab}{2))$

Tästä on selvää, että . Tämä tarkoittaa , että jos lajittelemme peräkkäin kokonaislukujen neliöt alkaen yläosaa lähimmästä neliöstä , ero on jossain iteraatiossa yhtä suuri kuin jonkin luvun neliö . Löydetyn lukuparin avulla voit löytää luvun tekijäparin : . $x^{2}-m=y^{2}$ $x$ $m$ $x^{2}-m$ $y$ $(x,y)$ $(a, b)$ $m$ $a={\frac {x+y}{2)),\quad b={\frac {xy}{2))$

Siten Fermatin menetelmä vähentää luvun tekijöiden laskemisen ongelman löytääkseen kokonaisluvut, joiden erotus on yhtä suuri kuin alkuperäinen luku . Fermatin menetelmä löytää nopeasti luvun tekijät, kun sen jakajat ovat lähellä , ts. mahdollisimman epätasaisille numeroille. Jos luku on tasainen , niin Fermatin menetelmä voi toimia jopa hitaammin kuin koejako [2] . $m$ $m$ ${\sqrt {m))$ $m$

Vuonna 1926 Maurice Krajczyk esitteli monografiassa [7] kokonaislukukerroinmenetelmänsä , joka oli Fermatin menetelmän "vahvistus".

Krajczyk ehdotti, että relaatiota tyydyttävien lukuparien sijasta etsitään vertailua tyydyttäviä pareja , ts. . Jos lisäksi , niin saamme vain triviaalin ratkaisun. Kuitenkin jos , niin määritetystä vertailusta käy ilmi , missä . Tämä merkitsee myös hajotusta: se on jaollinen : llä , mutta ei jaollinen kummallakaan :llä tai : llä , joten se on ei-triviaali jakaja [2] (katso #perustelu1 ). $(x,y)$ $x^{2}-y^{2}=m$ $(x,y)$ $x^{2}-y^{2}\equiv 0{\pmod {m))$ $x^{2}\equiv y^{2}{\pmod {m))$ $x\equiv \pm y{\pmod {m}}$ $x\not \equiv \pm y{\pmod {m}}$ $x^{2}-y^{2}=(xy)(x+y)=km$ $k\in \mathbb {Z}$ $m$ $(xy)(x+y)$ $xy$ $x+y$ ${\näyttötyyli \gcd(xy,m)}$ $m$

Krajczykin innovaation jälkeen luvun jakajien löytämisen algoritmi on muuttunut merkittävästi: nyt sinun on edelleen laskettava eri , mutta nyt sinun ei tarvitse "odota" toista neliötä, vaan sinun täytyy yrittää rakentaa se kertomalla saadut luvut [2] . $m$ $x^{2}-m$ $x$ $m$

Todellakin, harkitse muodon (ilmeisesti, ) numerosarjaa . Sitten, jos ts. , siitä seuraa, että [2] . Jotta voidaan määrittää, mitkä suhdeluvut on kerrottava, on tarpeen jakaa luvut tekijöiksi ja kertoa suhdeluvut siten, että tulot sisältävät alkukertoimia parillisina potenssiin, jolloin voit saada vertailun [8] . $\upsilon (u)=u^{2}-m$ $\upsilon \equiv u^{2}{\pmod {m}}$ ${\displaystyle \upsilon (u_{1})\upsilon (u_{2})\dots \upsilon (u_{k})=y^{2))$ ${\näyttötyyli (u_{1}^{2}-m)(u_{2}^{2}-m)\pisteet (u_{k}^{2}-m)=y^{2))$ $x^{2}=u_{1}^{2}u_{2}^{2}\dots u_{k}^{2}\equiv y^{2}{\pmod {m))$ $\upsilon$ ${\displaystyle \upsilon _{1}\upsilon _{2}\dots \upsilon _{k))$ $x^{2}\equiv y^{2}{\pmod {m))$

Krajczykin menetelmä supistaa luvun factoring-ongelman useiden vertailujen ja factoring-lukujen muodostamiseen . Krajczyk ei kuitenkaan esittänyt erityistä algoritmia lukuparien etsimiseen eikä algoritmista tapaa koota muodon [8] vertailurelaatiot löydetyistä suhteista . $m$ $u^{2}\equiv \upsilon {\pmod {m))$ $\upsilon$ $u,\upsilon$ $x^{2}\equiv y^{2}{\pmod {m))$

Vuonna 1931, vuonna [3] , Lemaire ja Powers ehdottivat kahta vaihtoehtoa näiden vertailujen luomiseksi. Molemmat muunnelmat perustuivat suhteisiin, jotka syntyvät neliöllisen irrationaalisuuden laajenemisesta jatkuviksi murto -osiksi , ja niillä oli ominaisuus, että magnitudit eivät ylittäneet [9] . Viimeinen epäyhtälö takaa, että luvut ovat pieniä, mikä helpottaa näiden lukujen hajottamista alkutekijöiksi [2] (ks . #justification2 ). $\upsilon$ $2{\sqrt {m))$ $\upsilon$

Samalla molemmat vaihtoehdot osoittautuvat vastaaviksi [3] : jos yksi algoritmin versio löytää ratkaisun, niin toinenkin versio löytää ratkaisun.

Molemmissa algoritmin versioissa oli kuitenkin haittapuoli - neliöllisen irrationaalisuuden laajeneminen jatkuvaksi murtoluvuksi on jaksollista ( Lagrangen lause ). Siksi tällä menetelmällä saatavien suhteiden määrä on rajallinen, eivätkä ne välttämättä riitä suhteiden asettamiseen ja vertailun muodostamiseen . Samaan aikaan, kuten käytännön kokeet osoittavat, suurilla arvoilla jatkuvaksi murto-osaksi laajentumisjakson pituus osoittautuu riittävän suureksi (luokkaa [10] ) tarvittavan määrän vertailuja varten. Tämän seurauksena suurille algoritmin molemmat versiot löytävät aina luvun tekijöiden jakamisen [ 11] . $x^{2}\equiv y^{2}{\pmod {m))$ $m$ ${\sqrt {m))$ $m$ $m$

Ensimmäinen vaihtoehto

Muista, että jokainen reaaliluku voidaan liittää kokonaislukujonoon , jota kutsutaan sen jatkuvaksi murtoluvuksi . Tämä vertailu on rakennettu seuraavasti $\xi$ $[b_{0},b_{1},b_{2},...]$

x_{0}=\xi ,\quad b_{i}=[x_{i}],\quad x_{i+1}={\frac {1}{x_{i}-b_{i} }},\quad i=0,1,2,\dots .

Jossa $\xi =b_{0}+{\frac {1}{b_{1}+{\frac {1}{b_{2}+{\frac {1}{\pisteet +{\frac {1 }{x_{n}}}}}}}}}=[b_{0},b_{1},b_{2},\dots ,b_{n-1},x_{n}].$

Jos laajennetaan luku jatkuvaksi murtoluvuksi , niin laajennusprosessissa syntyvillä luvuilla on muotoa kokonaisluvut , ja , [12] . $\xi ={\sqrt {m))$ $x_{n}$ $x_{n}={\frac {{\sqrt {m}}+A_{n}}{B_{n}}}$ $A_{n},B_{n}$ $A_{n}<{\sqrt {m))$ $0<B_{n}<2{\sqrt {m))$

Kertoimien yhtälö [3] täyttyy : $A_{n},B_{n}$

A_{n}^{2}+B_{n}B_{n-1}=m.

tämä tarkoittaa

-B_{n}B_{n-1}\equiv A_{n}^{2}{\pmod {m)),\quad n=0,1,\dots \ .\quad \quad \quad \quad(1)

Tuloksena oleva yhtälö on Krajczykin ehdottamassa muodossa ja sitä voidaan soveltaa luvun kertoimiin . $u^{2}\equiv \upsilon {\pmod {m))$ $m$

Laskemalla osamäärät peräkkäin , saamme muodon lausekkeet eri . Jakamalla suureet alkutekijöiksi ja yhdistämällä tuloksena saadut yhtäläisyydet saadaan muotovertailuja (katso #esimerkki1 ). $A_{0},B_{0},A_{1},B_{1},\dots$ $(yksi)$ $n$ $B_{n}$ $x^{2}\equiv y^{2}{\pmod {m))$

Toinen vaihtoehto

Jokaiseen jatkuvaan murto-osaan liitetään rationaalilukujen sarja , joka koostuu sopivista murtoluvuista , jotka on laskettu kaavoilla [3] : ${\frac {P_{n}}{Q_{n}}}=[b_{0},b_{1},\dots ,b_{n-1},b_{n}],n>0$

P_{n+1}=b_{n+1}P_{n}+P_{n-1},\quad Q_{n+1}=b_{n+1}Q_{n}+Q_{ n-1},\quad n\geqslant 0,

P_{0}=b_{0},\quad Q_{0}=P_{-1}=1,\quad Q_{-1}=0

ja pyrkii hajottavaan numeroon. Jos luku jaetaan jatkuvaksi murto -osaksi , relaatio [12] on tosi : $\xi ={\sqrt {m))$

{\displaystyle P_{n-1}^{2}-mQ_{n-1}=(-1)^{n}B_{n))

josta seuraa

P_{n-1}^{2}\equiv (-1)^{n}B_{n}{\pmod {m)),n=1,2,\dots \ .\quad \quad \ quad\quad(2)

Tuloksena olevalla yhtälöllä on muoto ja sitä voidaan käyttää luvun kertoimiin samalla tavalla kuin ensimmäisessä variantissa. $u^{2}\equiv \upsilon {\pmod {m))$ $m$

Algoritmi

Siten Lemairen ja Powersin korjaamalla Krajczykin menetelmällä on seuraava muoto [13] .

Kirjaudu sisään . Yhdistelmänumero . $m$

Poistu . Luvun ei- triviaali jakaja . $s$ $m$

Laajenna jatkuvaksi murto-osaksi. ${\sqrt {m))$
Käytä yhtälöitä tai , hanki joukko muodon vertailuja ja hajota luvut alkutekijöiksi. $(yksi)$ $(2)$ $u^{2}\equiv \upsilon {\pmod {m))$ $\upsilon$
Valitse ne yhtäläisyydet , joiden kertomalla saadaan lukujen laajenemisen tuloksena saatujen alkulukujen parillisten potenssien tulo . Siten saamme muodon suhteen . $u^{2}\equiv \upsilon {\pmod {m))$ $\upsilon$ $x^{2}\equiv y^{2}{\pmod {m))$
Jos , palaa sitten vaiheeseen 3. Jos olemassa oleva suhdeluku ei riitä yhtälön luomiseen , on tarpeen jatkaa luvun laajentamista jatkuvaksi murtoluvuksi ja palata sitten vaiheeseen 2. $x\equiv \pm y{\pmod {m}}$ $x^{2}\equiv y^{2}{\pmod {m))$ ${\sqrt {m))$
Käytä Euclid-algoritmia määrittääksesi . $p=\gcd(xy,m)$

Lemaire ja Powers esittivät työssään, kuinka on mahdollista generoida muotoisia suhteita , mutta he eivät Krajcikin tavoin antaneet algoritmista tapaa koota vertailurelaatioita löydetyistä vertailusuhteista . Tämä ongelma ratkaistiin Morrisonin ja Brillhartin menetelmällä. $u^{2}\equiv \upsilon {\pmod {m))$ $x^{2}\equiv y^{2}{\pmod {m))$

Morrisonin ja Brillhartin menetelmä

1970-luvun alussa Michael Morrison ja John Brillhart ehdottivat artikkelissa [5] omaa algoritmiaan, joka on muunnos Lemairen ja Powersin algoritmin toisesta versiosta. Tällä hetkellä jatkettujen murtolukujen menetelmä ymmärretään juuri Morrisonin ja Brillhartin algoritmiksi.

Suurin ero Morrisonin ja Brillhartin toteuttaman algoritmin ja alkuperäisen version välillä oli menetelmän käyttöönotto vertailun muodostamiseksi algoritmisesti tietyn lomakkeen vertailusarjan perusteella . Tämän menettelyn toteuttamiseksi käytettiin "tekijäpohjan" [11] käsitettä . $x^{2}\equiv y^{2}{\pmod {m))$ $u^{2}\equiv \upsilon {\pmod {m))$

Haemme lukujen tulona siten, että luvun modulon pienin absoluuttinen jäännös on alkulukujen tulo [14] . Sitten samoista alkuluvuista voidaan rakentaa ja . $x$ $u_{i}$ ${\displaystyle u_{i}^{2))$ $m$ $y$

Luonnollisen luvun tekijäkanta (tai tekijäkanta ) on joukko erillisiä alkulukuja , mahdollisesti poikkeuksena , joka voi olla yhtä suuri kuin . Tässä tapauksessa lukua, joka on joukon lukujen potenssien tulo, kutsutaan B-tasaiseksi luvuksi. Olkoon nyt B-sileitä lukuja, olkoon niiden laajennukset vähiten jäännösten itseisarvossa modulo . Laitetaan $m$ $B=\{p_{0},p_{1},\dots ,p_{h}\}$ $p_{i}$ $p_{0}$ ${\näyttötyyli -1}$ $b$ $b^{2}{\bmod {m))$ $B$ $u_{i}$ $\upsilon _{i}=u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij} }$ $m$

{\displaystyle \mathbf {e} _{i}=(e_{i0},e_{i1},\dots ,e_{ih})\in \mathbb {F} _{2}^{h))

missä , on vektoriavaruus kentän GF(2) päällä , joka koostuu nollien joukoista ja mittayksiköistä . $e_{ij}\equiv \alpha _{ij}\mod 2$ ${\displaystyle \mathbb {F} _{2}^{h))$ $h$

Valitsemme luvut niin, että vektorien summa on nolla. Määritellään $u_{i}$ $\mathbf{e}_i$

x=\left(\prod _{i}u_{i}\right){\bmod {m)),\quad y=\prod _{j=0}^{h}p_{j}^ {\gamma _{j))

missä . Sitten . $\gamma _{j}={\frac {1}{2}}\sum _{i}\alpha _{ij}$ $x^{2}\equiv y^{2}{\pmod {m))$

On vielä lisättävä, että Morrisonin ja Brillhartin algoritmin tekijäkanta koostuu niistä modulo-alkuluvuista, jotka ovat neliöjäännös [15] . $p_{i}$ $m$

Algoritmi

Morrisonin ja Brillhartin algoritmi on seuraava [16] .

Kirjaudu sisään . Yhdistelmänumero . $m$

Poistu . Luvun ei- triviaali jakaja . $s$ $m$

1. Muodosta laajennuskanta , jossa ja ovat pareittain erillisiä alkulukuja, modulo , joka on neliöjäännös. $B=\{p_{0},p_{1},\dots ,p_{h}\}$ $p_{0}=-1$ $p_{1},\dots ,p_{h}$ $m$

2. Otetaan kokonaisluvut , jotka ovat sopivien murtolukujen osoittajia tavalliseen jatkuvaan murto -osaan , joka ilmaisee luvun . Näistä osoittajista valitaan luvut, joiden absoluuttiset pienimmät jäännökset modulo ovat B - sileät : $u_{i}$ ${\sqrt {m))$ $h+2$ ${\displaystyle u_{i}^{2))$ $m$

u_{i}^{2}{\bmod {m}}=\prod _{j=0}^{h}p_{j}^{\alpha _{ij}}=\upsilon _{i }

missä . Jokaiseen numeroon liittyy myös indikaattorivektori . $\alpha _{ij}\geqslant 0$ $u_{i}$ $(\alpha _{i0},\alpha _{i1},\dots ,\alpha _{ih})$

3. Etsi (esimerkiksi Gaussin menetelmää käyttäen ) sellainen ei-tyhjä joukko , jossa on XOR - operaatio , , . $K\subseteqq \{1,2,\dots ,h+1\}$ $\oplus _{i\in K}\mathbf {e} _{i}=0$ $\oplus$ $\mathbf {e} _{i}=(e_{i1},e_{i2},\dots ,e_{ih}),e_{ij}\equiv \alpha _{ij}{\pmod {2 }}$ $0\leqslant j\leqslant h$

4. Laita . Sitten . $x\leftarrow \prod _{i\in K}u_{i}{\bmod {m)),\quad y\leftarrow \prod _{j=1}^{h}p_{j}^{ {\frac {1}{2}}\sum _{i\in K}\alpha _{ij}}{\bmod {m}}$ $x^{2}\equiv y^{2}{\pmod {m))$

5. Jos , laita ja palauta tulos: . $x\not \equiv y{\pmod {m))$ $p\leftarrow \gcd(xy,m)$ $s$

Muussa tapauksessa palaa vaiheeseen 3 ja vaihda asetusta . (Yleensä on useita vaihtoehtoja valita joukko samalle tekijäkannalle . Jos kaikki mahdollisuudet on käytetty, niin tekijäkannan kokoa tulee suurentaa).

K

K

B

Tuloksena olevasta algoritmista kehitettiin myöhemmin Dixon- algoritmi , josta poistettiin jatkettujen jakeiden laitteisto [17] . Dixonin algoritmin luomisen jälkeen jatkettujen murtolukujen menetelmä oli itse asiassa Dixonin algoritmi, jossa ehdottoman pienimmän tähteen valintaa jalostettiin [18] . $u_{i}$

Muutamia parannuksia

Anna . Yllä luku laajennettiin jatkuvaksi murto-osaksi . Tämä vaihtoehto on tehokas, kun ja ovat lähellä toisiaan. Kuitenkin mitä suurempi ero numeroiden ja välillä on , sitä aikaa vievämpi algoritmi tulee. Tässä tapauksessa voit sen sijaan laajentaa luvun jatkuvaksi murtoluvuksi , jossa pieni tekijä valitaan siten, että kaikki pienet alkuluvut sisällytetään tekijäkantaan [19] . $m=p\cdot q$ ${\sqrt {m))$ $s$ $q$ $s$ $q$ ${\sqrt {m))$ ${\sqrt {km}}$ $k$

Lisäksi, koska jatkuvien murtolukujen menetelmä on rakennettu Dixon-algoritmin kaavan mukaan, siihen voidaan soveltaa Dixon-algoritmin lisästrategioita .

Perustelut

Seuraava lemma osoittaa, että jos ja verrataan , niin numeroilla ja on yhteisiä jakajia. $x^{2}\equiv y^{2}{\pmod {m))$ $x\not \equiv y{\pmod {m))$ $xy$ $m$

Lemma (tekijämäärityksestä) [20] . Antaa olla pariton yhdistelmäluku ja olla modulo jäännöksiä siten, että ja . Silloin eriarvoisuus täyttyy . $m$ $x,y$ $m$ $x\not \equiv \pm y{\pmod {m}}$ $x^{2}\equiv y^{2}{\pmod {m))$ $1<\gcd(xy,m)<m$

Seuraavat kaksi lausetta ovat keskeisiä jatkuvalle murto-osien tekijöiden laskenta-algoritmille. Ne osoittavat, että on mahdollista löytää lukujono, jonka neliöillä on pienet jäännökset modulo . $u_{i}$ $m$

Lause [21] . Jos , jossa , ovat tavanomaisen jatkuvan murto- osan antaman luvun konvergentteja , niin arvio pätee kaikille . ${\frac {P_{n}}{Q_{n}}}$ ${\näyttötyyli n=1,2,\pisteet }$ $\alpha >1$ $n$ $|P_{n}^{2}-\alpha ^{2}Q_{n}^{2}|<2\alpha$

Seuraus [21] . Olkoon positiivinen luku ei täydellinen neliö ja , jossa , ovat konvergentteja . Sitten ehdottoman pienimmälle jäännökselle (eli tähteen ja välissä sijaitsevalle jäännökselle ) epäyhtälö on tosi , ja . $m$ ${\frac {P_{n}}{Q_{n}}}$ ${\näyttötyyli n=1,2,\pisteet }$ ${\sqrt {m))$ $P_{n}^{2}{\bmod {m))$ $-{\frac {m}{2))$ ${\frac {m}{2}}$ $|P_{n}^{2}{\bmod {m}}|<2{\sqrt {m}}$ $P_{n}^{2}{\bmod {m}}=P_{n}^{2}-mQ_{n}^{2}$

Esimerkkejä

Esimerkki 1 [22]

Otetaan luku tekijöihin Lemairen ja Powersin ensimmäisellä algoritmilla . $m=1081$

1. Laajennamme luvun jatkuvaksi murtoluvuksi ja kirjoitamme luvut taulukkoon saadaksemme muotoa . $\xi ={\sqrt {m}}={\sqrt {1081}}$ $A_{n},B_{n}$ $u^{2}\equiv \upsilon {\pmod {m))$

Taulukko: luvun 1081 kertoimet

i	x i	A i	B i
yksi	${\frac {32+{\sqrt {1081}}}{57}}$	32	57
2	${\frac {25+{\sqrt {1081}}}{8}}$	25	kahdeksan
3	${\frac {31+{\sqrt {1081}}}{15}}$	31	viisitoista
neljä	${\frac {29+{\sqrt {1081}}}{16}}$	29	16
5	${\frac {19+{\sqrt {1081}}}{45}}$	19	45
6	${\frac {26+{\sqrt {1081}}}{9}}$	26	9

2. Kirjoita nyt vertailut kohteelle : $-B_{n}B_{n-1}\equiv A_{n}^{2}{\pmod {m))$ ${\näyttötyyli n=2,3,4,5,6}$

-2^{3}\cdot 3\cdot 19\equiv 25^{2}{\pmod {1081)),

-2^{3}\cdot 3\cdot 5\equiv 31^{2}{\pmod {1081)),

-2^{4}\cdot 3\cdot 5\equiv 29^{2}{\pmod {1081)),

-2^{4}\cdot 3^{2}\cdot 5\equiv 19^{2}{\pmod {1081)),

-3^{4}\cdot 5\equiv 26^{2}{\pmod {1081)).

3. Kerrotaan neljäs ja viides vertailu, saadaan:

(-1)^{2}\cdot 2^{4}\cdot 3^{2}\cdot 5\cdot 3^{4}\cdot 5\equiv 19^{2}\cdot 26^{ 2}{\pmod {1081)),

ja antamalla vastaavat tekijät ja vähentämällä : $3^{2}$

2^{4}\cdot 3^{6}\cdot 5^{2}\equiv 19^{2}\cdot 26^{2}{\pmod {1081))

tai

540^{2}\equiv 494^{2}{\pmod {1081)).

4. Saimme vertailun muotoon , jonka avulla voit löytää luvun 1081 jakajan. Todellakin, . Sitten luvun 1081 toinen jakaja on 47. $x^{2}\equiv y^{2}{\pmod {m))$ $\gcd(540-494,1081)=23$

Esimerkki 2 [23]

Otetaan luku tekijöihin Morrisin ja Brilhartin menetelmällä . $m=21299881$

1. Rakennamme laajennuskannan pienistä alkuluvuista valitsemalla luvut, joiden modulo on neliöjäännös, joka tarkistetaan laskemalla Legendre-symbolit : $m$

\left({\frac {m}{3}}\right)=\left({\frac {m}{5}}\right)=\left({\frac {m}{7}} \right)=\left({\frac {m}{11}}\right)=\left({\frac {m}{19}}\right)=1.

Näin ollen tekijäkanta on yhtä suuri kuin , . ${\displaystyle B=\{-1,2,3,5,7,11,19\))$ $h=6$

2. Etsimme sopivien murtolukujen osoittajia numeroon : $P_{i}$ ${\sqrt {m))$

{\sqrt {m}}=[4615;{5,1,1,2,1,7,1,27,1,6,1,2,12,23,1,8,2,3 ,6,1,1,1,\pisteet }].

Valitsemme ne, joiden arvot ovat B-tasaisia. Laskelmien tulokset on kirjoitettu taulukkoon: $P_{i}^{2}{\bmod {m))$

k	i	Pi_ _	P 2 i ${\pmod {m))$	e i
yksi	2	27691	${\displaystyle -4235=-1\cdot 5\cdot 7\cdot 11^{2))$	(1, 0, 0, 1, 1, 0, 0)
2	3	50767	$2688=2^{7}\cdot 3\cdot 7$	(0, 1, 1, 0, 1, 0, 0)
3	6	1389169	$-7920=-1\cdot 2^{4}\cdot 3^{2}\cdot 5\cdot 11$	(1, 0, 0, 1, 0, 1, 0)
neljä	13	12814433311	$385=5\cdot 7\cdot 11$	(0, 0, 0, 1, 1, 1, 0)
5	16	2764443209657	$-3800=-1\cdot 2^{3}\cdot 5^{2}\cdot 19$	(1, 1, 0, 0, 0, 0, 1)
6	kahdeksantoista	20276855015255	${\displaystyle -1331=-1\cdot 11^{3))$	(1, 0, 0, 0, 0, 1, 0)
7	19	127498600693396	${\displaystyle 5415=3\cdot 5\cdot 19^{2))$	(0, 0, 1, 1, 0, 0, 0)
kahdeksan	24	2390521616955537	$-112=-1\cdot 2^{4}\cdot 7$	(1, 0, 0, 0, 1, 0, 0)

3. Koska , saamme $e_{1}\oplus e_{3}\oplus e_{6}\oplus e_{8}=0$

4. , $x=P_{2}\cdot P_{6}\cdot P_{18}\cdot P_{24}\equiv 12487442{\pmod {m))$

y=2^{4}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{3}\cdot 19^{0}=2236080

x^{2}\equiv y^{2}\equiv 13201055{\pmod {m))

5. Ehto täyttyy, joten laskemme . $x\not \equiv \pm y{\pmod {m}}$ $p=\gcd(xy,m)=\gcd(10251362,21299881)=3851$

Siksi ,. $21299881=3851\cdot 5531$

Laskennallinen monimutkaisuus

RSA - salausjärjestelmän käyttöönoton myötä 1970 -luvun lopulla faktorointialgoritmien laskennallinen monimutkaisuus tuli erityisen tärkeäksi [2] .

R. Schruppel suoritti heuristisen analyysin Morris- ja Brilhart-algoritmin suoritusajasta vuonna 1975 , vaikka sitä ei julkaistu [24] [2] .

Tarkempi arvio (joka jäi silti heuristiseksi) tehtiin vuonna [25] . Esitetään tämän työn mukaiset kompleksisuuden arvioinnin tulokset.

Tässä artikkelissa arvioita saattaessa tehdään joitain heuristisia oletuksia. Oletetaan esimerkiksi, että jos algoritmi muodostaa pareja siten, että , niin ainakin yksi niistä täyttää epäyhtälöt $1+[\log ^{2}m]$ $(x, y)$ $x^{2}\equiv y^{2}{\pmod {m))$

{\näyttötyyli 1<\gcd(x\pm y,m)}

Lausuma [26] . Jos , ja tekijäkanta koostuu ja kaikista alkuluvuista siten, että: ${\displaystyle a={\frac {1}{\sqrt {2))))$ $L=L(m)=\exp((\log m\log \log m)^{1/2})$ $p=-1$ $s$

2\leqslant p\leqslant L^{a},\quad \left({\frac {m}{p}}\right)=+1

sitten laskettaessa suppenevia murtolukuja, joissa , voimme olettaa, että algoritmi jakaantuu kahdeksi tekijäksi heuristisella arviolla aritmeettisten operaatioiden monimutkaisuudesta . ${\näyttötyyli L^{b))$ $b=a+{\frac {1}{4a}}$ $m$ $L_{m}\left[{\frac {1}{2));2\right]$

Katso myös

Muistiinpanot

↑ Knuth, 2013 , s. 439 441.
↑ 1 2 3 4 5 6 7 8 Pomerance, 1996 .
↑ 1 2 3 4 5 Lehmer, Powers, 1931 .
↑ 1 2 Knuth, 2013 , s. 434.
↑ 12 Morrison, Brillhart, 1975 .
↑ Makhovenko, 2006 , s. 223.
↑ Kraitchik M. Theorie des Nombres. Tome I ja II. — Pariisi: Gauthier-Villars. – 1926.
↑ 1 2 Nesterenko, 2012 , s. 173.
↑ Nesterenko, 2012 , s. 175.
↑ Yaschenko, 1999 , s. 113.
↑ 1 2 Nesterenko, 2012 , s. 178.
↑ 1 2 Yashchenko, 1999 , s. 112-113.
↑ Nesterenko, 2012 , s. 173,185.
↑ Manin, 1990 , s. 78.
↑ Makhovenko, 2006 , s. 220.
↑ Makhovenko, 2006 , s. 218-220.
↑ Knuth, 2013 , s. 439.
↑ Makhovenko, 2006 , s. 219.
↑ Yaschenko, 1999 , s. 114.
↑ Nesterenko, 2012 , s. 172.
↑ 1 2 Makhovenko, 2006 , s. 219-220.
↑ Nesterenko, 2012 , s. 176-177.
↑ Makhovenko, 2006 , s. 221-222.
↑ Knuth, 2013 , s. 436.
↑ Pomerance, 1982 .
↑ Vasilenko, 2003 , s. 87.

Kirjallisuus

Lehmer D. H. , Powers R. E. On factoring large numbers // Bull . , New Ser., Am. Matematiikka. soc. / S. Friedlander - Providence, RI : American Mathematical Society , 1931. - Voi. 33, Iss. 1. - s. 35-36. — ISSN 0273-0979 ; 1088-9485 - doi:10.1090/S0002-9904-1931-05271-X
Morrison M. A. , Brillhart J. Factoring-menetelmä ja F₇:n faktorointi // Math . Comp. - AMS , 1975. - Voi. 29, Iss. 129. - s. 183-205. — ISSN 0025-5718 ; 1088-6842 - doi: 10.2307/2005475
Pomerance C. Joidenkin kokonaislukufaktorointialgoritmien analyysi ja vertailu (englanniksi) // Computational Methods in Number Theory : Osa I / H. Lenstra , R. Tijdeman - Amsterdam : Mathematisch Centrum , 1982. - P. 89-139.
Manin, Yu. I., Panchishkin, A. A. Luku 3.4. Jatkuvien murtolukujen menetelmä (CFRAC) ja todelliset toisen asteen kentät // Johdatus lukuteoriaan, lukuteoria - 1 . — Tieteen ja tekniikan tulokset. Ser. Moderni prob. matto. Fundam. ohjeita. - M .: VINITI , 1990. - T. 49. - S. 77-80. — 341 s.
Pomerance C. Tarina kahdesta seulasta // Huomautuksia Amer . Matematiikka. soc. / F. Morgan - AMS , 1996. - Voi. 43. - P. 1473-1485. — ISSN 0002-9920 ; 1088-9477
Johdatus kryptografiaan / Yashchenko, V.V. - Moskova: MTsNMO , 1999. - 272 s. - ISBN 5-900916-40-5 .
Koblitz N. Lukuteorian ja kryptografian kurssi - 2. painos - M . : Tieteellinen kustantaja TVP , 2001. - S. 174-179. — 254 s. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa - M .: MTsNMO , 2003. - 328 s. — ISBN 978-5-94057-103-2
Makhovenko E. B. Lukuteoreettiset menetelmät kryptografiassa - M .: Helios ARV , 2006. - P. 219-222. — ISBN 978-5-85438-143-7
Nesterenko A. Yu. Numeroteoreettiset menetelmät kryptografiassa - Moskova : Moskovan osavaltion elektroniikan ja matematiikan instituutti , 2012. - P. 172-186. — 224 s. — ISBN 978-5-94506-320-4
Knut D. E. Ohjelmoinnin taito - 3. painos - Williams , 2013. - V. 2. Saadut algoritmit. — 832 s. — ISBN 978-5-8459-0081-4