Lenstra elliptik-egri faktorizatsiya - Lenstra elliptic-curve factorization

The Lenstra elliptik-egri faktorizatsiya yoki elliptik-egri faktorizatsiya usuli (ECM) tezkor, pastkieksponent ish vaqti, uchun algoritm tamsayı faktorizatsiyasi, ish bilan ta'minlangan elliptik egri chiziqlar. Uchun umumiy maqsad faktoring, ECM ma'lum bo'lgan uchinchi tezkor faktoring usuli. Ikkinchi eng tezkor ko'p polinomli kvadratik elak, va eng tezkor umumiy sonli elak. Lenstra elliptik-egri faktorizatsiyasi nomi berilgan Xendrik Lenstra.

Amaliy ma'noda ECM maxsus faktoring algoritmi hisoblanadi, chunki u kichik omillarni topish uchun eng mos keladi. Hozirda^[yangilash], bu hali ham eng yaxshi algoritm bo'linuvchilar 50 dan 60 gacha raqamlar, chunki uning ishlash vaqti eng kichik omil kattaligiga bog'liq p raqamning kattaligi bilan emas n hisobga olinishi. Ko'pincha ECM ko'plab omillarga ega bo'lgan juda katta butun sondan kichik omillarni olib tashlash uchun ishlatiladi; agar qolgan tamsayı hali ham kompozitsiyali bo'lsa, unda u faqat katta omillarga ega va umumiy maqsadlar texnikasi yordamida aniqlanadi. Hozirgacha ECM yordamida topilgan eng katta omil 83 ta o'nli raqamga ega va 2013 yil 7 sentyabrda R. Propper tomonidan kashf etilgan.^[1] Tekshirilgan egri chiziqlar sonining ko'payishi omilni topish imkoniyatini yaxshilaydi, ammo bunday emas chiziqli raqamlar sonining ko'payishi bilan.

Algoritm

Berilgan natural sonning koeffitsientini topish uchun Lenstra elliptik-egri faktorizatsiya usuli ${ displaystyle n}$ quyidagicha ishlaydi:

1. Tasodifiy tanlang elliptik egri chiziq ustida ${ displaystyle mathbb {Z} / n mathbb {Z}}$, shaklning tenglamasi bilan ${ displaystyle y ^ {2} = x ^ {3} + ax + b { pmod {n}}}$ ahamiyatsiz bilan birga nuqta ${ displaystyle P (x_ {0}, y_ {0})}$ ustida.

   Buni avval tasodifiy tanlash orqali amalga oshirish mumkin ${ displaystyle x_ {0}, y_ {0}, a in mathbb {Z} / n mathbb {Z}}$va keyin sozlash ${ displaystyle b = y_ {0} ^ {2} -x_ {0} ^ {3} -ax_ {0} { pmod {n}}}$ nuqta egri chiziqda ekanligiga ishonch hosil qilish.

2. Biror narsani aniqlash mumkin Qo'shish egri chiziqdagi ikkita nuqtadan, a ni aniqlash uchun Guruh. Qo'shimcha qonunlar elliptik egri chiziqlar bo'yicha maqola.

   Nuqtaning takrorlangan ko'paytmalarini hosil qilishimiz mumkin ${ displaystyle P}$: ${ displaystyle [k] P = P + ldots + P { text {(k marta)}}}$. Qo'shish formulalari akkord qo'shilishining modul moyilligini olishni o'z ichiga oladi ${ displaystyle P}$ va ${ displaystyle Q}$va shu tariqa modul qoldiq sinflari o'rtasida bo'linish ${ displaystyle n}$yordamida ishlatilgan kengaytirilgan evklid algoritmi. Xususan, ba'zilar tomonidan bo'linish ${ displaystyle v { bmod {n}}}$ ga hisoblashni o'z ichiga oladi ${ displaystyle gcd (v, n)}$.

   Shaklning qiyaligini hisoblaymiz ${ displaystyle u / v}$ bilan ${ displaystyle gcd (u, v) = 1}$, keyin bo'lsa ${ displaystyle v = 0 { bmod {n}}}$, nuqta qo'shishning natijasi bo'ladi ${ displaystyle infty}$, "vertikal" chiziqning birlashuviga to'g'ri keladigan "cheksizlikda" nuqta ${ displaystyle P (x, y), P '(x, -y)}$ va egri. Ammo, agar ${ displaystyle gcd (v, n) neq 1, n}$, keyin nuqta qo'shilishi egri chiziq bo'yicha mazmunli nuqta hosil qilmaydi; lekin, eng muhimi, ${ displaystyle gcd (v, n)}$ ning ahamiyatsiz omilidir ${ displaystyle n}$.

