Edvard egri chizig'i - Edwards curve

Tenglamaning Edvard egri chiziqlari x² + y² = 1 − d ·x²·y² uchun haqiqiy sonlar ustida d = 300 (qizil), d = √8 (sariq) va d = -0.9 (ko'k)

Yilda matematika, Edvard egri chiziqlari oila elliptik egri chiziqlar tomonidan o'rganilgan Xarold Edvards 2007 yilda. Elliptik egri chiziqlar kontseptsiyasi cheklangan maydonlar da keng ishlatiladi egri chiziqli kriptografiya. Edvard egri chiziqlarining qo'llanilishi kriptografiya tomonidan ishlab chiqilgan Daniel J. Bernshteyn va Tanja Lange: ular Edvards shaklining taniqli bilan taqqoslaganda bir nechta afzalliklarini ta'kidladilar Weierstrass shakli.

Ta'rif

Edvards egri chizig'ining a ga tenglamasi maydon K bunga ega emas xarakterli 2 bu:

${ displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2} ,}$

kimdir uchun skalar ${ displaystyle d in K setminus {0,1 }}$.Parametrlari bilan quyidagi shakl v va d Edvards egri chizig'i deb ataladi:

${ displaystyle x ^ {2} + y ^ {2} = c ^ {2} (1 + dx ^ {2} y ^ {2}) ,}$

qayerda v, d ∈ K bilan CD(1 − v⁴·d) ≠ 0.

Har bir Edvard egri chizig'i ikki tomonlama teng ichida elliptik egri chiziqqa Weierstrass shakli va shu bilan algebraik guruh qonunini qabul qiladi, chunki u neytral element sifatida xizmat qiladigan nuqtani tanlaydi. Agar K sonli, so'ngra barcha elliptik egri chiziqlarning katta qismi K Edvards egri chiziqlari sifatida yozilishi mumkin, Edvards shaklidagi ko'pincha elliptik egri chiziqlar umumiyligini yo'qotmasdan, c = 1 ga ega. Keyingi bo'limlarda c = 1 deb taxmin qilinadi.

Guruh qonuni

(Shuningdek qarang Vayderstras egri chiziqli guruh qonuni )

Elliptik egri chiziqdagi nuqtalar abeliya guruhini tashkil qiladi: bitta nuqta qo'shish va butun sonni olish mumkin. Agar elliptik egri chiziq yagona bo'lmagan kub tenglama bilan tavsiflangan bo'lsa, u holda ikkita nuqta yig'indisi P va Q, belgilangan P + Q, egri chiziq va u orqali o'tuvchi chiziq o'rtasida kesishishning uchinchi nuqtasi bilan bevosita bog'liqdir P va Q. Ammo Edvards egri chiziqlari singari yuqori darajadagi singular uchun vaziyat biroz murakkabroq. Edvards egri chiziqlariga qo'shilish qonunini geometrik tushuntirish uchun Arene va boshqalarning "Teytlar juftligini tezroq hisoblashi" ga qarang.^[1]

Edvardsning qo'shilishi to'g'risidagi qonun

1-turdagi egri chiziq va neytral elementga xizmat qilish uchun tanlangan nuqta nazarda tutilgan har qanday elliptik egri chiziqda ikkita nuqta yig'indisi nuqta koordinatalarini oqilona ifodalash bilan beriladi, ammo umuman olganda ulardan foydalanish kerak bo'lishi mumkin barcha mumkin bo'lgan juftlarni qamrab oladigan bir nechta formulalar. Edvards egri chizig'i uchun neytral element nuqta (0, 1), ballar yig'indisi (x₁, y₁) va (x₂, y₂) formula bilan berilgan

${ displaystyle (x_ {1}, y_ {1}) + (x_ {2}, y_ {2}) = left ({ frac {x_ {1} y_ {2} + x_ {2} y_ {1 }} {1 + dx_ {1} x_ {2} y_ {1} y_ {2}}}, { frac {y_ {1} y_ {2} -x_ {1} x_ {2}} {1-dx_ {1} x_ {2} y_ {1} y_ {2}}} o'ng) = chap ({ frac {x_ {1} y_ {1} + x_ {2} y_ {2}} {x_ {1) } x_ {2} + y_ {1} y_ {2}}}, { frac {x_ {1} y_ {1} -x_ {2} y_ {2}} {x_ {1} y_ {2} -y_ {1} x_ {2}}} o'ng) ,}$

