Of cryptography

276 CHAPTER 9 MATHEMATICS OF CRYPTOGRAPHY
Now three equations can be solved using the Chinese remainder theorem to find z. One of the acceptable answers is z = 457.

5. KVADRATIK KONGRUENSIYA

Chiziqli moslik 2-bobda va Xitoy qoldiqlari teoremasi oldingi bobda muhokama qilingan. Kriptografiyada kvadratik moslik⎯ya'ni a2x2 + a1x + a0 ≡ 0 (mod n) ko'rinishdagi tenglamalarni ham muhokama qilishimiz kerak. Biz o'zimizni cheklaymiz a2 = 1 va a1 = 0 bo'lgan kvadrat tenglamalarga o'tish, ya'ni ko'rinishdagi tenglamalar
x2 ≡ a (mod n).

Kvadrat moslik moduli va Primer

Biz birinchi navbatda modul tub bo'lgan holatni ko'rib chiqamiz. Boshqacha qilib aytganda, biz x2 ≡ a (mod p) ko'rinishdagi tenglamaning yechimlarini topmoqchimiz, bunda p tub son, a butun son bo'lib, p a bo'ladi. Ushbu turdagi tenglamaning yechimi yo'q yoki aniq ikkita mos kelmaydigan yechimga ega ekanligini isbotlash mumkin.


Misol 9.39
x2 ≡ 3 (mod 11) tenglamaning ikkita yechimi bor, x ≡ 5 (mod 11) va x ≡ −5 (mod 11). Lekin e'tibor bering -5 ≡ 6 (mod 11), shuning uchun echimlar aslida 5 va 6. Bu ikki yechim mos kelmasligini ham unutmang.


Misol 9.40
x2 ≡ 2 (mod 11) tenglama yechimga ega emas. Uning kvadrati 2 mod 11 bo'lishi uchun x butun sonini topib bo'lmaydi.


Kvadrat qoldiqlar va qoldiq bo'lmaganlar
x2 ≡ a (mod p) tenglamada, agar tenglama ikkita yechimga ega bo'lsa, a kvadrat qoldiq (QR) deyiladi; a tenglamaning yechimlari bo'lmasa, kvadratik qoldiq (QNR) deyiladi. Zp* da p - 1 elementlar bilan aynan (p - 1)/2 elementlar kvadratik qoldiqlar va (p - 1)/2 kvadratik bo'lmagan qoldiqlar ekanligini isbotlash mumkin.


Misol 9.41
Z11* da 10 ta element mavjud. Ularning aniq beshtasi kvadratik qoldiqlar, beshtasi esa qoldiqsiz. Boshqacha qilib aytganda, Z11* 9.4-rasmda ko'rsatilganidek, QR va QNR ikkita alohida to'plamga bo'linadi.


Eyler mezoni
Butun son QR moduli p ekanligini qanday tekshirishimiz mumkin? Eyler mezoni juda aniq shartni beradi:

1. 
   Agar a(p−1)/2 ≡ 1 (mod p), a kvadratik qoldiq moduli p.
   
2. 
   Agar a(p−1)/2 ≡ −1 (mod p) bo‘lsa, a kvadratik qoldiq bo‘lmagan modul p.
   

9.5-Bo’lim KVADRATIK KONGRUENSIYA 277
9.4-rasm. Z11* elementlarning QR va QNR larga bo'linishi

Har bir element kvadrat ildizga ega Hech bir element kvadrat ildizga ega emas

Misol 9.42
Z23* da 14 yoki 16 QR ekanligini aniqlash uchun biz hisoblaymiz:



Kvadrat tenglamani yechish moduli
Eyler mezoni a butun soni Zp* da QR yoki QNR baholash bildirsa-da, u x2 ≡ a (mod p) yechimini topa olmaydi. Bu kvadrat tenglamaning yechimini topish uchun biz tubning p = 4k + 1 yoki p = 4k + 3 bo'lishi mumkin ko'ramiz, bunda k musbat butun sondir. Kvadrat tenglamaning yechimi birinchi navbatda juda muhim; vaqtida. Biz faqat vaziyatni muhokama qilamiz, biz10-bobda Rabin kriptotizimini muhokama qilamiz.
Maxsus holat: p = 4k + 3 Agar p 4k + 3 ko'rinishida bo'lsa (ya'ni p ≡ 3 mod 4) va a Zp* da QR bo'lsa, u holda


x ≡ a^(p+1)/4 (mod p) and x ≡ − a^{(p + 1)/4} (mod p)


Misol 9.43
Quyidagi kvadrat tenglamalarni yeching:
a. x² ≡ 3 (mod 23)
b. x² ≡ 2 (mod 11)
c. x² ≡ 7 (mod 19)
Yechimlar

1. 
   Birinchi tenglamada 3 Z23 da QR hisoblanadi. Yechim x ≡ ± 16 (mod 23). Boshqa so'zlar bilan aytganda,
   
2. 
   √3 ≡ ± 16 (mod 23).
   
3. 
   Ikkinchi tenglamada 2 Z11 da QNR hisoblanadi. Z11 da √2 uchun yechim yo'q.
   
4. 
   Uchinchi tenglamada 7 Z19 da QR hisoblanadi. Yechim x ≡ ± 11 (mod 19). Boshqacha qilib aytganda, √7 ≡ ± 11 (mod 19).