3. Hisoblash ${ displaystyle [k] P}$ elliptik egri chiziqda (${ displaystyle { bmod {n}}}$), qaerda ${ displaystyle k}$ ko'plab kichik sonlarning hosilasi: masalan, kichik kuchlarga ko'tarilgan kichik sonlar mahsuloti p-1 algoritmi yoki faktorial ${ displaystyle B!}$ ba'zilari uchun juda katta emas ${ displaystyle B}$. Buni bir vaqtning o'zida bitta kichik omil samarali bajarish mumkin. Qabul qilish uchun ayting ${ displaystyle [B!] P}$, birinchi hisoblash ${ displaystyle [2] P}$, keyin ${ displaystyle [3] ([2] P)}$, keyin ${ displaystyle [4] ([3!] P)}$, va hokazo. ${ displaystyle B}$ etarlicha kichik bo'lishi uchun tanlangan ${ displaystyle B}$-qismni qo'shish oqilona vaqt ichida amalga oshirilishi mumkin.
   • Agar yuqoridagi barcha hisob-kitoblarni qaytarib bo'lmaydigan elementlarga duch kelmasdan tugatsak (${ displaystyle { bmod {n}}}$), bu elliptik egri chiziqlar (modulli tublar) tartibi emasligini anglatadi silliq etarli, shuning uchun biz boshqa bir egri va boshlang'ich nuqtasi bilan qayta urinib ko'rishimiz kerak.
   • Agar biz duch kelsak ${ displaystyle gcd (v, n) neq 1, m}$ biz tugatdik: bu ahamiyatsiz bo'lmagan omil ${ displaystyle n}$.

Vaqtning murakkabligi raqamning eng kichik asosiy omili kattaligiga bog'liq va u bilan ifodalanishi mumkin exp [(√2 + o (1)) √lnp ln lnp], qayerda p ning eng kichik omilidir n, yoki ${ displaystyle L_ {p} left [{ frac {1} {2}}, { sqrt {2}} right]}$, yilda L-yozuvlar.

Algoritm nima uchun ishlaydi?

Agar p va q ning ikkita asosiy bo'luvchisi n, keyin y² = x³ + bolta + b (modn) xuddi shu tenglamani ham nazarda tutadi modulp va modulq. Ushbu ikkita kichik elliptik egri chiziqlar ${ displaystyle boxplus}$- qo'shimchalar endi haqiqiydir guruhlar. Agar ushbu guruhlarda bo'lsa N_p va N_q mos ravishda elementlar, keyin har qanday nuqta uchun P asl egri chiziqda, tomonidan Lagranj teoremasi, k > 0 minimaldir ${ displaystyle kP = infty}$ egri modulda p shuni anglatadiki k ajratadi N_p; bundan tashqari, ${ displaystyle N_ {p} P = infty}$. O'xshash bayonot egri modul uchun amal qiladi q. Elliptik egri chiziq tasodifiy tanlanganda, keyin N_p va N_q yaqin tasodifiy sonlar p + 1 va q + 1, navbati bilan (pastga qarang). Demak, asosiy omillarning aksariyati bo'lishi ehtimoldan yiroq emas N_p va N_q bir xil, va ehtimol hisoblash paytida eP, ba'zilariga duch kelamiz kP bu ∞ modulp lekin emas modulq, yoki aksincha. Agar shunday bo'lsa, kP asl egri chiziqda mavjud emas va hisoblashlarda biz ba'zi birlarini topdik v ham gcd (v,p) = p yoki gcd (v, q) = q, lekin ikkalasi ham emas. Anavi, gcd (v, n) ahamiyatsiz omil berdi ningn.

ECM yoshi kattaroqni takomillashtirishdir p − 1 algoritm. The p − 1 algoritm asosiy omillarni topadi p shu kabi p − 1 bu b-kuchlar yumshoq ning kichik qiymatlari uchun b. Har qanday kishi uchun e, ning ko'paytmasi p − 1, va har qanday a nisbatan asosiy ga p, tomonidan Fermaning kichik teoremasi bizda ... bor a^e ≡ 1 (mod p). Keyin gcd (a^e − 1, n) omilini keltirib chiqarishi mumkin n. Biroq, algoritm qachon amalga oshmaydi p - 1 o'z ichiga olgan raqamlarda bo'lgani kabi katta asosiy omillarga ega kuchli sonlar, masalan.

