Elliptik egri chiziqqa tegishli ratsional nuqtalarni aniqlash va qo

Elliptik egri chiziqqa tegishli ratsional nuqtalarni aniqlash va qo'shish.
Oldindan shuni aytish lozimki, hozirgi kunda
tenglamaning barcha rastional yechimlarini topish matematikada noma'lumligicha qolib kelmokda. Lekin, quyidagi ikkita usuldan foydalanib, rastional echimlarni topish mumkin.
1-usul. Tanlangan y2=x3+ax+b tenglamaga xi qiymatlarni berib, tenglamaning o'ng tomoni to'la kvadrat tashkil qilish tekshiriladi. Agar biror xk qiymatda tenglikni o'ng tomonidagi ifodaning qiymati to'la kvadrat tashkil qilsa, u holda tenglamaga tegishli nuqta koordinatalarini
(; ) (5)
juftliklar bilan fiksirlanadi.
2- usul. Bu usulda nuqta koordinatalari (x; y) va tenglamaning bitta a –koeffistientini fiksirlab: (a; x; y R) ,
b=y2-x3-ax (6)
formula orqali b–koeffistient hisoblab topiladi va uning asosida tenglama quriladi. Elliptik egri chiziq koeffistientlarini olingan rastional koordinatali nuqta orqali aniqlashning bunday usuli samarali hisoblanadi.
Elliptik egri chiziq rastional nuqtalarini qo'shish
Ushbu
elliptik egri chiziqda , nuqtalar berilgan bo'lsin. Bu nuqtalar orqali to'g'ri chiziq o'tkaziladi. U holda o'tkazilgan chiziq, E - egri chiziqni uchinchi nuqtada kesib o'tadi. Bu nuqtani - o'qiga simmetrik ko'chiriladi va hosil bo'lgan:
nuqta va nuqtalarning elliptik egri chiziq ustida yig'indisi deb e’lon qilinadi:
Bu grafik tenglama bitta echimga ega bo'lgan hol uchun keltirildi.
Yuqorida elliptik egri chiziqda koordinatalari har xil bo'lgan, ya’ni bo’lgan nuqtalar yig’indisini topish ko’rib chiqildi. Endi qanday amalga oshirilishi haqida to'xtab o'tiladi. Buning uchun elliptik egri chiziqdagi -nuqta orqali urinma to'g'ri chiziq o'tkaziladi. Bu urinma elliptik egri chiziq grafigidagi ikkinchi qismni (giperbola qismida) biror nuqtada kesib o'tadi. Ana shu kesib o'tgan nuqta -o'qiga nisbatan simmetrik ko'chiriladi va bu nuqta [2]P deb e’lon qilinadi:
So’ngra, [3]P ni topish uchun, [3]P=[2]P+P, shu kabi [4]P=[3]P+P, [5]P=[4]P+P va hokazolar amalga oshiriladi.
Har doim ham va nuqtalar orqali o'tuvchi to'g'ri chiziq elliptik egri chiziqni uchinchi nuqtada kesib o'tavermaydi. Masalan, va nuqtalardan o’tuvchi to’g’ri chiziq -o’qiga perpendikulyar bo’lib, u elliptik egri chiziqni uchinchi nuqtada kesib o’tmaydi:
Bunday holda o'tkazilgan to'g'ri chiziq elliptik egri chiziqni cheksizlikda kesib o'tadi deb qabul qilinib, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilgan deb hisoblanadi, ya’ni cheksizlikdagi barcha nuqtalar, elliptik egri chiziq nuqtalari ustida aniqlangan qo'shish amaliga nisbatan, haqiqiy sonlarni qo'shishdagi nol qiymati kabi xossaga ega. Haqiqatan ham, va nuqtalardan o'tuvchi to'g'ri chiziq -o'qiga perpendikulyar bo'lib, u elliptik egri chiziqni uchinchi nuqtada kesib o'tmay, cheksizlikdagi 0E nuqtaga yo'naladi. Cheksizlikdagi 0E nuqta bilan -nuqtani qo’shishni 0E + shaklida ko'rib chiqadigan bo'lsak, bu nuqtalardan o'tuvchi to'g'ri chiziq -o'qiga perpendikulyar bo'lib, elliptik egri chiziqni - nuqtada kesib o'tadi, so'ngra 0E + -yig'indini ifodalovchi nuqtani topish uchun bu - nuqta - o'qiga simmetrik akslantirilsa, - nuqta bilan ustma-ust tushadi, ya’ni kiritilgan qo'shish amali qoidasiga ko'ra 0E += tenglik o'rinli bo'ladi. Bu 0E nuqta- o'qiga nisbatan akslantirilsa, yana qarama-qarshi tomon cheksizligidagi (-0E) - nuqtaga yo'naladi. Ammo, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilganda (-0E)+= tenglikning o'rinli bo'lishiga keltirilgan fikr-mulohozalar asosida ham ishonch hosil qilish mumkin.
Bevosita hisoblashlar bilan ko'rsatish mumkinki, elliptik egri chiziq nuqtalarini qo'shish amali Abel gruppasini tashkil etadi, ya’ni elliptik egri chiziqqa tegishli bo’lgan - nuqtalar uchun:
1) kommutativlik ;
2) assostiativlik ;
3) nol elementining mavjudligi a+ 0E = a;
4) teskari (qarama-qarshi ishorali) elementning mavjudligi
a+(-a)= 0E kabi Abel gruppasining aksiomalari o'rinlidir.
Elliptik egri chiziqning nuqtalarini qo'shish formulalari uning geometrik ma’nosidan kelib chiqqan holda keltirib chiqariladi. Ko'rib o'tilganlarga muvofiq, agar va - nuqtalar -elliptik egri chiziqda yotsa, ya’ni nuqtalar bo'lsa, unda ular orqali kesuvchi to'g'ri chiziq o'tkazilib, bu kesuvchi to'g'ri chiziq -elliptik egri chiziqni biror uchinchi nuqtada kesib o'tadi.
Tasdiq. Agar nuqtalar rastional koordinatali bo'lsa, u holda nuqta koordinatalari ham rastional bo'ladi.
Isboti. nuqtalar orqali o’tuvchi to'g'ri chiziqning umumiy ko'rinishi:
ifodaga ega bo'lib, bu erda – koeffistientlar va nuqtalarning koordinatalari orqali ifodalanadi. , -nuqtalar chiziqqa tegishli. Bundan esa:
va ,
ekanligi kelib chiqadi.
Shuningdek,
.
Shunday qilib, y = k x + d to’g’ri chizig'i tiklab olindi. Keyingi qadamda
y = kx+d – ifoda
elliptik egri chiziqning tenglamasiga qo'yiladi, yani
u holda uchinchi tartibli tenglama uchun Viet teoremasiga ko'ra:
tenglik o'rinli bo’lib, bu oxirgi tenglikda - rastional sonlar bo'lgani uchun, ham rastional son bo'ladi. Xuddi shuningdek,
ifodaga ko'ra - sonining ham rastional ekanligi kelib chiqadi.
Bu keltirilgan tasdiq isbotidan esa yig’indi nuqta koordinatasini hisoblash formulasini keltirib chiqarish mumkin. nuqta – nuqtani - o'qiga simmetrik ko’chirishdan hosil bo'lar edi. Natijada, yig'indi nuqtaning koordinatalari , deb belgilansa, bu koordinatalar quyidagi formulalar orqali topiladi:
chunki Bu formulada -koeffistienti qiymatining o’rniga qo'yilsa, quyidagi tengliklar hosil bo'ladi:
(7)
Bu erda, .
Agar bo’lsa, u holda kesuvchi to’g’ri chiziq o'rniga urinma o'tkazilib, quyidagi formulalar keltirib chiqariladi:
(8)
Shunday qilib, hech bo'lmasa bitta - rastional nuqta elliptik egri chiziqdagi nuqta bo'lsa, u holda (7), (8) - formulalar orqali [2]P-ni topish uchun, [2]P=P+P, [3]P-ni topish uchun, [3]P=[2]P+P, shu kabi [4]P=[3]P+P, [5]P=[4]P+P va hokazolarni topishimiz mumkin bo’ladi.
Shuni alohida ta’kidlash kerakki, keltirilgan (7) va (8) formulalar (3) tenglamaga nisbatan keltirib chiqarildi. Endi elliptik egri chiziqning kriptografiyada keng qo’llaniladigan
tenglamasi uchun rastional nuqtalarini qo'shish formulalari keltirib o'tiladi:
(9)
bu erda, .
Agar bo'lsa, u holda
(10)
Oldindan berilgan - EECh rastional nuqtalarini topishning samarali usulini aniqlash hozirgi kunda sonlar nazariyasining muammolaridan biri hisoblansada, egri chiziqqa tegishli bitta nuqta topilsa, qolganlari (7), (8) formulalar orqali aniqlanadi.
EECh nuqtalarini qo'shish jarayonida quyidagi ikkita holat bo'lishi mumkin:
Biror n –qadamda [n]P= 0E tenglik bajarilishi mumkin;
[2]P, [3]P, [4]P va hokazo [n]P – nuqtalar har xil qiymatga ega bo’lishi mumkin.
1.4-ta’rif: Agar barcha holatlarda [m]P0E bajarilib, [n]P = 0E bo'lsa, u holda – nuqta – chekli tartibga ega deyiladi.
Xulosa
Xulosa o'rnida aytish joizki elliptik egri chiziqlar matematik yechimlarini hisoblash murakkabligi va uning affin nuqtalari (yechimlari) ning gruppa, abel gruppasi va maydon hosil qilishi (albatta xususiy holatlar uchun, barcha E | K larda ham emas) kriptologiyada ahamiyati katta. Elliptik egri chiziqning aynan yuqorida aytib o'tilgan ko'rinishlarini (affin nuqtalarini) shifrlash algoritmlari va elektron raqamli imzo protokollarida qo'llab ularning samaradorligi va bardoshliligini yanada oshirish mumkin.
Adabiyotlar
Akbarov D.Y – Axborot xavfsizligini ta’minlashning kriptografik usullari.
“UDK – 004.421.5 Qo'lyozma huquqi asosida”gi Magistrlik akademik darajasini olish uchun yozilgan dissertatsiya.
http://fayllar.org
|