Istalgan nuqtaning teskari tomoni (x₁, y₁) bu (-x₁, y₁). (0, -1) nuqta 2-tartibda va (± 1,0) nuqtalarda 4-tartib borligini tekshirish mumkin. Xususan, Edvards egri chizig'ida har doim 4-tartibli nuqta bor K.

Agar d kvadrat emas yilda K va ${ displaystyle (x_ {1}, y_ {1}), (x_ {2}, y_ {2}) in {(x, y) | x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2} }}$, unda istisno nuqtalar mavjud emas: maxrajlar 1 +dx₁x₂y₁y₂ va 1 -dx₁x₂y₁y₂ har doim nolga teng. Shuning uchun, Edvardsning qo'shilish qonuni qachon to'liq bo'ladi d kvadrat emas K. Bu shuni anglatadiki, formulalar Edvards egri chizig'idagi barcha kirish nuqtalari uchun ishlaydi, ikki baravar ko'paytirish uchun istisnolar, neytral element uchun istisnolar, salbiylar uchun istisno va boshqalar.^[2] Boshqacha qilib aytganda, bu Edvards egri chizig'idagi kirish nuqtalarining barcha juftliklari uchun aniqlangan K va natija kirish nuqtalarining yig'indisini beradi.

Agar d - kvadrat yilda K, keyin bir xil operatsiya alohida nuqtalarga ega bo'lishi mumkin, ya'ni juftliklar bo'lishi mumkin (x₁, y₁) va (x₂, y₂) bu erda 1 +dx₁x₂y₁y₂ = 0 yoki 1 -dx₁x₂y₁y₂ = 0.

Edvards Qo'shish qonunining jozibali xususiyatlaridan biri shundaki, u qat'iydir birlashtirilgan ya'ni undan himoyani soddalashtirib, bir nuqtani ikki baravar oshirish uchun ham foydalanish mumkin yon kanal hujumi. Yuqoridagi qo'shilish formulasi boshqa birlashtirilgan formulalarga qaraganda tezroq va to'liqlikning kuchli xususiyatiga ega^[2]

Qo'shish qonunining misoli :

Bilan Edvards shaklidagi elliptik egri chiziqni ko'rib chiqing d=2

${ displaystyle { displaystyle} x ^ {2} + y ^ {2} = 1 + 2x ^ {2} y ^ {2}}$

va nuqta ${ displaystyle P_ {1} = (1,0)}$ ustida. Ning yig‘indisi ekanligini isbotlash mumkin P₁ neytral element bilan (0,1) yana P beradi₁. Darhaqiqat, yuqorida keltirilgan formuladan foydalanib, ushbu summa bilan berilgan nuqtaning koordinatalari:

${ displaystyle x_ {3} = { frac {x_ {1} y_ {2} + y_ {1} x_ {2}} {1 + dx_ {1} x_ {2} y_ {1} y_ {2}} } = 1}$

${ displaystyle y_ {3} = { frac {y_ {1} y_ {2} -x_ {1} x_ {2}} {1-dx_ {1} x_ {2} y_ {1} y_ {2}} } = 0}$

Doira bo'yicha analog

Soat guruhi

Nuqtalarning egri chiziqdagi "qo'shilishi" tushunchasini yaxshiroq tushunish uchun klassik doiralar guruhi tomonidan yaxshi misol keltirilgan:

radius 1 doirasini oling

${ displaystyle { displaystyle} x ^ {2} + y ^ {2} = 1}$

va ikkita fikrni ko'rib chiqing P₁= (x₁, y₁), P₂= (x₂, y₂) ustida. A ga ruxsat bering₁ va a₂ shunday burchaklar bo'ling:

${ displaystyle { displaystyle} P_ {1} = (x_ {1}, y_ {1}) = ( sin { alpha _ {1}}, cos { alpha _ {1}})}$

${ displaystyle { displaystyle} P_ {2} = (x_ {2}, y_ {2}) = ( sin { alfa _ {2}}, cos { alfa _ {2}})}$

P ning yig'indisi₁ va P₂ shunday qilib, "ularning burchaklari" yig'indisi bilan berilgan. Ya'ni, P nuqta₃= P₁+ P₂ koordinatali (x) doiradagi nuqta₃, y₃), bu erda:

${ displaystyle { displaystyle} x_ {3} = sin ({ alpha} _ {1} + { alpha} _ {2}) = sin { alpha} _ {1} cos { alpha} _ {2} + sin { alpha} _ {2} cos { alpha} _ {1} = x_ {1} y_ {2} + x_ {2} y_ {1}}$

${ displaystyle { displaystyle} y_ {3} = cos ({ alfa} _ {1} + { alpha} _ {2}) = cos { alfa} _ {1} cos { alpha} _ {2} - sin { alpha} _ {1} sin { alpha} _ {2} = y_ {1} y_ {2} -x_ {1} x_ {2}.}$

Shu tarzda, radiusi 1 doirasidagi nuqtalar uchun qo'shilish formulasi:

${ displaystyle { displaystyle} (x_ {1}, y_ {1}) + (x_ {2}, y_ {2}) = (x_ {1} y_ {2} + x_ {2} y_ {1}, y_ {1} y_ {2} -x_ {1} x_ {2})}$.

Projektiv bir hil koordinatalar

Kriptografiya nuqtai nazaridan, bir hil koordinatalar oldini olish uchun ishlatiladi maydon inversiyalari affin formulasida paydo bo'ladi. Dastlabki Edvards qo'shish formulalarida inversiyani oldini olish uchun egri tenglamani yozish mumkin proektiv koordinatalar kabi:

${ displaystyle (X ^ {2} + Y ^ {2}) Z ^ {2} = Z ^ {4} + dX ^ {2} Y ^ {2}}$.

Proektiv nuqta (X₁ : Y₁ : Z₁) ga to'g'ri keladi afinaviy nuqta (X₁/Z₁, Y₁/Z₁) Edvards egri chizig'ida.

Identifikatsiya elementi (0: 1: 1) bilan ifodalanadi. Ning teskarisiX₁ : Y₁ : Z₁) bu (-X₁ : Y₁ : Z₁).

Proektsion bir hil koordinatalarda qo'shimcha formula quyidagicha berilgan: [ular aniq etarli emas, chunki nuqta ikki baravar ko'payishi uchun P1 = P2 bo'lsa, natija X3 = 0, Y3 = 0, Z3 = 0 ga teng bo'ladi]

(X₃ : Y₃ : Z₃) = (X₁ : Y₁ : Z₁) + (X₂ : Y₂ : Z₂)

qayerda

X₃ = Z₁Z₂(X₁Y₂ − Y₁X₂)(X₁Y₁Z₂² + Z₁²X₂Y₂)

Y₃ = Z₁Z₂(X₁X₂ + Y₁Y₂) (X₁Y₁Z₂² - Z₁²X₂Y₂)

Z₃ = kZ₁²Z₂²(X₁X₂ + Y₁Y₂) (X₁Y₂ - Y₁X₂) bilan k = 1/v.

Algoritm

Quyidagi algoritmdan foydalanib, X₃, Y₃, Z₃ quyidagicha yozilishi mumkin: X₃→ GJ, Y₃→ HK, Z₃→ kJK.d

bu erda: A → X₁Z₂,

B → Y₁Z₂,

C → Z₁X₂,

D → Z₁Y₂,

E → AB,

F → CD,

G → E + F,

H → E-F,

J → (A-C) (B + D) -H,

K → (A + D) (B + C) -G

Ikki baravar

Ikki baravar qo'shish bilan bir xil formulada bajarilishi mumkin. Ikki baravar kiritish holatlar (x₁, y₁) va (x₂, y₂) teng ekanligi ma'lum. Beri (x₁, y₁) Edvards egri chizig'ida, koeffitsientni (bilan) bilan almashtirish mumkinx₁² + y₁² − 1)/x₁²y₁² quyidagicha:

${ displaystyle { begin {aligned} 2 (x_ {1}, y_ {1}) & = (x_ {1}, y_ {1}) + (x_ {1}, y_ {1}) [6pt ] 2 (x_ {1}, y_ {1}) & = chap ({ frac {2x_ {1} y_ {1}} {1 + dx_ {1} ^ {2} y_ {1} ^ {2} }}, { frac {y_ {1} ^ {2} -x_ {1} ^ {2}} {1-dx_ {1} ^ {2} y_ {1} ^ {2}}} o'ng) [6pt] & = chap ({ frac {2x_ {1} y_ {1}} {x_ {1} ^ {2} + y_ {1} ^ {2}}}, { frac {y_ {1) } ^ {2} -x_ {1} ^ {2}} {2-x_ {1} ^ {2} -y_ {1} ^ {2}}} right) end {aligned}}}$

Bu maxrajning darajasini 4 dan 2 gacha pasaytiradi, bu tezroq juftlashda aks etadi va Edvards koordinatalarida umumiy qo'shimcha 10 ga tengM + 1S + 1C + 1D. + 7a va xarajatlarni ikki baravar oshirish 3M + 4S + 3C + 6a qayerda M maydonni ko'paytirish, S dala kvadratlari, D. - bu tanlanadigan egri chizig'i parametri bilan ko'paytirish xarajatlari va a maydonni qo'shishdir.

Ikki barobar ko'payishning misoli

Qo'shish qonuni uchun avvalgi misolda bo'lgani kabi, d = 2 bilan Edvards egri chizig'ini ko'rib chiqing:

${ displaystyle { displaystyle} x ^ {2} + y ^ {2} = 1 + 2x ^ {2} y ^ {2}}$

va P nuqta₁= (1,0). 2P nuqtaning koordinatalari₁ ular:

${ displaystyle x_ {3} = { frac {2x_ {1} y_ {1}} {1 + dx_ {1} ^ {2} y_ {1} ^ {2}}} = 0}$

${ displaystyle y_ {3} = { frac {y_ {1} ^ {2} -x_ {1} ^ {2}} {1-dx_ {1} ^ {2} y_ {1} ^ {2}} } = - 1}$

P ni ikki baravar oshirish natijasida olingan nuqta₁ shunday qilib P₃=(0,-1).

Aralash qo'shimchalar

Aralash qo'shish Z bo'lganida bo'ladi₂ ekanligi ma'lum 1. Bunday holda A = Z₁^.Z₂ yo'q qilinishi mumkin va umumiy xarajatlar 9 ga kamayadiM+1S+1C+1D.+7a

Algoritm

A = Z₁^.Z₂ // boshqacha qilib aytganda, A = Z₁

B = Z₁²

C = X₁.X₂

D = Y₁^.Y₂

E = d^.C^.D.

F = B-E

G = B + E

X₃= A^.F ((X_Men+ Y₁)^.(X₂+ Y₂) -C-D)

Y₃= A^.G^.(D-C)

Z₃= C^.F^.G

Uch marta

Uch marta avval nuqtani ikki baravar oshirish, so'ngra natijani o'ziga qo'shish orqali amalga oshirilishi mumkin. Ikki barobarga teng egri chiziqli tenglamani qo'llash orqali biz erishamiz

${ displaystyle 3 (x_ {1}, y_ {1}) = chap ({ frac {(x_ {1} ^ {2} + y_ {1} ^ {2}) ^ {2} - (2y_ {) 1}) ^ {2}} {4 (x_ {1} ^ {2} -1) x_ {1} ^ {2} - (x_ {1} ^ {2} -y_ {1} ^ {2}) ^ {2}}} x_ {1}, { frac {(x_ {1} ^ {2} + y_ {1} ^ {2}) ^ {2} - (2x_ {1}) ^ {2}} {-4 (y_ {1} ^ {2} -1) y_ {1} ^ {2} + (x_ {1} ^ {2} -y_ {1} ^ {2}) ^ {2}}} y_ {1} o'ng). ,}$

Ushbu operatsiyani bajarish uchun standart Edvards koordinatalarida ikkita formulalar to'plami mavjud. Birinchisi 9 turadiM + 4S ikkinchisiga esa 7 kerakM + 7S. Agar S / M nisbati juda kichik, xususan 2/3 ostida, keyin ikkinchi to'plam yaxshiroq, katta nisbatlar uchun birinchisiga ustunlik beriladi.^[3]Qo'shish va ko'paytirish formulalaridan foydalanish (yuqorida aytib o'tilganidek) nuqta (X₁ : Y₁ : Z₁) ramziy ma'noda 3 (X₁ : Y₁ : Z₁) va (bilan solishtirgandaX₃ : Y₃ : Z₃)

Uch marta uchish misoli

D = 2, va P nuqta bilan Edvards egri chizig'ini berish₁= (1,0), 3P nuqta₁ koordinatalariga ega:

${ displaystyle x_ {3} = { frac {(x_ {1} ^ {2} + y_ {1} ^ {2}) ^ {2} - (2y_ {1}) ^ {2}} {4 ( x_ {1} ^ {2} -1) x_ {1} ^ {2} - (x_ {1} ^ {2} -y_ {1} ^ {2}) ^ {2}}} x_ {1} = -1}$

${ displaystyle y_ {3} = { frac {(x_ {1} ^ {2} + y_ {1} ^ {2}) ^ {2} -2 (x_ {1}) ^ {2}} {- 4 (y_ {1} ^ {2} -1) y_ {1} ^ {2} + (x_ {1} ^ {2} -y_ {1} ^ {2}) ^ {2}}} y_ {1 } = 0}$

Shunday qilib, 3P₁= (- 1,0) = P-₁. Ikkala misolni hisobga olgan holda ushbu natijani topish mumkin: 2P₁= (0,1), shuning uchun 3P₁ = 2P₁ + P₁ = (0, -1) + P₁ = -P₁.

Algoritm

A = X₁²

B = Y₁²

C = (2Z₁)²

D = A + B

E = D²

F = 2D. (A-B)

G = E-B.C.

H = E-A.C.

I = F + H

J = F-G

X₃= G.J.X1

Y₃= H.I.Y1

Z₃= I.J.Z1

Ushbu formulaning narxi 9 ga tengM + 4S

Inverted Edwards koordinatalari

Bernshteyn va Lange elliptik egri chiziqlar uchun hatto tezroq koordinatalar tizimini joriy qildilar Teskari Edvard koordinatalari^[4] unda koordinatalar (X : Y : Z) egri chiziqni qondirish (X² + Y²)Z² = (dZ⁴ + X²Y²) va affine nuqtasiga mos keladi (Z/X, Z/Y) Edvards egri chizig'ida x² + y² = 1 + dx²y² XYZ ≠ 0 bilan.

Inverted Edwards koordinatalari, standart Edvards koordinatalaridan farqli o'laroq, to'liq qo'shilish formulalariga ega emas: neytral element kabi ba'zi nuqtalarni alohida ko'rib chiqish kerak. Ammo qo'shimcha formulalar hali ham kuchli birlashishning afzalliklariga ega: ular ochkoni ikki baravar oshirish uchun o'zgarishsiz ishlatilishi mumkin.

Ushbu koordinatalar bilan ishlash haqida ko'proq ma'lumot olish uchun qarang http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

Edvard egri chiziqlari uchun kengaytirilgan koordinatalar

Boshqa bir koordinatalar tizimi mavjud bo'lib, u bilan Edvards egri chizig'ini ko'rsatish mumkin; ushbu yangi koordinatalar chaqiriladi kengaytirilgan koordinatalar^[5] va teskari koordinatalardan ham tezroq. Ushbu koordinatalar bilan ishlashda talab qilinadigan vaqt xarajatlari haqida ko'proq ma'lumot olish uchun qarang:http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Shuningdek qarang

• Twisted Edvards egri chizig'i

Muayyan holatda talab qilinadigan ish vaqti haqida qo'shimcha ma'lumot olish uchun qarang Elliptik egri chiziqlardagi operatsiyalar xarajatlari jadvali.

Izohlar

Adabiyotlar

• Bernshteyn, Doniyor; Lange, Tanja (2007), Elliptik egri chiziqlarda tezroq qo'shish va ikki baravar oshirish (PDF)
• Edvards, Garold M. (2007 yil 9 aprel), "Elliptik egri chiziqlar uchun normal shakl", Amerika Matematik Jamiyati Axborotnomasi, 44 (3): 393–422, doi:10.1090 / s0273-0979-07-01153-6, ISSN  0002-9904
• Elliptik egri chiziqlar bo'yicha tezroq guruh operatsiyalari, H. Hisil, K. K. Vong, G. Karter, E. Douson
• D.J.Bernshteyn, P.Birkner. T. Lanj, S-Peters, Ikki asosli elliptik-egri chiziqli bitta skalyarli ko'paytirishni optimallashtirish (PDF)CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
• Vashington, Lourens S. (2008), Elliptik egri chiziqlar: sonlar nazariyasi va kriptografiya, Diskret matematika va uning qo'llanilishi (2-nashr), Chapman & Hall / CRC, ISBN  978-1-4200-7146-7
• Bernshteyn, Doniyor; Lange, Tanja, Inverted Edwards koordinatalari (PDF)

Tashqi havolalar

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-edwards.html