ECM ushbu to'siqni ko'rib chiqish orqali o'tadi guruh tasodifiy elliptik egri chiziq ustidan cheklangan maydon Z_pdeb o'ylash o'rniga multiplikativ guruh ning Z_p har doim tartibga ega bo'lganp − 1.

Elliptik egri chiziq guruhining tartibi tugadi Z_p o'rtasida o'zgarib turadi (juda tasodifiy) p + 1 − 2√p va p + 1 + 2√p tomonidan Xassening teoremasi, va ba'zi bir elliptik egri chiziqlar uchun silliq bo'lishi mumkin. Dan foydalanib, Hasse-oralig'ida silliq guruh tartibini topishiga hech qanday dalil yo'q evristik ehtimollik usullari Kanfild-Erdes-Pomerans teoremasi mos ravishda optimallashtirilgan parametr tanlovi bilan va L-yozuvlar, biz sinab ko'rishni kutishimiz mumkin L[√2/2, √2] silliq guruh buyurtmasini olishdan oldin egri chiziqlar. Ushbu evristik taxmin amalda juda ishonchli.

Misol

Quyidagi misol Trappe va Vashington (2006), ba'zi tafsilotlar qo'shilgan.

Biz omil qilmoqchimiz n = 455839. Keling, elliptik egri chiziqni tanlaymiz y² = x³ + 5x – 5, nuqta bilan P = (1, 1) ustiga, va keling, hisoblashga harakat qilaylik (10!)P.

Tegishli chiziqning qaysidir nuqtadagi qiyaligi A=(x, y) s = (3x² + 5)/(2y) (mod n). Foydalanish s biz 2 ni hisoblashimiz mumkinA. Agar qiymati s shakldadir a / b qayerda b > 1 va gcd (a,b) = 1, biz topishimiz kerak modulli teskari ning b. Agar u mavjud bo'lmasa, gcd (n,b) ning ahamiyatsiz omilidir n.

Avval biz hisoblash 2P. Bizda ... bor s(P) = s(1,1) = 4, shuning uchun koordinatalari 2P = (x ′, y) bor x ′ = s² – 2x = 14 va y = s(x – x ′) – y = 4(1 – 14) – 1 = –53, barcha raqamlar tushunilgan (mod n). Buni tekshirish uchun faqat 2P haqiqatan ham egri chiziqda: (–53)² = 2809 = 14³ + 5·14 – 5.

Keyin biz 3 (2) ni hisoblaymizP). Bizda ... bor s(2P) = s(14, -53) = –593/106 (mod n). Dan foydalanish Evklid algoritmi: 455839 = 4300·106 + 39, keyin 106 = 2·39 + 28, keyin 39 = 28 + 11, keyin 28 = 2·11 + 6, keyin 11 = 6 + 5, keyin 6 = 5 + 1. Shuning uchun gcd (455839, 106) = 1, va orqaga qarab ishlash (ning versiyasi kengaytirilgan evklid algoritmi ): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Shuning uchun 106⁻¹ = 81707 (mod 455839), va –593/106 = –133317 (mod 455839). Buni hisobga olgan holda s, biz 2 (2) koordinatalarini hisoblashimiz mumkinP), xuddi yuqoridagi kabi: 4P = (259851, 116255). Buning haqiqatan ham egri chiziq ekanligini tekshirish uchun: y² = 54514 = x³ + 5x - 5 (mod 455839). Shundan so'ng biz hisoblashimiz mumkin ${ displaystyle 3 (2P) = 4P boxplus 2P}$.

Biz xuddi shunday 4 ni hisoblashimiz mumkin!Pva hokazo, lekin 8!P invert qilishni talab qiladi 599 (mod 455839). Evklid algoritmi 455839 ning 599 ga bo'linishini beradi va biz a ni topdik faktorizatsiya 455839 = 599 · 761.

