Uchga yo'naltirilgan Doche-Icart-Kohel egri chizig'i - Tripling-oriented Doche–Icart–Kohel curve - Wikipedia

The uch baravar yo'naltirilgan Doche-Icart-Kohel egri chizig'i ning shakli elliptik egri chiziq so'nggi paytlarda ishlatilgan kriptografiya; bu ma'lum bir turdagi Weierstrass egri chizig'i. Muayyan sharoitlarda ba'zi operatsiyalar, qo'shish, ikki yoki uch baravar oshirish kabi, ushbu shakl yordamida tezroq hisoblash mumkin. Uch marta yo'naltirilgan Doche-Icart-Kohel egri chizig'i, ko'pincha qisqartma bilan chaqiriladi. 3DIK Kristof Dox, Tomas Ikart va Devid R. Koxel tomonidan kiritilgan [1]

Ta'rif

Uchlikka yo'naltirilgan Doche-Icart-Kohel tenglamasining egri chizig'i

Ruxsat bering bo'lishi a maydon ning xarakterli turli xil shakllar 2 va 3.

Elliptik egri chiziq uch baravar yo'naltirilgan Doche-Icart-Kohel shakli bilan belgilanadi tenglama:

bilan .

Umumiy nuqta P kuni bor affin koordinatalari . "Cheksizlik nuqtasi" ifodalaydi neytral element guruh qonuni uchun va u yozilgan proektiv koordinatalar O = (0: 1: 0) sifatida. Nuqtani inkor etish P = (xy) ushbu neytral elementga nisbatan -P = (x, −y).

Guruh qonuni

Uchlik yo'naltirilgan Doche-Icart-Kohel shaklidagi elliptik egri chiziqni ko'rib chiqing affin koordinatalari:

Boshqa elliptik egri shakllarida bo'lgani kabi, nuqta qo'shish yoki ikki baravar oshirish kabi nuqtalar orasidagi ba'zi "operatsiyalarni" aniqlash mumkin (Shuningdek qarang Guruh qonuni ). Keyingi bo'limlarda fikrlarni qo'shish, inkor qilish va ikki baravar oshirish formulalari keltirilgan. Qo'shish va ko'paytirish formulalari ko'pincha boshqa operatsiyalar uchun ishlatiladi: nuqta berilgan P elliptik egri chiziqda hisoblash mumkin [n] P, qayerda n bu tamsayı, qo'shish va ikki baravar oshirishdan foydalangan holda; ko'p sonli ballarni hisoblash muhim ahamiyatga ega egri chiziqli kriptografiya va Lenstra elliptik egri faktorizatsiyasi.

Qo'shish

Berilgan va kuni , nuqta koordinatalariga ega:

Ikki baravar

Bir nuqta berilgan kuni , nuqta koordinatalariga ega:

Salbiy

Bir nuqta berilgan kuni , uning inkor neytral elementga nisbatan bu .

Da berilgan boshqa formulalar ham mavjud [2] uch karra yo'naltirilgan Doche-Icart-Kohel egri chiziqlari uchun tez uch marta ishlash va aralash qo'shimchalar.

Yangi Jacobian koordinatalari

Ushbu egri chiziqlarda hisoblash uchun odatda nuqta ko'rsatilgan yangi Jacobian koordinatalari (Jn):

yangi Jacobian koordinatalarida nuqta shaklga ega ; bundan tashqari:

har qanday kishi uchun .

Bu, masalan, nuqta degan ma'noni anglatadi va nuqta (uchun ) aslida bir xil.

Shunday qilib, an afinaviy nuqta kuni kabi yangi Jacobian koordinatalarida yozilgan , qayerda va ; shu tarzda, uchun tenglama bo'ladi:

Atama egri chiziqdagi nuqta aralash bo'ladi qo'shimcha (ya'ni har xil ikkita nuqta orasidagi qo'shimcha koordinatalar tizimi ) yanada samarali.

The neytral element yangi Jacobian koordinatalarida .

Algoritmlar va misollar

Qo'shish

