6-ma’ruza Mavzu: Elliptik egri chiziqlarga asoslangan ochiq kalitli shifrlash algoritmlari

Elliptik egri chiziqqa tegishli ratsional nuqtalarni aniqlash usullari
Oldindan shuni aytish lozimki, hozirgi kunda

tenglamaning barcha ratsional yechimlarini topish matematikada nomalumligicha qolib kelmokda. Lekin, quyidagi ikkita usuldan foydalanib, ratsional yechimlarni topish mumkin.

1- usul. Tanlangan y²=x³+ax+b tenglamaga x_i qiymatlar berilib, tenglamaning o‘ng tomoni to‘la kvadrat tashkil qilishini tekshiriladi. Agar qandaydir x_k qiymatda to‘la kvadrat tashkil qilsa, u holda tenglamaga tegishli nuqta kordinatalarini
( ; ) (12.4)
juftliklar bilan fiksirlanadi. Bu usul tenglama koeffitsiyentlariga biror shart avvaldan berilgan holda yaxshi natija beradi. Ya’ni koeffitsentlarga mos tenglama qurib, keyin shu tenglamaga tegishli nuqta qidirish usuli hisoblanadi.

2- usul. Bu usul topilishi kerak bo‘lgan nuqtaga biror shart qo‘yilganda foydalaniladigan usul hisoblanadi. Ya’ni nuqta koordinatalari (x; y) va tenglamaning bitta a –koeffitsentini fiksirlab: (a; x; y R) ,


b=y²-x³-ax (12.5)
formula orqali b–koeffitsiyent hisoblab topiladi va uning asosida tenglama quriladi.
Elliptik egri chiziqlarning ratsional 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, Ye- egri chiziqni uchinchi nuqtada kesib o‘tadi. Bu nuqtani - o‘qiga simmetrik ko‘chiriladi va hosil bo‘lgan :

nuqtani, va nuqtalarning elliptik egri chiziq ustida yig‘indisi deb elon qilinadi:

Bu grafik tenglama bitta yechimga 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‘xtalinadi. 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 nuqtani -o‘qiga nisbatan simmetrik ko‘chiriladi va bu nuqta deb elon qilinadi:

So‘ngra, -ni topish uchun, , shu kabi , 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 - nuqtaga yo‘naladi. Cheksizlikdagi - nuqta bilan -nuqtani qo‘shishni + 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, sungra + -yig‘indini ifodalovchi nuqtani topish uchun bu - nuqtani - o‘qiga simmetrik akslantirilsa, - nuqta bilan ustma-ust tushadi, ya’ni kiritilgan qo‘shish amali qoidasiga ko‘ra + = tenglik o‘rinli bo‘ladi. Bu - nuqtani - o‘qiga nisbatan akslantirilsa yana qarama – qarshi tomon cheksizligidagi (- ) - nuqtaga yo‘naladi. Ammo, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilganda (- )+ = tenglikning o‘rinli bo‘lishiga keltirilgan fikr mulohozalar asosida ham ishonch hosil qilish mumkin.