Buning natijasi bu egri chiziq (mod 599) bor 640 = 2⁷·5 ball, esa (mod 761) u bor 777 = 3·7·37 ochkolar. Bundan tashqari, 640 va 777 eng kichik musbat sonlardir k shu kabi kP = ∞ egri chiziqda (mod 599) va (mod 761), navbati bilan. Beri 8! bizda mavjud bo'lgan 640-ning ko'paytmasi, ammo 777-ning ko'paytmasi emas 8!P = ∞ egri chiziqda (mod 599), lekin egri chiziqda emas (mod 761), shuning uchun takroriy qo'shimchalar bu erda buzilib, faktorizatsiyani keltirib chiqardi.

Projektiv koordinatalari bo'lgan algoritm

Proektiv tekislikni ko'rib chiqishdan oldin ${ displaystyle ( mathbb {Z} / n mathbb {Z}) / sim,}$ avval "normal" ni ko'rib chiqing proektsion maydon ℝ dan yuqori: nuqtalar o'rniga kelib chiqishi orqali chiziqlar o'rganiladi. Chiziq nolga teng bo'lmagan nuqta sifatida ifodalanishi mumkin ${ displaystyle (x, y, z)}$, ekvivalentlik munosabati ostida ~ tomonidan berilgan: ${ displaystyle (x, y, z) sim (x ', y', z ')}$ ⇔ ∃ v ≠ 0 shunday x '= vx, y '= vy va z '= vz. Ushbu ekvivalentlik munosabati ostida bo'shliq deyiladi proektsion tekislik ${ displaystyle mathbb {P} ^ {2}}$; bilan belgilanadigan punktlar ${ displaystyle (x: y: z)}$, kelib chiqishi orqali o'tadigan uch o'lchovli kosmosdagi chiziqlarga mos keladi. E'tibor bering, nuqta ${ displaystyle (0: 0: 0)}$ Bu bo'shliqda mavjud emas, chunki har qanday yo'nalishda chiziq chizish uchun kamida x ', y' yoki z '≠ 0 dan bittasi kerak bo'ladi. Endi deyarli barcha chiziqlar har qanday berilgan tekislik orqali o'tishini kuzatib boring, masalan (X,Y, 1) samolyot, bu tekislikka parallel ravishda chiziqlar, koordinatalari (X, Y, 0), yo'nalishlarni affinada ishlatiladigan "cheksiz nuqtalar" sifatida noyob tarzda belgilang (X, Y) - samolyot yuqorida joylashgan.

Algoritmda faqat ℝ maydon ustidagi elliptik egri chiziqning guruh tuzilishi ishlatiladi. Bizga ℝ maydoni kerak emasligi sababli, cheklangan maydon ham elliptik egri chiziq bo'yicha guruh tuzilishini ta'minlaydi. Biroq, xuddi shu egri chiziq va ishlashni hisobga olgan holda ${ displaystyle ( mathbb {Z} / n mathbb {Z}) / sim}$ bilan n oddiy emas, guruhga bermaydi. Elliptik egri chizig'i usuli qo'shilish qonunining ishlamay qolish holatlaridan foydalanadi.

Endi algoritmni proektiv koordinatalarda bayon qilamiz. Keyin neytral element cheksiz nuqtada beriladi ${ displaystyle (0: 1: 0)}$. Ruxsat bering n (musbat) tamsayı bo'ling va elliptik egri chiziqni ko'rib chiqing (ustiga qandaydir tuzilishga ega bo'lgan nuqtalar to'plami) ${ displaystyle E ( mathbb {Z} / n mathbb {Z}) = {(x: y: z) in mathbb {P} ^ {2} | y ^ {2} z = x ^ {3} + axz ^ {2} + bz ^ {3} }}$.