Quyidagi algoritm ikki nuqta yig'indisini aks ettiradi va uchburchak yo'naltirilgan Doche-Icart-Kohel shaklida elliptik egri chiziqda. Natijada nuqta paydo bo'ladi .Bu taxmin qilinmoqda va bu .Bu amalga oshirish qiymati 7M + 4S + 1 * a3 + 10add + 3 * 2 + 1 * 4 ni tashkil etadi, bu erda M ko'paytmalarni, S kvadratlarni, a3 doimiy a ga ko'paytishni bildiradi.3, qo'shish kerakli qo'shimchalar sonini anglatadi.

Misol

Ruxsat bering va elliptik egri chiziqdagi affin nuqtalari :

.

Keyin:

Bunday holatda e'tibor bering Natijada paydo bo'lgan nuqta , affin koordinatalarida .

Ikki baravar

Quyidagi algoritm nuqtaning ikki baravar ko'payishini anglatadi uchburchakka yo'naltirilgan Doche-Icart-Kohel shaklidagi elliptik egri chiziqda. , .Bu amalga oshirish qiymati 2M + 7S + 1 * a2 + 1 * a3 + 12add + 2 * 2 + 1 * 3 + 1 * 8; bu erda M ko'paytmalarni, S kvadratlarni, a2 va a3 doimiylarni ko'paytmalarni a ni bildiradi2 va a3 navbati bilan va qo'shimchalar qo'shimchalarni bildiradi.

Misol

Ruxsat bering nuqta bo'ling .

Keyin:

E'tibor bering, bu erda nuqta affine koordinatalarida Natijada paydo bo'lgan nuqta , affin koordinatalarida .

Weierstrass formasi bilan ekvivalentlik

Har qanday elliptik egri chiziq ikki tomonlama teng Weierstrass shaklida yozilgan boshqasiga.

Quyidagi o'ralgan uch baravar yo'naltirilgan Doche-Icart-Kohel egri chizig'i:

tomonidan Weierstrass shakliga aylantirilishi mumkin xarita:

Shu tarzda, shu ravishda, shunday qilib bo'ladi:

.

Aksincha, Weierstrass shaklida elliptik egri berilgan:

,

quyidagi aloqadan foydalanib "mos keladigan" uchlikka yo'naltirilgan Doche-Icart-Kohel egri chizig'ini topish mumkin:

qayerda a a ildiz polinomning

qayerda

bo'ladi j-o'zgarmas egri chiziq egri chizig'ining .

E'tibor bering, bu holda berilgan xarita nafaqat birja tengligi, balki an bo'ladi izomorfizm egri chiziqlar orasidagi.

Ichki havola

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

Izohlar

  1. ^ Kristof Dox, Tomas Ikart va Devid R. Kohel, Izogeniya dekompozitsiyalari bilan skalerni samarali ko'paytirish
  2. ^ Kristof Dox, Tomas Ikart va Devid R. Kohel, Izogeniya dekompozitsiyalari bilan skalerni samarali ko'paytirish, 198-199 bet

Tashqi havolalar

Adabiyotlar

  • Kristof Dox; Tomas Ikart va Devid R. Kohel (2006). Izogeniya dekompozitsiyalari bilan skalerni samarali ko'paytirish (PDF). paydo bo'ldi PKC 2006 yil, 3958-sonli LNCS (Ma'ruzalar seriyasi, kompyuter fanlari) qismining bir qismi. Springer Verlag. 285-352 betlar.
  • Daniel J. Bernshteyn, Tanja Lange (2007). Elliptik egri chiziqli bitta skalyarli ko'paytirishni tahlil qilish va optimallashtirish (PDF). G.L.Mullen, D. Panario, I.E.larda paydo bo'lgan. Shparlinski (tahr.), Finite Fields and Applications (8-sonli xalqaro konferentsiya, Fq8, Melburn, Avstraliya, 2007 yil 9-13 iyul). Matematika fanining tasnifi.
  • D.J.Bernshteyn, P.Birkner, T.Lange va C.Peters (2007). Ikki asosli elliptik-egri chiziqli bitta skalyarli ko'paytirishni optimallashtirish (PDF). K. Srinatan paydo bo'ldi, C. Pandu Rangan, M. Yung (Eds.), Hindistondagi Kriptologiya bo'yicha 8-Xalqaro konferentsiya materiallari: Kriptologiyada taraqqiyot (Indocrypt 2007) 9-13 dekabr 2007, Chennai, Hindiston. Springer.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  • http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html