Texnologiyalari universiteti kriptografiyaning matematik asoslari

Elliptik egri chiziqqa tegishli rasional nuqtalarni aniqlash usullari Oldindan shuni aytish lozimki, hozirgi kunda
y ²  x³  ax² bx  c,
tenglamaning barcha rasional yechimlarini topish matematikada nomalumligicha qolib kelmokda. Lekin, quyidagi ikkita usuldan foydalanib, rasional yechimlarni topish mumkin.
1-usul. Tanlangan y²=x³+ax+b tenglamaga x_i qiymatlarni berib, tenglamaning o‘ng tomoni to‘la kvadrat tashkil qilish tekshiriladi. Agar biror x_k qiymatda tenglikni o‘ng tomonidagi ifodaning qiymati to‘la kvadrat tashkil qilsa, u holda tenglamaga tegishli nuqta koordinatalarini
( x_k ; y_k   x_k³  ax_k b ) (5)
juftliklar bilan fiksirlanadi.
2- usul. Bu usulda nuqta koordinatalari (x; y) va tenglamaning bitta a – koeffisiyentini fiksirlab: (a; x; y _R) ,
b=y²-x³-ax (6)
formula orqali b–koeffisiyent hisoblab topiladi va uning asosida tenglama quriladi. Elliptik egri chiziq koeffisiyentlarini olingan rasional koordinatali nuqta orqali aniqlashning bunday usuli samarali hisoblanadi.
Elliptik egri chiziqlarning rasional nuqtalarini qo‘shish
Ushbu
E : y ²  x³  ax² bx  c,
elliptik egri chiziqda P(x₁, y₁ ), Q(x₂ , y₂ ) 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 B(x₃ , y₃ ) nuqtani Ox- o‘qiga simmetrik ko‘chiriladi va hosil bo‘lgan:
B^`(x₃, y₃)  P(x₁, y₁) Q(x₂ , y₂ )
nuqta P(x₁, y₁) va Q(x₂, y₂) nuqtalarning elliptik egri chiziq ustida yig‘indisi deb elon qilinadi:

Bu grafik x³ _ ax² _bx _ c_ 0 tenglama bitta yechimga ega bo‘lgan hol uchun keltirildi.
Yuqorida elliptik egri chiziqda koordinatalari har xil bo‘lgan, ya’ni
P(x₁, y₁ )  Q(x₂ , y₂ )  0 bo‘lgan nuqtalar yig‘indisini P(x₁, y₁ )  Q(x₂ , y₂ ) topish ko‘rib chiqildi. Endi P_ P _ ? qanday amalga oshirilishi haqida to‘xtab o‘tiladi. Buning uchun elliptik egri chiziqdagi P -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 Ox-o‘qiga nisbatan simmetrik ko‘chiriladi va bu nuqta [2]P deb elon 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 P(x₁, y₁) va Q(x₂, y₂) nuqtalar orqali o‘tuvchi to‘g‘ri chiziq elliptik egri chiziqni uchinchi nuqtada kesib o‘tavermaydi. Masalan, P(x₁, y₁) va Q(x₁, y₁) nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox-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, P(x₁, y₁ ) va Q(x₁, y₁ ) nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox-o‘qiga perpendikulyar bo‘lib, u elliptik egri chiziqni uchinchi nuqtada kesib o‘tmay, cheksizlikdagi 0_E nuqtaga yo‘naladi. Cheksizlikdagi 0_E nuqta bilan P(x₁, y₁ )-nuqtani qo‘shishni 0_E +P(x₁, y₁ ) shaklida ko‘rib chiqadigan bo‘lsak, bu nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox-o‘qiga perpendikulyar bo‘lib, elliptik egri chiziqni Q(x₁,_ y₁)- nuqtada kesib o‘tadi, so‘ngra 0_E +P(x₁, y₁) -yig‘indini ifodalovchi nuqtani topish uchun bu Q(x₁, y₁)- nuqta Ox- o‘qiga simmetrik akslantirilsa, P(x₁, y₁)- nuqta bilan ustma-ust tushadi, ya’ni kiritilgan qo‘shish amali qoidasiga ko‘ra 0_E +P(x₁, y₁ )=P(x₁, y₁ ) tenglik o‘rinli bo‘ladi. Bu 0_E nuqtaOx- o‘qiga nisbatan akslantirilsa, yana qarama-qarshi tomon cheksizligidagi (-0_E) - nuqtaga yo‘naladi. Ammo, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilganda (-0_E)+P(x₁, y₁ )=P(x₁, y₁ ) 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, yani elliptik egri chiziqqa tegishli bo‘lgan a,b, c - nuqtalar uchun:

1. 
   kommutativlik ab ba ;
   
2. 
   assosiativlik (a  b)  c  (b  c)  a ;
   
3. 
   nol elementining mavjudligi a+ 0_E = a;
   
4. 
   teskari (qarama-qarshi ishorali) elementning mavjudligi a+(-a)= 0_E kabi Abel gruppasining aksiomalari o‘rinlidir.