1. Tanlang ${ displaystyle x_ {P}, y_ {P}, a in mathbb {Z} / n mathbb {Z}}$ bilan a ≠ 0.
2. Hisoblang ${ displaystyle b = y_ {P} ^ {2} -x_ {P} ^ {3} -ax_ {P}}$. Elliptik egri chiziq E keyin berilgan Weierstrass shaklida bo'ladi ${ displaystyle y ^ {2} = x ^ {3} + ax + b}$ va proektiv koordinatalardan foydalangan holda elliptik egri chiziq bir hil tenglama bilan berilgan ${ displaystyle ZY ^ {2} = X ^ {3} + aZ ^ {2} X + bZ ^ {3}}$. Buning mohiyati bor ${ displaystyle P = (x_ {P}: y_ {P}: 1)}$.
3. Yuqori chegarani tanlang ${ displaystyle B in mathbb {Z}}$ bu elliptik egri chiziq uchun. Izoh: Siz faqat omillarni topasiz p agar elliptik egri chiziqning guruh tartibi bo'lsa E ustida ${ displaystyle mathbb {Z} / p mathbb {Z}}$ (bilan belgilanadi ${ displaystyle #E ( mathbb {Z} / p mathbb {Z})}$) B-silliq degan ma'noni anglatadi, bu barcha asosiy omillar ${ displaystyle #E ( mathbb {Z} / p mathbb {Z})}$ kamroq yoki teng bo'lishi kerak B.
4. Hisoblang ${ displaystyle k = { rm {lcm}} (1, nuqta, B)}$.
5. Hisoblang ${ displaystyle kP: = P + P + cdots + P}$ (k marta) ringda ${ displaystyle E ( mathbb {Z} / n mathbb {Z})}$. E'tibor bering, agar ${ displaystyle #E ( mathbb {Z} / n mathbb {Z})}$ bu B- yumshoq va n asosiy (va shuning uchun) ${ displaystyle mathbb {Z} / n mathbb {Z}}$ maydon) bu ${ displaystyle kP = (0: 1: 0)}$. Ammo, agar shunday bo'lsa ${ displaystyle #E ( mathbb {Z} / p mathbb {Z})}$ bo'linuvchi uchun B-silliqdir p ning n, mahsulot (0: 1: 0) bo'lmasligi mumkin, chunki agar qo'shish va ko'paytirish yaxshi aniqlanmagan bo'lsa n asosiy emas. Bunday holda, ahamiyatsiz bo'luvchini topish mumkin.
6. Agar yo'q bo'lsa, unda 2-bosqichga qayting. Agar shunday bo'ladigan bo'lsa, mahsulotni soddalashtirganda buni sezasiz ${ displaystyle kP.}$

5-bandda aytilishicha, to'g'ri sharoitda ahamiyatsiz bo'luvchi topilishi mumkin. Lenstra (Elliptik egri chiziqli tamsayılarni faktorizatsiya qilish) maqolasida ta'kidlanganidek, qo'shimcha taxminni talab qiladi ${ displaystyle gcd (x_ {1} -x_ {2}, n) = 1}$. Agar ${ displaystyle P, Q}$ emas ${ displaystyle (0: 1: 0)}$ va alohida (aks holda qo'shimcha shunga o'xshash ishlaydi, ammo biroz boshqacha), keyin qo'shimcha quyidagicha ishlaydi:

• Hisoblash uchun: ${ displaystyle R = P + Q;}$ ${ displaystyle P = (x_ {1}: y_ {1}: 1), Q = (x_ {2}: y_ {2}: 1)}$,
• ${ displaystyle lambda = (y_ {1} -y_ {2}) (x_ {1} -x_ {2}) ^ {- 1}}$,
• ${ displaystyle x_ {3} = lambda ^ {2} -x_ {1} -x_ {2}}$,
• ${ displaystyle y_ {3} = lambda (x_ {1} -x_ {3}) - y_ {1}}$,
• ${ displaystyle R = P + Q = (x_ {3}: y_ {3}: 1)}$.

Agar qo'shimcha ishlamasa, bu xatolarni hisoblash bilan bog'liq ${ displaystyle lambda.}$ Xususan, chunki ${ displaystyle (x_ {1} -x_ {2}) ^ {- 1}}$ har doim ham hisoblash mumkin emas, agar n asosiy emas (va shuning uchun) ${ displaystyle mathbb {Z} / n mathbb {Z}}$ maydon emas). Dan foydalanmasdan ${ displaystyle mathbb {Z} / n mathbb {Z}}$ maydon bo'lib, quyidagilarni hisoblash mumkin:

• ${ displaystyle lambda '= y_ {1} -y_ {2}}$,
• ${ displaystyle x_ {3} '= { lambda'} ^ {2} -x_ {1} (x_ {1} -x_ {2}) ^ {2} -x_ {2} (x_ {1} -x_) {2}) ^ {2}}$,
• ${ displaystyle y_ {3} '= lambda' (x_ {1} (x_ {1} -x_ {2}) ^ {2} -x_ {3} ') - y_ {1} (x_ {1} - x_ {2}) ^ {3}}$,
• ${ displaystyle R = P + Q = (x_ {3} '(x_ {1} -x_ {2}): y_ {3}' :( x_ {1} -x_ {2}) ^ {3})}$va agar iloji bo'lsa soddalashtiring.

Ushbu hisoblash har doim qonuniydir va agar gcd ning Zbilan muvofiqlashtirish n ≠ (1 yoki n), shuning uchun soddalashtirish muvaffaqiyatsiz tugaydi, ning ahamiyatsiz bo'luvchisi n topildi.

Twisted Edvards egri chiziqlari

Dan foydalanish Edvard egri chiziqlari foydalanishdan kamroq modulli ko'paytmalar va kamroq vaqt talab etiladi Montgomeri egri chiziqlari yoki Weierstrass egri chiziqlari (boshqa ishlatilgan usullar). Edvard egri chiziqlaridan foydalanib, siz yana ko'p sonlarni topishingiz mumkin.

Ta'rif. Ruxsat bering ${ displaystyle k}$ unda maydon bo'ling ${ displaystyle 2 neq 0}$va ruxsat bering ${ displaystyle a, d in k setminus {0 }}$ bilan ${ displaystyle a neq d}$. Keyin burilgan Edvards egri chizig'i ${ displaystyle E_ {E, a, d}}$ tomonidan berilgan ${ displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}.}$ Edvards egri - bu burilgan Edvards egri chizig'i ${ displaystyle a = 1}$.

Edvards egri chizig'ida nuqta to'plamini yasashning beshta ma'lum usuli mavjud: afin nuqtalari to'plami, proektsion nuqtalar to'plami, teskari nuqtalar to'plami, kengaytirilgan nuqtalar to'plami va tugallangan nuqtalar to'plami.

Afinaviy nuqtalar to'plami quyidagicha:

${ displaystyle {(x, y) in mathbb {A} ^ {2}: ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2} }}$.

Qo'shish qonuni tomonidan berilgan

${ displaystyle (e, f), (g, h) mapsto chap ({ frac {eh + fg} {1 + degfh}}, { frac {fh-aeg} {1-degfh}} o'ng ).}$

(0,1) nuqta uning neytral elementi va teskari tomoni ${ displaystyle (e, f)}$ bu ${ displaystyle (-e, f)}$.

Proektsion Weierstrass egri chizig'i afinadan qanday chiqishiga o'xshash boshqa tasvirlar.

Har qanday elliptik egri chiziq Edvards shaklida tartibning nuqtasi bor 4. Demak burama guruh Edvard egri chizig'i ${ displaystyle mathbb {Q}}$ ikkalasiga ham izomorfdir ${ displaystyle mathbb {Z} / 4 mathbb {Z}, mathbb {Z} / 8 mathbb {Z}, mathbb {Z} / 12 mathbb {Z}, mathbb {Z} / 2 mathbb {Z} times mathbb {Z} / 4 mathbb {Z}}$ yoki ${ displaystyle mathbb {Z} / 2 mathbb {Z} times mathbb {Z} / 8 mathbb {Z}}$.

ECM uchun eng qiziqarli holatlar ${ displaystyle mathbb {Z} / 12 mathbb {Z}}$ va ${ displaystyle mathbb {Z} / 2 mathbb {Z} times mathbb {Z} / 8 mathbb {Z}}$, chunki ular egri chiziqli modulli sonlarning guruh tartiblarini mos ravishda 12 va 16 ga bo'linishga majbur qiladi. Quyidagi egri chiziqlar uchun izomorfik burilish guruhi mavjud ${ displaystyle mathbb {Z} / 12 mathbb {Z}}$:

• ${ displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$ nuqta bilan ${ displaystyle (a, b)}$ qayerda ${ displaystyle b notin {- 2, -1 / 2,0, pm 1 }, a ^ {2} = - (b ^ {2} + 2b)}$ va ${ displaystyle d = - (2b + 1) / (a ​​^ {2} b ^ {2})}$
• ${ displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$ nuqta bilan ${ displaystyle (a, b)}$ qayerda ${ displaystyle a = { frac {u ^ {2} -1} {u ^ {2} +1}}, b = - { frac {(u-1) ^ {2}} {u ^ {2 } +1}}}$ va ${ displaystyle d = { frac {(u ^ {2} +1) ^ {3} (u ^ {2} -4u + 1)} {(u-1) ^ {6} (u + 1) ^ {2}}}, u {0, pm 1 } emas.}$

3-tartibli har bir Edvards egri chizig'i yuqorida ko'rsatilgan usullar bilan yozilishi mumkin. Burilish guruhiga egri chiziqlar izomorfik ${ displaystyle mathbb {Z} / 2 mathbb {Z} times mathbb {Z} / 8 mathbb {Z}}$ va ${ displaystyle mathbb {Z} / 2 mathbb {Z} times mathbb {Z} / 4 mathbb {Z}}$ tub sonlarni topishda samaraliroq bo'lishi mumkin.^[2]

2-bosqich

Yuqoridagi matn elliptik egri faktorizatsiyasining birinchi bosqichi haqida. Bosh bo'linuvchini topishga umid bor p shu kabi ${ displaystyle sP}$ ning neytral elementidir ${ displaystyle E ( mathbb {Z} / p mathbb {Z})}$.Ikkinchi bosqichda asosiy bo'luvchi topiladi degan umiddamiz q shu kabi ${ displaystyle sP}$ kichik bosh buyurtma mavjud ${ displaystyle E ( mathbb {Z} / q mathbb {Z})}$.

Umid qilamizki, buyurtma o'rtasida bo'ladi ${ displaystyle B_ {1}}$ va ${ displaystyle B_ {2}}$, qayerda ${ displaystyle B_ {1}}$ 1 va bosqichda aniqlanadi ${ displaystyle B_ {2}}$ 2-bosqichning yangi parametri.-ning kichik tartibini tekshirish ${ displaystyle sP}$, hisoblash yo'li bilan amalga oshirilishi mumkin ${ displaystyle (ls) P}$ modul n har bir asosiy uchun l.

GMP-ECM va EECM-MPFQ

Twisted Edwards elliptik egri chiziqlaridan foydalanish va boshqa texnikalar singari Bernshteyn va boshq^[2] ECMni optimallashtirishni ta'minlash. Uning yagona kamchiligi shundaki, u Zimmermanning GMP-ECM dasturiga qaraganda kichikroq kompozit raqamlar ustida ishlaydi.

Giperelliptik-egri usuli (HECM)

So'nggi paytlarda foydalanishda o'zgarishlar mavjud giperelliptik egri chiziqlar faktor tamsayılarga. Cosset o'z maqolasida (2010 y.) Giperelliptik egri chiziqni ikki jins bilan qurish mumkinligini ko'rsatadi (shuning uchun egri chiziq) ${ displaystyle y ^ {2} = f (x)}$ bilan f 5) daraja, bu bir vaqtning o'zida ikkita "normal" elliptik egri chiziqdan foydalanish bilan bir xil natijani beradi. Kummer sirtidan foydalangan holda hisoblash samaraliroq bo'ladi. Giperelliptik egri chiziqning kamchiliklari (elliptik egri chiziqqa nisbatan) hisoblashning ushbu muqobil usuli bilan qoplanadi. Shuning uchun, Cosset taxminan faktorizatsiya qilish uchun giperelliptik egri chiziqlardan foydalanish elliptik egri chiziqlardan foydalanishdan yomonroq emas deb da'vo qilmoqda.

Kvant versiyasi (GEECM)

Bernshteyn, Xeninger, Lou va Valenta GEECM-ni, Edvards egri chiziqli ECM ning kvant versiyasini taklif qilishadi.^[3] U foydalanadi Grover algoritmi standart kubiklarga ega kvant kompyuterni va EECM ishlaydigan klassik kompyuter bilan taqqoslanadigan tezlikni nazarda tutgan holda, standart EECM bilan taqqoslaganda topilgan tub sonlarning uzunligini taxminan ikki baravar oshirish.

Shuningdek qarang

• UBASIC amaliy dastur uchun (ECMX).

Adabiyotlar

• Bernshteyn, Daniel J.; Birkner, Piter; Lange, Tanja; Peters, Christiane (2013). "Edvards egri chiziqlaridan foydalangan holda ECM". Hisoblash matematikasi. 82 (282): 1139–1179. doi:10.1090 / S0025-5718-2012-02633-0. JANOB  3008853.
• Bosma, V.; Xulst, M. P. M. van der (1990). Tsiklotomiya bilan birinchi darajali isbotlash. Ph.D. Tezislar, Amsterdam universiteti. OCLC  256778332.
• Brent, Richard P. (1999). "O'ninchi Fermat raqamini faktorizatsiya qilish". Hisoblash matematikasi. 68 (225): 429–451. doi:10.1090 / S0025-5718-99-00992-8. JANOB  1489968.
• Koen, Anri (1993). Hisoblash algebraik sonlar nazariyasi kursi. Matematikadan aspirantura matnlari. 138. Berlin: Springer-Verlag. doi:10.1007/978-3-662-02945-9. ISBN  978-0-387-55640-6. JANOB  1228206.
• Cosset, R. (2010). "2-egri chiziqli faktorizatsiya". Hisoblash matematikasi. 79 (270): 1191–1208. arXiv:0905.2325. Bibcode:2010MaCom..79.1191C. doi:10.1090 / S0025-5718-09-02295-9. JANOB  2600562.
• Lenstra, A. K.; Lenstra Jr., H. W., nashr. (1993). Sonli dala elagining rivojlanishi. Matematikadan ma'ruza matnlari. 1554. Berlin: Springer-Verlag. doi:10.1007 / BFb0091534. ISBN  978-3-540-57013-4. JANOB  1321216.
• Lenstra Jr., H. W. (1987). "Elliptik egri chiziqli tamsayılarni faktoring qilish" (PDF). Matematika yilnomalari. 126 (3): 649–673. doi:10.2307/1971363. JSTOR  1971363. JANOB  0916721.
• Pomerans, Karl; Crandall, Richard (2005). Asosiy sonlar: hisoblash istiqbollari (Ikkinchi nashr). Nyu-York: Springer. ISBN  978-0-387-25282-7. JANOB  2156291.
• Pomerance, Karl (1985). "Kvadratik elak faktoring algoritmi". Kriptologiya, prok. Evrokript '84. Kompyuter fanidan ma'ruza matnlari. 209. Berlin: Springer-Verlag. 169-182 betlar. doi:10.1007/3-540-39757-4_17. ISBN  978-3-540-16076-2. JANOB  0825590.
• Pomerance, Karl (1996). "Ikki elakdan ertak" (PDF ). Amerika Matematik Jamiyati to'g'risida bildirishnomalar. 43 (12): 1473–1485. JANOB  1416721.
• Silverman, Robert D. (1987). "Ko'p polinomli kvadratik elak". Hisoblash matematikasi. 48 (177): 329–339. doi:10.1090 / S0025-5718-1987-0866119-8. JANOB  0866119.
• Trappe, V.; Vashington, L. C. (2006). Kodlash nazariyasi bilan kriptografiyaga kirish (Ikkinchi nashr). Saddle River, NJ: Pearson Prentice Hall. ISBN  978-0-13-186239-5. JANOB  2372272.
• Semyuel S. Vagstaff, kichik (2013). Faktoring quvonchi. Providence, RI: Amerika matematik jamiyati. 173-190 betlar. ISBN  978-1-4704-1048-3.
• Vatras, Martsin (2008). Kriptografiya, raqamlar tahlili va juda katta sonlar. Bydgoszcz: Voytsexovskiy-Shtaynhagen. PL: 5324564.

Tashqi havolalar

• Elliptik egri usuli yordamida faktorizatsiya, ECM dan foydalanadigan va ga o'tadigan Java applet O'z-o'zini ishga tushirish kvadratik elak tezroq bo'lganda.
• GMP-ECM, ECMni samarali amalga oshirish.
• ECMNet, bir nechta faktorizatsiya loyihalari bilan ishlaydigan oson mijoz-serverni amalga oshirish.
• pyecm, ECM ning python dasturi. Psycco va / yoki gmpy bilan juda tezroq.
• Tarqatilgan hisoblash loyihasi yoyo @ Home ECM subproject - bu Elliptik egri chiziqli faktorizatsiya dasturi bo'lib, u er-xotin loyihada turli xil sonlar uchun omillarni topish uchun ishlatiladi.
• Lenstra Elliptic Curve Factorization algoritmining manba kodi Oddiy C va GMP Elliptik egri chiziqli faktorizatsiya algoritmi manba kodi.
• EECM-MPFQ MPFQ cheklangan maydon kutubxonasi bilan yozilgan Edvards egri chiziqlari yordamida ECMni amalga oshirish.