Ikki baravar yo'naltirilgan Doche-Icart-Kohel egri chizig'i - Doubling-oriented Doche–Icart–Kohel curve - Wikipedia

Ikki baravarga yo'naltirilgan Doche-Icart-Kohel tenglamasining egri chizig'i ${ displaystyle y ^ {2} = x ^ {3} -x ^ {2} -16x}$

Yilda matematika, ikki baravar yo'naltirilgan Doche-Icart-Kohel egri chizig'i bu shakl elliptik egri chiziq yozilishi mumkin. Bu alohida holat Weierstrass shakli va bu ham muhimdir egri chiziqli kriptografiya chunki ikki baravar ko'payish sezilarli darajada tezlashadi (hisoblash 2- tarkibi sifatidaizogeniya va uning ikkilamchi ). Uni Kristof Dox, Tomas Ikart va Devid R.Koxel kiritgan Izogeniya dekompozitsiyalari bilan skalerni samarali ko'paytirish.^[1]

Ta'rif

Ruxsat bering ${ displaystyle K}$ bo'lishi a maydon va ruxsat bering ${ displaystyle a in K}$. Keyin, ikki baravarga yo'naltirilgan Doche-Icart-Kohel egri chizig'i parametr a yilda affin koordinatalari quyidagilar bilan ifodalanadi:

${ displaystyle y ^ {2} = x ^ {3} + ax ^ {2} + 16ax}$

Teng ravishda, ichida proektiv koordinatalar:

${ displaystyle ZY ^ {2} = X ^ {3} + aZX ^ {2} + 16aXZ ^ {2},}$

bilan ${ displaystyle x = { frac {X} {Z}}}$ va ${ displaystyle y = { frac {Y} {Z}}}$.

E'tibor bering, chunki bu egri chiziq alohida holat Weierstrass shakli, elliptik egri chiziqning (Weierstrass formasi) eng keng tarqalgan shakliga o'tish kerak emas.

Guruh qonuni

Ni tahlil qilish qiziq guruh qonuni yilda egri chiziqli kriptografiya, qo'shish va qo'shilish formulalarini belgilash, chunki bu formulalar ko'p sonli ballarni hisoblash uchun zarurdir [n] P (qarang Kvadratlar yordamida ko'rsatkichlar ). Umuman olganda, guruh qonuni quyidagicha ta'riflanadi: agar uchta nuqta bir qatorda joylashgan bo'lsa, unda ular nolga tenglashadi. Shunday qilib, ushbu xususiyatga ko'ra, guruh qonunlari har qanday egri shakli uchun farq qiladi.

Bunday holda, bu egri chiziqlar Weierstrass egri chiziqlarining maxsus holatlari bo'lganligi sababli, qo'shimcha faqat Weierstrass egri chiziqlaridagi standart qo'shimchadir. Boshqa tomondan, nuqtani ikki baravar oshirish uchun standart ikki barobar formuladan foydalanish mumkin, ammo bu unchalik tez bo'lmaydi. neytral element bu ${ displaystyle theta = (0: 1: 0)}$ (proektiv koordinatalarda), buning uchun ${ displaystyle theta = - theta}$. Keyin, agar ${ displaystyle P = (x, y)}$ ahamiyatsiz element (${ displaystyle P! = O}$), u holda bu nuqtaning teskari tomoni (qo'shimcha bo'yicha) –P = (x, -y) bo'ladi.

Qo'shish

Ushbu holatda, affin koordinatalari qo'shilish formulasini aniqlash uchun ishlatiladi:

(x₁, y₁) + (x₂, y₂) = (x₃, y₃) qayerda

x₃ = (-x₁³+ (x₂-a) x₁²+ (x₂²+ 2ax₂) x₁+ (y₁²-2y₂y₁+ (- x₂³-ax₂²+ y₂²))) / (x₁²-2x₂x₁+ x₂²)

y₃ = ((-y₁+ 2y₂) x₁³+ (- oy₁+ (- 3y₂x₂+ ay₂)) x₁²+ ((3x₂²+ 2ax₂) y₁-2ay₂x₂) x₁+ (y₁³-3y₂y₁²+ (- 2x₂³-ax₂²+ 3y₂²) y₁+ (y₂x₂³+ ay₂x₂²-y₂³))) / (- x₁³+ 3x₂x₁²-3x₂²x₁+ x₂³)

Ikki baravar

2 (x₁, y₁) = (x₃, y₃)

x₃ = 1 / (4y₁²) x₁⁴-8a / y₁²x₁²+ 64a2 / y₁²

y₃ = 1 / (8y₁³) x₁⁶+ ((- a²+ 40a) / (4y₁³)) x₁⁴+ ((ay.)₁²+ (16a³-640a²)) / (4y₁³)) x₁²+ ((- 4a²y₁²-512a³) / y₁³)

