Lenstra elliptinen käyrä tekijöihin

Lenstra elliptinen käyrä tekijöihinjako tai elliptinen käyrä tekijöihinjakoalgoritmi menetelmä on nopea, osa-eksponentiaalinen aika algoritmi kokonaisluku tekijöihin joka työllistää elliptinen käyrät. Yleiskäyttöön factoring, ECM on kolmanneksi nopein tiedossa factoring menetelmällä. Toiseksi nopein on useita polynomi asteen seula ja nopein on yleinen numero kenttään seula. Lenstra elliptinen käyrä tekijöihin on nimetty Hendrik Lenstran.

Käytännöllisesti katsoen ECM katsotaan erityistä tarkoitusta varten factoring algoritmi, koska se on sopivin löytää pieniä tekijöitä. Tällä hetkellä se on edelleen paras algoritmi jakajia ei suuresti ylitä 20-25 numeroa, koska sen aika hallitsee koko pienimmän tekijän s eikä koko luku n laskettaisi. Usein, ECM käytetään poistamaan pieniä tekijöiden erittäin suuri kokonaisluku kanssa monia tekijöitä; jos jäljellä kokonaisluku on edelleen komposiitti, niin se on vain iso tekijät ja on laskelmiin käyttäen yleiskäyttöinen tekniikoita. Suurin tekijä löytyi käyttäen ECM toistaiseksi on 83 numeroa ja havaittiin 7. syyskuuta 2013 R. Propper. Määrän lisääminen käyrät testattu parantaa mahdollisuuksia löytää tekijä, mutta ne eivät ole lineaarisia kasvaessa numeroiden määrä.

Lenstra n elliptinen käyrä tekijöihin

Lenstra elliptinen käyrä tekijöihinjako menetelmä löytää tekijä antanut luonnollinen luku toimii seuraavasti:

  • Valitse satunnainen elliptinen käyrä yli, jossa yhtälö muodossa yhdessä ei-triviaali kohta se.
  • Lisäys "P ja Q pistettä yleensä määrittelee konsernin toiminnalle P ⊕ Q käyrä joiden tuote voidaan laskea annettujen kaavojen artikkelissa ellipsinmuotoinen käyriä.
  • Laskea EP elliptisellä käyrällä, jossa e on tuote monien pienien: sanoa, tuote pienten alkulukujen nostetaan pieni toimivaltaa, kuten p - 1-algoritmin, tai kertoma B! joillekin ole liian suuri B. Tämä voidaan tehdä tehokkaasti, yksi pieni tekijä kerrallaan. Sano, saada B! P, ensin laskea 2P, sitten 3 ja sitten 4, ja niin edelleen. Tietenkin, B pitäisi olla niin pieni, että B-viisas ⊕-lisäys voidaan suorittaa kohtuullisessa ajassa.
    • Jos pystyimme lopettaa kaikki laskelmat edellä kohtaamatta kuin käännettävissä osia, meidän täytyy yrittää uudelleen joidenkin muiden käyrä ja lähtökohta.
    • Jos jossain vaiheessa löysimme kP = ∞, meidän pitäisi aloittaa alusta uusi käyrä ja lähtökohta, koska tämä kohta on ryhmä ykkösalkio, joten ei muutu näin enää summausoperaatiot.
    • Jos kohtasimme syt jossain vaiheessa, että ei ollut 1 eikä n, niin olemme tehneet: se on ei-triviaali tekijä n.

Aika monimutkaisuus riippuu koosta tekijän ja se voidaan esittää exp) √), jossa p on pienin tekijä n, tai L-merkintää.

Miksi algoritmi toimii?

