4.3 Elliptik egri chiziqlar
2
-2
0
4
6
4
8
10
-6
-10
-4 -2 0 2
-4
-8
Ushbu bo'limning qolgan qismida asosiy ta'riflar va umumiy operatsiyalar
4.3.1 Ta'rif
Haqiqiy sonlar ustidagi elliptik egri chiziqlar elliptik egri chiziq tenglamasini
qanoatlantiradigan nuqtalar to'plami (x, y) sifatida aniqlanadi:
Shunga qaramay, biz ta'kidlaymizki, cheklangan maydonlar ustidagi elliptik egri
chiziqlar kriptografik nuqtai nazardan yagona tegishlidir. Aniqroq qilib aytganda, elliptik
egri chiziqlarning ikkilik tasviri bu erda muhokama qilinadi, bu 10-bobda taqdim etiladigan
ish bilan bevosita bog'liq.
elliptik egri chiziqlar tushuntiriladi.
Elliptik egri chiziqlar haqiqiy sonlar, kompleks sonlar va boshqa har qanday sohada
aniqlanishi mumkin. Elliptik egri chiziqlarning geometrik xossalarini tushuntirish uchun,
avvalo, R haqiqiy sonlari ustida aniqlangan elliptik egri chiziqlarni ko'rib chiqamiz.
Elliptik egri chiziqlar nazariyasi so'nggi 150 yil davomida sonlar nazariyasi va algebrada
keng o'rganildi. Dastlab sof estetik sabablarga ko'ra moslashtirilgan boy va chuqur
nazariy asos ishlab chiqilgan. Elliptik egri chiziqli kriptotizimlar birinchi marta N. Koblits
[180] va V. Miller [236] tomonidan taklif qilingan. O'shandan beri ushbu mavzu bo'yicha
juda ko'p adabiyotlar to'plangan. Yaqinda elliptik egri kriptotizimlar kalitlarni yaratish,
imzolash va tekshirish kabi xavfsizlik dasturlari uchun keng tarqalgan.
y2 = x3 + ax + b
(4.7)
y2 = x3 - 9x + 9 y2 = x3 + 2x + 6
y2 = x3 + x + 9
73
4.3 Elliptik egri chiziqlar
4.1-rasm. Turli a va b uchun elliptik egri tenglama y2 = x3 + ax + b
0
-2
-4
-6
4
2
6
8
-2
0 2 4
-8
-4
-5
-15
-5
-10
5
0
10
15
5
0
Machine Translated by Google
Elliptik egri guruhlar qo'shimcha guruhlardir; ya'ni ularning asosiy vazifasi qo'shishdir. Egri chiziqqa
ikkita nuqta qo'shilishini tasavvur qilish uchun bu erda geometrik tasvir ko'rsatilgan. Eslatib o'tamiz,
P = (x, y) nuqtaning manfiyligi uning x o'qida aks etishidir: ÿP nuqta (x, ÿy) dir. Shuningdek, agar P
nuqtasi egri chiziqda bo'lsa, ÿP nuqtasi ham egri chiziqda bo'ladi.
Ushbu kichik bo'limning qolgan qismida egri chiziqning ikkita aniq nuqtasi uchun qo'shish
operatsiyasi tushuntiriladi. Egri chiziqqa ikkita nuqta qo'shish uchun ba'zi maxsus holatlar ham
tasvirlangan.
4.3.2 Elliptik egri amallar
bu yerda a va b haqiqiy sonlar. a va b ning har bir tanlovi 4.1-rasmda ko'rsatilganidek, boshqa elliptik
egri chiziq hosil qiladi. 4.7 tenglamadagi elliptik egri chiziq, agar 4a3 + 27b2 = 0 bo'lsa, guruh hosil
qiladi. Haqiqiy sonlar ustidagi elliptik egri chiziq guruhi tegishli elliptik egri chiziqdagi nuqtalardan va
abadiylik nuqtasi deb ataladigan maxsus O nuqtadan iborat.
• Aniq P va Q qo'shish: P va Q elliptik egri chiziqda ikkita alohida nuqta bo'lsin va P = -Q. Elliptik egri
chiziq guruhidagi qo'shish qonuni P + Q = R. P va Q nuqtalarini qo'shish uchun egri chiziqni
boshqa nuqtada kesib o'tadigan ikkita nuqta orqali chiziq o'tkaziladi, ÿR deb nomlanadi. Kerakli
nuqta bo'lgan R nuqtasini olish uchun ÿR nuqtasi x o'qida aks ettiriladi. Elliptik egri chiziqqa ikkita
alohida nuqta qo'shishning geometrik tasviri 4.2-rasmda ko'rsatilgan.
-4
Q
P
10
-8
R
8
-3
4
-1
5
6
R
-2
-10
-5
-6
2
1
3
0
R
Q
0
-15
-5
P
5
10
15
R
0
-10
-5
5
4. Matematik asos
74
4.2-rasm. Elliptik egri chiziqqa ikkita alohida nuqta qo'shish (Q = -P)
Machine Translated by Google
• P va ÿP ni qo‘shish: P va ÿP nuqtalarini qo‘shish uchun ikkita alohida P va Q
nuqtalarni qo‘shish usulini qo‘llash mumkin emas, chunki P va ÿP nuqtalaridan
o‘tuvchi chiziq vertikal chiziq bo‘lib, elliptik egri chiziq bilan kesishmaydi. 4.3-
rasmda ko'rsatilganidek, uchinchi nuqta. Elliptik egri chizig'i guruhiga cheksiz
O nuqtadagi nuqtani kiritishining sababi shu. Ta'rifga ko'ra, P +(ÿP) = O. Bu
tenglama natijasida elliptik egri guruhdagi P +O = P. O ning cheksizligidagi
nuqta elliptik egri chiziq guruhining additiv identifikatori deb ataladi. Barcha
aniq belgilangan elliptik egri chiziqlar qo'shimcha o'ziga xoslikka ega.
4.3-rasm. Q = -P bo'lganda ikkita P va Q nuqtalarini qo'shish
4.4-rasm. Elliptik egri chiziqdagi P nuqtani ikki barobarga oshirish
75
4.3 Elliptik egri chiziqlar
-15
-5
-5
R = P+P
6
-10
-5 -3
P
0
-10
8
6
8
Q
10
-2
2
0
P
= x3 - 8x + 8
-6
-4
1
2
2 y
R
P
-8
2 y
5
-2
-10
-4
-6
10
15
10
-2
0
-8
0 2 4 6
R = P+P = 2P
0
3 5
-4
R
R
5
4
4
-1
= x3 - 4x + 9
R
Machine Translated by Google
ÿR nuqtasi x o'qida kerakli nuqta bo'lgan R ga aks etadi.
Bu amal P nuqtani ikki barobarga oshirish deyiladi. • y = 0
bo‘lganda P(x, y) ni ikki barobarga oshirish: Agar P(x, y) nuqta uchun y = 0 bo‘lsa, u elliptik egri chiziqni
boshqa nuqtada kesib o‘tmaydi, chunki P da elliptik egri chiziqqa teguvchi chiziq vertikaldir. Ta'rifga
ko'ra, bunday P nuqtasi uchun 2P = O. Agar bu vaziyatda 3P ni topmoqchi bo'lsa, 2P + P qo'shilishi
mumkin. Bu P + O = P bo'ladi. Shunday qilib, 3P = P, 4P = O, 5P = P, 6P = O, 7P = P,
Elliptik egri chiziq guruhidagi nuqtani ikki barobar oshirish qonuni quyidagicha aniqlanadi: P + P =
2P = R. P(x, y) nuqtani o'ziga qo'shish uchun P nuqtada egri chiziqqa teginish chizig'i o'tkaziladi. y
= 0, u holda tangens chiziq elliptik egri chiziqni 4.4-rasmda ko'rsatilganidek, yana bitta ÿR nuqtasida
kesib o'tadi.
• y = 0 bo‘lganda P(x, y) ni ikki barobarga oshirish:
va boshqalar.
4.3.3 Elliptik egri chiziqli skalyar ko'paytirish
Elliptik egri guruhlarda ko'paytirish amali mavjud emas. Shu bilan birga, kP skalyar mahsulotini bir xil P
nuqtaning k nusxasini qo'shish yo'li bilan olish mumkin, buni oxirgi bo'limda tasvirlangan qo'shish va
ikki baravar formulalar yordamida amalga oshirish mumkin. Shunday qilib, shu tarzda olingan kP = P
+ P + .....P mahsuloti elliptik egri skaler ko'paytirishga aytiladi. 4.6-rasmda P nuqtaning 6 nusxasini
olish uchun skalyar ko'paytirish jarayoni ko'rsatilgan. Biroq, professional elliptik egri kriptotizimni amalga
oshirish uchun k ning ancha yuqori qiymatlari qo'llaniladi. Odatda, k ning bit uzunligi 160-521 bit
oralig'ida tanlanadi.
4. Matematik asos
76
4.5-rasm. y = 0 bo'lganda P(x, y) ni ikki barobarga oshirish
10
6
4
P
-10
-4 -2
2
0
2P = Q
-6
-8
8
2 y
-2
= x3 - 9x + 9
-4
0
2 4 6
Machine Translated by Google
4.4 GF (2m) ustidan elliptik egri chiziqlar
10
-15
5
5
-5
-5
15
5P6P
0
0
5
0
P
-5
15
10
-10
5
-15
P
15
-10
10
5P
-5
0
0
5
P
-10
10
0
-5
3P
0
5
15
-10
15
5
4P
5
-5
-10
P
5
-5
-5
P
-5
10
5
3P2P
-15
0
4P
5
-5
2P
P
-15
-5
15
0
-10
0
-15
5
0
0
-5
10
-15
(c) 3P
(d) 4P
(e) 5P
(f) 6P
77
(b) 2P
(a) P
4.4 GF (2m) ustidan elliptik egri chiziqlar
y2 = x3 ÿ 3x + 3 egri chizig‘i
4.6-rasm. Elliptik egri skalar ko'paytirish kP, k = 6 va elliptik uchun
b = 0 bo'lgan GF(2m) ichida a va b elementlarni tanlash orqali hosil bo'ladi .
y2 + xy = x3 + ax2 + b
GF (2m) asosiy maydoni 4.8- tenglamada ko'rsatilganidek, biroz sozlangan. Bu
Ikki xarakteristikasi tufayli elliptik egri chiziq uchun tenglama
Elliptik egri chiziqqa elliptik egri chiziqni qanoatlantiruvchi barcha nuqtalar (x, y) kiradi
(4.8)
GF(2m) ustidan tenglama (bu yerda x va y ÿ GF(2m)). Elliptik egri chiziq ustidagi guruh
Machine Translated by Google
(y2+y1)
(x2+x1)
y1
x1
Elliptik egri chiziqdagi nuqtalarni ikki yoki uchta koordinata yordamida ifodalash mumkin. Affin-
koordinatali tasvirda E(GF(2m)) dagi chekli nuqta ikkita koordinata x bilan belgilanadi; y ÿ GF(2m)
4.8 tenglamani qanoatlantiradi. Cheksiz nuqtaning affin koordinatalari yo'q.
Proyektivdan affinga: x = X/Z2; y = Y/Z3
Guruh qonuni uchun algebraik formulalar afin va proyektiv koordinatalar uchun farqlanadi.
Keyingi kichik bo'limlarda GF (2m) ustidan guruh qonuni afin koordinatalar tasviri yordamida
tushuntiriladi. Bir nechta proyektiv koordinatalar ko'rinishlari uchun guruh qonunlari §4.5 da
o'rganilgan.
4.4.2 Nuqtalarni ikki barobar oshirish
P(x1, y1) egri chiziqdagi nuqta bo'lsin. Agar x1 = 0 bo'lsa, u holda 2P = O. Agar x1 = 0 bo'lsa, R =
2P va R(x2, y2) quyidagicha beriladi:
4.4.1 Ballarni qo'shish
Affin koordinatalardan proyektiv koordinatalarga va aksincha o'tkazish uchun formulalar quyidagicha
berilgan:
x3 = m2 + m + x1 + x2 + a y3 =
m(x1 + x3) + x3 + y1
Haqiqiy sonlar ustidagi elliptik egri guruhlarda bo'lgani kabi, P + (ÿP) = O, bu erda O cheksizlik nuqtasi.
Bundan tashqari, elliptik egri guruhidagi barcha P nuqtalari uchun P + O = P.
Affin-to-proektiv: X = x; Y = y; Z=1
GF(2m) maydoni ustidagi proyektiv tekislik tushunchasidan foydalanishimiz mumkin [229].
Shunday qilib, nuqtani ikkita emas, balki uchta koordinata yordamida ifodalash mumkin. Keyin,
affin-koordinatali vakillik x bo'lgan P nuqta berilgan; y; mos keladigan X proyektiv koordinatali tasvir
mavjud; Y va Z shundayki,
m =
P(x; y) ÿ P(X; Y ;Z)
(4.9)
Eslatib o'tamiz, a - elliptik egri chiziq bilan tanlangan parametrlardan biri va m - P va Q orqali
o'tadigan chiziqning qiyaligi.
P = (x, y) nuqtaning manfiysi -P = (x, x + y). P = Q deb faraz qilsak, u holda R(x3, y3) = P(x1, y1)
+ Q(x2, y2) bu yerda:
GF(2m) tegishli elliptik egri chiziqdagi nuqtalardan, cheksizlikdagi nuqtadan iborat O.
m = x1 + x2
= m2 + m + a y2 =
(x1)2 + (m + 1) × x2
(4.10)
4. Matematik asos
78
Machine Translated by Google
E'tibor bering, E(Fq) elliptik egri chizig'i , ya'ni Fq ning tenglamani qanoatlantiradigan
barcha nuqtalarining yig'indisi . (4.10) faqat chekli ko'p bo'lishi mumkin. Har bir mumkin
bo'lgan juftlik (x, y) egri chiziqda bo'lsa ham, faqat q2 imkoniyatlar bo'lar edi . Aslini
olganda, E(Fq) egri chizig'i ko'pi bilan 2q +1 nuqtaga ega bo'lishi mumkin, chunki bizda
cheksizlikda bir nuqta va 2q juftlik (x, y) mavjud (har bir x uchun bizda y ning ikkita qiymati bor).
[q + 1 - 2 ÿq, q + 1 + 2 ÿq] oraliq Hasse intervali deyiladi.
Aniqroq aytganda, elliptik egri kriptotizimlarning xavfsizligi Elliptik egri diskret
logarifmik muammoga (ECDLP) tayanadi.
Cheklangan maydonlar misolida qilganimizdek, elliptik egri chiziqlardagi
elementning tartibi tushunchasini ham kiritishimiz mumkin. E(Fq) dagi P nuqtaning
tartibi eng kichik butun son n bo'lib, nP = 0 bo'ladi. Har qanday nuqtaning tartibi u
doimo aniqlanadi va #E(Fq) egri chizig'ining tartibini ajratadi. Bu, agar r va l butun
sonlar bo'lsa, rP = lP bo'lishini kafolatlaydi, agar r ÿ l (mod n) bo'lsa.
Agar a p(x) ning ildizi bo'lsa, bizda p (a) = 0 bo'ladi, bu shuni anglatadiki,
p(a) = a4 + a + 1 = 0.
4.4.4 Elliptik egri chiziqlar guruhlari va diskret logarifm masalasi
(4.12)
|#E(Fq) ÿ (q + 1)| ÿ 2 ÿq
F = GF(24) ibtidoiy uch a’zoli p(x) quyidagicha berilgan ikkilik chekli maydon
bo‘lsin,
p(x) = x4 + x + 1.
(4.11)
Egri chiziqdagi nuqtalarning umumiy soni, shu jumladan O nuqta egri chiziqning
tartibi deb ataladi. Buyurtma #E(Fq) deb yozilgan. Xasse tomonidan kashf etilgan
mashhur natija bu raqam uchun pastki va yuqori chegaralarni beradi.
Oxirgi bo'limda biz ikkita elliptik egri operatsiyani ko'rib chiqdik: nuqta qo'shish
va nuqtani ikki barobarga oshirish. Nuqtani qo'shish va ikki barobarga oshirish
operatsiyalari nuqtaning istalgan sonini (2P, 3P, kP va boshqalar) hisoblash uchun
ishlatilishi mumkin. KP nuqtasini shu tarzda aniqlash nuqtaning skalar ko'paytmasi
deb ataladi. Ushbu bo'limning qolgan qismida biz bunday elliptik egri operatsiyani
hisoblashning kichik misolini keltiramiz.
4.24 teorema. [227] E(Fq) nuqtalar soni #E (Fq) boÿlsin. Keyin,
4.4.5 Misol
Har bir kriptotizim murakkab matematik muammoga asoslangan bo'lib, uni hal
qilish uchun hisoblash mumkin emas. Diskret logarifm muammosi ko'plab
kriptotizimlar, shu jumladan Elliptik egri kriptotizimlar xavfsizligi uchun asosdir.
4.4.3 Elliptik egri chiziqning tartibi
(4.13)
79
4.4 GF (2m) ustidan elliptik egri chiziqlar
Machine Translated by Google
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a3
a3
a2
a2
a14
a15
y2 + xy = x3 + a13x2 + a6
yuqoridagi tenglamani quyidagicha qayta yozish mumkin
a ibtidoiy elementning ifodasi va vakolatlari.
Keling, to'plam sifatida aniqlangan supersingular bo'lmagan elliptik egri chiziqni ko'rib chiqaylik
(4.14) tenglamadan foydalanib, 4.1-jadvalda ko'rsatilganidek, endi F ning 15 nolga teng bo'lmagan
elementining har birini ifodalash mumkin. E'tibor bering, biz har qanday birini belgilashimiz mumkin
egri chiziq, shu jumladan cheksiz O nuqtasi. 4.1-jadvaldan foydalanib, biz buni ko'rishimiz mumkin, uchun
q = F ning 24 elementi faqat to'rtta koordinatadan foydalangan holda.
E'tibor bering, F dagi barcha elementlar 4.1-jadvalda qo'llanilgan uchta ko'rinishning istalgani
bilan tavsiflanishi mumkin, ya'ni polinom tasviri, koordinata.
a4 = a + 1.
(4.15)
E'tibor bering, (4.8) tenglamaning a va b koeffitsientlari uchun biz ni tanladik
misol, nuqta,
(4.14)
a13 va a6 qiymatlari mos ravishda. Bunday holda jami 14 ta yechim mavjud
qanoatlantiruvchi (x, y) ÿ F × F nuqtalari
Ikkilik maydon arifmetikasi uchun qo'shish ayirish bilan tengdir. Demak,
0
GF(2m) polinomidagi element
0
4. Matematik asos
(0011)
a2 + a (0110)
a
80
(0100)
a3 + a2 (1100)
a3 + a2 + a (1110)
a3 + a2 + 1 (1101)
(1000)
a3 + a2 + a + 1 (1111)
a3 + 1 (1001)
a + 1
ning tenglamasi. ((4.12))
1
(0000)
(0010)
a3 + a (1010)
4.1-jadval. Maydon elementlari F = GF(24), Primitiv trinomial yordamida aniqlangan
a2 + a + 1 (0111)
(0001)
Koordinatalar
a3 + a + 1 (1011)
a
a2 + 1 (0101)
Machine Translated by Google
2,
(a2)2 + a3a2 = (a3)3 + a13(a3)2 + a6
= a9 + a4 + a6
(0101) = (0101),
beri
(0011) + (0110) = (1010) + (0011) + (1100)
F4 ustidan (4.15) tenglamani qanoatlantiradi
(4.16)
(4.17)
Qayerda biz a15 = 1 identifikatoridan foydalanganmiz . Barcha o'n uchta chekli nuqtalar
qondirish tenglamasi (4.15) 4.7-rasmda ko'rsatilgan.
Endi P = (a3, a2) nuqtani ikki barobarga oshirish uchun (4.10) tenglamadan foydalanamiz . Foydalanish
yana bir bor 4.1-jadvalni olamiz,
a
a
a
11 a
a
12 a
2 a
a
10 a
a
a
a
a
x
a
a
y
a
12 a
a
0 a
a
a
a
a
3 a
a
a
a
14 a
a
a
y2 + xy = x3 + a13x2 + a6
P = (xp, yp) = (a3, a2)
a4 + a5 = a9 + a19 + a6
81
4.4 GF (2m) ustidan elliptik egri chiziqlar
4.7-rasm. Tenglamaning elliptik egri chizig'idagi elementlar (4.15)
9
15
9
6
4
11
8
10
4
3
5
7
5
13
14
15
2
6
8
13
7
Machine Translated by Google
p
yp
xp
+ xp +
Shubhasiz, haqiqiy kriptografik dasturda n parametri etarlicha katta tanlanishi kerak, shunda
qidirish jadvalining bunday yondashuvini samarali yaratish imkonsiz bo'ladi. Bugungi amaliyotda n ÿ
2160 etarli ekanligini isbotladi.
Elliptik egri chiziqlar ustida Abel guruhini hosil qilish uchun elliptik egri chiziq guruhi
qonunini aniqlash kerak edi. Aniqroq aytganda, (4.9) va (4.10) tenglamalarning
nuqta qo'shish va nuqta ikkilanish ibtidoiylarini aniqladik. Biroq, bu tenglamalarning
hisoblash qiymati qimmat maydonning teskari operatsiyasini va bir nechta maydonni
ko'paytirishni hisoblashni o'z ichiga oladi.
Dala ko'paytirishning hisoblash qiymatiga nisbatan in-versiyaning hisoblash
qiymati sifatida belgilangan munosabat (I/M) apparat va dasturiy ta'minotni amalga
oshirishda mos ravishda 6 va 20 dan yuqori bo'lganligi sababli, muqobil nuqta
ko'rinishlarini topish uchun kuchli motivatsiya mavjud. Bu qimmat dala inversiyalarini
kamroq qimmat maydonlarni ko'paytirish orqali savdo qilish imkonini beradi.
E'tibor bering, §4.4.3 da aytib o'tilganidek, P ning n tartibi #E(Fq) egri chizig'ining
tartibini ajratadi. 4.2-jadvalda P ning barcha oltita chekli karralari keltirilgan.
(4.18)
§4.4.3 da aytib o'tganimizdek, biz P ni uning skalyar ko'paytmalariga qo'shishda
davom etishimiz mumkin, lekin oxir-oqibat, n ÿ #E(Fq) skalyar ko'paytirishdan so'ng,
natijada cheksiz O nuqtaga erishamiz. Eslatib o'tamiz, n butun soni P nuqtaning
tartibi deb ataladi. Qo'ldagi holat uchun P ning asosiy tartibi k = 7 bo'ladi.
Yuqorida olingan natija haqiqatda (4.15) tenglamaning elliptik egri chizig'idagi nuqta
ekanligini 4.7-rasmdan tekshirish mumkin.
4.4-§da boshida ko'rganimizdek, ikkita koordinatada elliptik nuqta tasviri afin
tasvir, uchta koordinatada ekvivalent nuqta tasviri esa proyektiv tasvir deb ataladi.
+
p
p
x2p = x2
b x2
= (a3)2 + a6 · (a3)ÿ2 = a6
+ a6 · aÿ6 = a6 + 1 = a13 y2p = x2 x2p +
x2p = a6 + a3 + a2 · aÿ3 a13 + a13 =
a6 + a3 + aÿ1 a13 + a13 = a6 + a1 +
a12 + a13 = a6
3P
5P
6P
4.2-jadval. (4.16) tenglamaning P nuqtasining skalar karralilari
P 2P
4P
82
4. Matematik asos
(a3, a2) (a13, a6) (a14, a9) (a14, a4) (a13, a15) (a3, a6)
4.5 Nuqtalarni ifodalash
Machine Translated by Google
X
(X1, Y1,Z1) ÿ (X2, Y 2,Z2)| Agar X1 = lc X2, Y1 = ldY2, Z1 = lZ2 bo'lsa.
Y
2
Ushbu bo'limning qolgan qismida tushuntirilganidek, proyektiv guruh qonuni
maydonni ko'paytirishning umumiy sonini ko'paytirish narxida maydon
inversiyasidan foydalanmasdan amalga oshirilishi mumkin. Darhaqiqat, maydon
inversiyasi faqat proyektiv tasvirdan affin tasvirga2 o‘tkazilganda talab qilinadi,
bu biz ketma-ket ko‘p nuqta qo‘shish va ikkilanishni amalga oshirishni
rejalashtirayotgan vaziyatlarda (masalan, elliptik egri chiziqli skalyar ko‘paytirishda)
qimmatli bo‘ladi.
(X : Y : Z) = (lcX, ldY, lZ) : l ÿ Kÿ .
proyektiv nuqta deb ataladi [133] va (X, Y,Z) bunday sinfning vakili nuqtasi, ya'ni
sinf ichidagi har qanday nuqta vakili nuqta hisoblanadi.
= {(X : Y : Z) : X, Y,Z ÿ K,Z = 0} ,
biz P(K)ÿ nuqtasi va affin nuqtalar to'plami o'rtasida yakkama-yakka muvofiqlikni
olamiz ,
Xususan, agar Z = 0 bo'lsa, ( Zd , 1) ekvivalentlik sinfining (X : Y : Z) vakili
nuqtadir.
A(K) = {(x, y : x, y ÿ K)} .
Kÿ maydonidagi har bir mumkin bo'lgan l uchun ,
P(K) ÿ
Ekvivalent sinf
4.5.1 Proyektiv koordinatalar
Zc ,
c va d K maydonida musbat butun sonlar bo‘lsin. K3 \ {(0, 0, 0)} ekvivalent sinfini
quyidagicha aniqlash mumkin:
Shuning uchun, agar biz barcha proyektiv nuqtalar to'plamini aniqlasak (ekvivalent sinflar)
Har bir affin nuqtasi noyob ekvivalentlik sinfi bilan birma-bir bog'lanishi mumkinligini ko'rsatish mumkin.
Keyin har bir elliptik nuqta mos keladigan ekvivalentlik sinfini qondiradigan uchlik bilan ifodalanadi. E'tibor
bering, bu proyektiv ko'rinishdagi qo'shish va ikkilamchi amallarni qayta belgilash zarurati tug'iladi.
Affin koordinata tizimidagi har bir nuqta, xususan, ekvivalentlik sinfi tomonidan
belgilangan to'plamga mos keladi. P(K)0 = {(X : Y : Z) : X, Y,Z ÿ K,Z = 0} ga
tegishli nuqtalar toÿplami cheksizlikdagi chiziq deb ataladi, chunki bu sinf hech
qanday element bilan mos kelmaydi. affin nuqtalari to'plami.
83
4.5 Nuqtalarni ifodalash
§4.4 da affindan proyektiv koordinatalarga va aksincha aniq konvertatsiya tenglamalari bayon etilgan.
Machine Translated by Google
X3 = X4
Y
1
1
1
X
1
Z3 = C2;
Z3 = X2
3
2
X3 = A2 + D + E; F = X3 + X2 · Z3;
1
1 2
2
3
Zc
Y2) = (X3 : Y3 : Z3) 8 maydonning hisoblash qiymatida bajarilishi mumkin
(4.19)
demak, bunday tasvirlashda nuqta qo'shish algoritmining ta'rifi.
LD koordinatalari apparatni amalga oshirish uchun juda jozibali, chunki
· Z2
);
P. 2(X1 : Y1 : Z1) = (X3 : Y3 : Z3) ni ikki baravar koÿpaytirish mumkin .
elliptik egri konstanta b bilan maydonni ko'paytirish [213],
aralash koordinatalarda qo'shishni hisoblash algoritmlari, ya'ni bir nuqta
x ni va y ni Zd ga almashtirish orqali proyektiv koordinatalar . Doimiy qiymatlar
Y
4.5.2 L'opez-Dahab koordinatalari
(4.20)
(4.21)
+ b · Z4
Y/Z2. Shuning uchun elliptik egri chiziq tenglamasi (4.8) LD proyektiviga ko'rsatilgan
U holda ÿP = (X1 : X1 + Y1 : Z) nuqta nuqtaning qo‘shish teskari nuqtasidir.
D = B2 · (C + aZ2
3 ; Y3 = (E + Z3) · F + G
+ b · Z2
Lopez-Dahab (LD) proyektiv koordinatalarida [211] proyektiv nuqta (X:
egri chiziqdagi P nuqta, u P +O = O+P = P ekanligini tasdiqlaydi. P = (X1 : Y1 : Z1) bo'lsin.
1 ,
affin koordinatalarida, ikkinchisi esa proyektiv koordinatalarda berilgan.
c va d elliptik egri arifmetik xarakteristikani aniqlaydi va
+ XY Z = X3Z + aX2Z2 + Z4
1 ,
Agar Q = ÿP bo'lsa, nuqta qo'shish primitiv (X1 : Y1 : Z1) + (X2 :
A = Y2 · Z2
E = A · C;
va d = 1, yakobiylar, c = 2 va d = 3 va Lo´pez-Dahab (LD) koordinatalari bilan, c = 1 va d =
2. Oxirgi koordinatalar tizimi taklif qiladi.
E (K) elliptik egri chizig'i uchun Weiershtrass tenglamasini quyidagicha aniqlash mumkin
2 umumiy maydonni ko'paytirish va ikkitadan iborat hisoblash qiymatida amalga oshiriladi
C = Z1 · B;
· (Y
+ Y1; B = X2 · Z1 + X1;
va Q = (X2 : Y2 : 1) 4.19 egri chizig'iga tegishli ikkita ixtiyoriy nuqta bo'lsin.
Y: Z) bilan Z= 0 affin koordinatalariga mos keladi x = X/Z va y =
Eng mashhur proyektiv koordinatalar tizimi c = 1 bo'lgan standartdir
koordinatalarini quyidagicha yozish mumkin:
Y3 = Y
ko'paytirish,
+ X3 + Z3) + Z2
nuqta qo'shish amalini bajarish uchun ular faqat 8 ta maydonni ko'paytirishdan foydalanadilar.
Cheksizlik nuqtasi endi O = (1 : 0 : 0) shaklida ifodalanadi. Har qanday o'zboshimchalik uchun
G = (X2 + Y2) · Z2
4. Matematik asos
84
Machine Translated by Google
4.6.1 Ikkilik vakillik
bj2j P = 2(...2(2blÿ1P + blÿ2P) + ...) + b0P.
KP elliptik operatsiyasini hisoblashning an'anaviy usuli bj2jga asoslanadi ,
bunda har bir bj ÿ {0, 1}, k ning
ikkilik ko'rinishida. Agar k = bo'lsa, kP ni
quyidagicha hisoblash mumkin: [228]:
Bu usul l nuqtani ikki baravar oshirishni va wk - 1 nuqta qo'shimchalarini talab
qiladi, bu erda wk - skaler k ning ikkilik ko'rinishining Hamming vazni
(koeffitsientlarning umumiy soni bj = 1).
bu yerda skalyar k uning ikkilik kengayishi yordamida ifodalanadi, ya'ni k = bn2n
+ bnÿ1 + 2nÿ1 +. . . + b12 + b0 bu erda bi ÿ [0, 1].
kP =
anxn+anÿ1xnÿ1+. . .+a2x2+a1x+a0 = a0+(a1+(a2+(. . .+(anÿ1+(an+x)x). .)x)x)x.
Skayar ko'paytirishni samarali hisoblash bo'yicha hisobot qilingan ishlarning
aksariyati Horner ko'pnomli tasviriga asoslangan,
Ko'rsatkichni qayta kodlash yordamida keyingi nuqta qo'shimchalari sonini
kamaytirish mumkin [158, 240, 80, 180]. Qayta kodlash usullari identifikatsiyadan
foydalanadi
eksponentning siyrak tasvirini olish uchun 1 lar blokini yiqitish. Shunday qilib, {0,
1, ÿ1} raqamlaridan foydalangan holda eksponentning ortiqcha belgili raqamli
tasviri olinadi. Masalan, (011110) qayta kodlanishi mumkin
kabi
4.6.2 Qayta kodlash usullari
lÿ1
2i+jÿ1 + 2i+jÿ2 + · · · + 2i = 2i+j ÿ 2i
| 