Algoritmlar va misollar

Qo'shish

Eng tezkor qo'shimchalar quyidagilar (natijalar bilan taqqoslaganda: http://hyperelliptic.org/EFD/g1p/index.html ) va uning narxi 4 ko'paytma, 4 kvadrat va 10 qo'shimcha.

A = Y₂-Y₁

AA = A²

B = X₂-X₁

CC = B²

F = X₁CC

Z₃ = 2CC

D = X₂Z₃

ZZ₃ = Z₃²

X₃ = 2 (AA-F) -aZ₃-D

Y₃ = ((A + B)²-AA-CC) (D-X₃) -Y₂ZZ₃

Misol

Ruxsat bering ${ displaystyle K = mathbb {Q}}$. $ P = (X $) bo'lsin₁, Y₁) = (2,1), Q = (X₂, Y₂) = (1, -1) va a = 1, keyin

A = 2

AA = 4

B = 1

CC = 1

F = 2

Z₃=4

D = 4

ZZ₃=16

X₃=-4

Y₃=336

Shunday qilib, P + Q = (- 4: 336: 4)

Ikki baravar

Quyidagi algoritm eng tezkoridir (solishtirish uchun quyidagi havolani ko'ring: http://hyperelliptic.org/EFD/g1p/index.html ) va uning narxi 1 ko'paytma, 5 kvadrat va 7 qo'shimchalar.

A = X₁²

B = A-a16

C = a₂A

YY = Y₁²

YY₂ = 2YY

Z₃ = 2YY₂

X₃ = B²

V = (Y₁+ B) 2-YY-X₃

Y₃ = V (X₃+ 64C + a (YY₂-C))

ZZ₃ = Z₃²

Misol

Ruxsat bering ${ displaystyle K = mathbb {Q}}$ va a = 1. P = (- 1,2) bo'lsin, keyin Q = [2] P = (x3, y3) quyidagicha bo'ladi:

A = 1

B = -15

C = 2

YY = 4

YY₂=8

Z₃=16

X₃=225

V = 27

Y₃=9693

ZZ₃=256

Shunday qilib, Q = (225: 9693: 16).

Kengaytirilgan koordinatalar

Qo'shish va ikki barobar hisoblash imkon qadar tezroq bo'lishi kerak, shuning uchun koordinatalarning quyidagi ko'rinishini ishlatish qulayroq:

${ displaystyle x, y}$ bilan ifodalanadi ${ displaystyle X, Y, Z, ZZ}$ quyidagi tenglamalarni qondirish:

${ displaystyle x = { frac {X} {Z}}}$

${ displaystyle y = { frac {Y} {ZZ}}}$

${ displaystyle ZZ = Z ^ {2}}$

Keyinchalik, ikki barobarga yo'naltirilgan Doche-Icart-Kohel egri chizig'i quyidagi tenglama bilan berilgan:

${ displaystyle Y ^ {2} = ZX ^ {3} + aZ ^ {2} X ^ {2} + 16aZ ^ {3} X}$.

Ushbu holatda,${ displaystyle P = (X: Y: Z: ZZ)}$ teskari umumiy nuqta ${ displaystyle -P = (X: -Y: Z: ZZ)}$Bundan tashqari, egri chiziqdagi fikrlar quyidagilarni qondiradi: ${ displaystyle (X: Y: Z: Z ^ {2}) = ( lambda X: lambda ^ {2} Y: lambda Z: lambda ^ {2} Z ^ {2})}$ Barcha uchun ${ displaystyle lambda}$ nolga teng bo'lmagan.

Ushbu egri chiziqlar uchun tezroq ikki baravar ko'paytirish formulalari va aralash qo'shimchalar formulalari Doche, Icart va Kohel tomonidan kiritilgan; ammo hozirgi kunda ushbu formulalar Daniel J. Bernshteyn va Tanja Lange tomonidan takomillashtirilgan (EFD havolasini quyida ko'ring).

Ichki havola

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

Izohlar

Adabiyotlar

• Kristof Dox, Tomas Ikart va Devid R. Kohel (2006). "Izogeniya dekompozitsiyalari bilan skalerni samarali ko'paytirish". Ochiq kalit kriptografiyasi - PKC 2006. Kompyuter fanidan ma'ruza matnlari. 3958. Springer Berlin / Heidelberg. 191–206 betlar. doi:10.1007/11745853_13. ISBN  978-3-540-33851-2.

• Daniel J. Bernshteyn va Tanja Lange (2008). Elliptik egri chiziqli bitta skalyar ko'paytishni tahlil qilish va optimallashtirish. ISBN  9780821857892.

Tashqi havolalar

• http://hyperelliptic.org/EFD/g1p/index.html
• http://www.hyperelliptic.org/EFD/g1p/auto-2dik.html