Jos p ja q ovat kahden alkutekijät n, niin y = x + ax + b merkitsee samaa yhtälöä myös modulo p ja modulo q. Nämä kaksi pienempää elliptinen käyrät -addition ovat nyt aitoja ryhmiä. Jos näillä ryhmillä on Np ja Nq elementtejä, vastaavasti, sitten tahansa P alkuperäisen käyrän, jonka Lagrangen lause, K & gt; 0 on minimaalinen niin, että käyrällä modulo p merkitsee sitä, että k jakaa Np; lisäksi ,. Analoginen lausunto pätee käyrä modulo q. Kun elliptinen käyrä on valittu satunnaisesti, sitten Np ja Nq ovat satunnaisia ​​numeroita lähellä p + 1 ja q + 1, vastaavasti. Siksi on epätodennäköistä, että suurin osa alkutekijät Np ja Nq ovat samat, ja on varsin todennäköistä, että vaikka tietotekniikka eP, tulemme kohtaamaan joitakin kP että on ∞ modulo p mutta ei modulo q, tai päinvastoin. Kun näin on, KP ei löydy alkuperäisen käyrän, ja laskelmat löysimme vastaan ​​joko syt = p tai syt = q, mutta ei molempia. Eli syt antoi ei-triviaali tekijä n.

ECM on sen ytimessä parantaa iäkkäiden p - 1-algoritmia. P - 1-algoritmia löytää alkutekijät p siten, että p - 1 on b-powersmooth pieniä arvoja b. Mistään e, useita p - 1, ja kaikki suhteellisen prime p, jonka Fermat'n pieni lause meillä ≡ 1. Tällöin syt todennäköisesti tuottaa tekijä n. Kuitenkin algoritmi epäonnistuu, kun p - 1 on iso alkutekijöitä, kuten on laita numeroiden sisältää vahvoja alkulukuja, esimerkiksi.

ECM saa kiertää tämän esteen harkitsemalla ryhmä satunnainen elliptisen käyrän yli äärellisen Zp, pikemminkin kuin ottaen multiplikatiivisessa ryhmä Zp joka on aina jotta s - 1.

Järjestys ryhmä elliptisen käyrän yli Zp vaihtelee p + 1 - 2√p ja p + 1 + 2√p Hasse lause, ja on todennäköisesti sileä joillekin elliptisiin käyriin. Vaikka ei ole näyttöä siitä, että tasainen ryhmä tilaus löytyvät Hasse-intervalli, käyttäen heuristisia todennäköisyyspohjaista menetelmiä, Canfield-Erdős-Pomerance lause sopivasti optimoitu parametri valintoja, ja L-merkintä, voimme odottaa kokeilla L käyrät ennen saada tasainen ryhmä järjestyksessä. Tämä heuristisia arvio on hyvin luotettava käytännössä.

Esimerkki

Seuraava esimerkki on Trappe & amp; Washington, joitakin yksityiskohtia lisätty.

Haluamme tekijä n = 455839. Valitaan elliptinen käyrä y = x + 5x - 5, jossa pisteen P = sitä, ja yritetään laskea P.

Ensin lasketaan 2P. Kulmakerroin tangentin P on s = / = 4, ja sitten koordinaatit 2P = ovat ja = 4-1 = -53, kaikki numerot ymmärretty. Vain tarkistaa, 2P on todellakin käyrällä: = 2809 = 14 + 5 · 14-5.

Sitten laskemme 3. Tangentin kulmakerroin linjan 2P on s = / (2) = -593/106. Eukleideen algoritmi: 455839 = 4300 · 106 + 39, sitten 106 = 2 · 39 + 28, sitten 39 = 28 + 11, sitten 28 = 2 · 11 + 6, sitten 11 = 6 + 5, sitten 6 = 5 + 1. Täten syt = 1, ja työ taaksepäin: 1 = 6-5 = 2 · 6-11 = 2 · 28-5 · 11 = 7 · 28-5 · 39 = 7 · 106-19 · 39 = 81707 · 106 - 19 · 455839. Näin ollen 106 = 81707, ja -593/106 = -133317. Koska tämä s, voimme laskea koordinaatit 2, kuten teimme edellä: 4P =. Vain tarkistaa, että tämä on todellakin käyrän: y = 54514 = x + 5x - 5. Tämän jälkeen voidaan laskea.

Voimme samalla laskea 4! P, ja niin edelleen, mutta 8! P vaatii kääntelemällä 599. Eukleideen algoritmi antaa joka 455839 on jaollinen 599, ja olemme löytäneet tekijöihinjako 455839 = 599 · 761.

Syy siihen, että tämä toimi on, että käyrä on 640 = 2 · 5 pistettä, kun se on 777 = 3 · 7 · 37 pistettä. Lisäksi 640 ja 777 ovat pienimpiä positiivisia kokonaislukuja k siten, että kP = ∞ käyrän ja vastaavasti. Koska 8! on moninkertainen 640 mutta ei jaollinen 777, meillä on 8! P = ∞ käyrän, mutta ei käyrällä, joten toistuva lisäksi hajosi täällä, saadaan tekijöihin.

Algoritmi projektiivinen koordinaatit

Ennen kuin tarkastellaan projektiivisen kone yli / ~, ensin harkittava "normaali" projective tilaa yli ℝ: sijasta pistettä, linjojen läpi alkuperää tutkitaan. Linja voidaan esittää ei-nollapiste, alle ekvivalenssirelaatio ~ antama: ~ ⇔ ∃ c ≠ 0 siten, että x "= cx, y '= CY ja z' = CZ. Tämän ekvivalenssirelaatio, tilaa kutsutaan projektiivinen kone; pistettä, merkitään, vastaavat rivit kolmiulotteisessa tilassa, jotka kulkevat alkuperä. Huomaa, että kohta ei ole tässä tilassa, koska vetää raja kaikin mahdollisin suuntaan edellyttää vähintään yksi x ', y' tai Z '≠ 0. Nyt huomauttavat, että lähes kaikki linjat menevät läpi tiettynä vertailutaso - kuten suuntainen, kun taas linjat juuri tämän tason suuntaisesti, joiden koordinaatit, määritä suuntiin ainutlaatuisen, kuten "pistettä ääretön", joita käytetään affiini suuntainen se yläpuolella.

Vuonna algoritmi, vain ryhmän rakenteen, elliptisen käyrän kentän ℝ käytetään. Koska emme välttämättä tarvitse kenttä ℝ, äärellisen tarjoaa myös konsernirakenteessa elliptisellä käyrällä. Ottaen kuitenkin huomioon sama käyrä ja toiminta yli / ~ kanssa ei prime ei anna ryhmä. Elliptinen käyrä menetelmä hyödyntää vajaatoimintatapaukset lisäyksen lakia.

Nyt todeta algoritmin projective koordinaatit. Neutraali elementti on tällöin pisteen äärettömään. Antaa oltava kokonaisluku ja harkita elliptinen käyrä.

  • Pick kaupungissa.
  • Laske. Elliptinen käyrä on sitten Weierstrass muodossa antama ja käyttämällä projektiivinen koordinoi elliptinen käyrä saadaan homogeeninen yhtälö. Se on piste.
  • Valitse suurimpina tämän elliptinen käyrä. Huomautus: Voit vain löytää tekijöitä jos ryhmä järjestystä elliptinen käyrä yli on B-sileä, mikä tarkoittaa, että kaikki alkutekijät # täytyy olla pienempi tai yhtä suuri.
  • Laske.
  • Laske kehässä. Huomaa, että jos # on-sileän ja on alkuluku että. Jos kuitenkin vain # on B-sileä joillekin jakaja, tuote ei ehkä ole, koska ja kertolaskua eivät ole hyvin määritelty, jos ei ole alkuluku. Tässä tapauksessa ei-triviaali jakaja löytyy.
  • Jos ei, palaa vaiheeseen 2. Jos näin tapahtuu, niin huomaat tämän yksinkertaistamiskehityksessä tuote.

5 kohdassa sanotaan, että oikeissa olosuhteissa ei-triviaali jakaja löytyy. Kuten vuonna Lenstra artikkelissa lisäksi tarvitsee oletus. Jos eivät ole, ja selvä, sitten lisäksi toimii seuraavasti:

  • Laskea :,,
  • ,
  • ,
  • ,
  • .

Jos lisäksi epäonnistuu, tämä johtua vika laskettaessa. Erityisesti koska ei aina voida laskea, jos ei ole alkuluku. Turvautumatta että kenttä, voisi laskea:

  • ,
  • ,
  • ,
  • , Ja yksinkertaistaa mahdollisuuksien.

Tämä laskelma on aina laillinen ja jos syt on -coordinate kanssa ≠, joten kun yksinkertaistaa epäonnistuu, ei-triviaali tekijä, löytyy.

Twisted Edwards käyrät

Käyttö Edwards käyrät tarvitsee vähemmän modulaarinen kertolaskua ja vähemmän aikaa kuin käyttämällä Montgomery käyriä tai Weierstrass käyriä. Käyttämällä Edwards käyrät voit myös löytää enemmän alkulukuja.

Määritelmä: Antaa olla alalla, jossa, ja anna kanssa. Sitten kierretty Edwards käyrä saadaan Edwards käyrä on kierretty Edwards käyrä, jossa.

On viisi tunnettuja tapoja rakentaa joukko pisteen Edwards käyrä: joukko affiini pistettä, joukko projective pistettä, joukko käänteisen pistettä, joukko laajennettu pistettä ja joukko suoritettujen pistettä.

Joukko Affiininen pisteitä annetaan :.

Lisäksi laki annetaan. Kohta on sen neutraali elementti ja negatiivinen on. Muut esitykset määritellään samaan tapaan projektiivinen Weierstrass käyrä seuraa affine.

Mikä tahansa elliptinen käyrä Edwards muodossa on työjärjestyspuheenvuoro 4. Joten vääntö ryhmä Edwards käyrä yli on isomorfinen joko tai.

Mielenkiintoisin tapauksissa ECM ovat ja, koska ne pakottavat ryhmä tilaukset käyrän modulo pohjustaa olla jaollinen 12 ja 16 vastaavasti. Seuraavat käyrät on vääntö ryhmä isomorfinen:

  •  kärjellä missä ja
  •  kärjellä missä ja

Jokainen Edwards käyrä työjärjestyspuheenvuoron 3 voidaan kirjoittaa tavoin yllä. Käyrät vääntö ryhmä isomorfinen ja löytyvät sivun alkuun 30.

Vaihe 2

Ylläoleva teksti on noin ensimmäinen vaihe elliptisen käyrän tekijöihin. Siellä toivoo löytävänsä prime jakaja niin, että on neutraali elementti. Toisessa vaiheessa yksi toivoo löytänyt prime jakaja niin, että on pieni prime järjestyksessä.

Toivomme ollakseen välillä ja, jossa määritetään vaiheessa 1 ja on uusi vaihe 2 parametri. Tarkistetaan pieni järjestyksessä, voidaan tehdä laskemalla modulo jokaista prime.

Menestys todennäköisyys käyttäen EECM-MPFQ

Saat SpeedUp tekniikoita käyttäen Edward käyriä ja täytäntöönpanon tulokset, katso: sivut 30-32.

Hyperelliptic käyrä menetelmä

On viimeaikainen kehitys käyttäen hyperelliptic kaarteissa tekijä kokonaislukuja. Cosset osoittaa artikkelissaan, että voidaan rakentaa hyperelliptic käyrä suvun kaksi, joka antaa saman tuloksen kuin kahdella "normaali" elliptisten käyrien samanaikaisesti. Hyödyntämällä Kummer Pinta laskelma on tehokkaampaa. Haitat hyperelliptic käyrän kompensoidaan tällä vaihtoehtoinen tapa laskea. Siksi Cosset karkeasti väittää, että käyttämällä hyperelliptic käyrät tekijöihinjako ei ole huonompi kuin käyttämällä elliptisiin käyriin.

  0   0
Edellinen artikkeli KTSM-TV
Seuraava artikkeli Henry Peacham

Aiheeseen Liittyvät Artikkelit

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha