Texnologiyalari universiteti kriptografiyaning matematik asoslari

3.8.3 Kvadratik chegirmalar

Agar p – tub son va 0< a< p bo‘lib, ushbu x² _a(mod r)
munosabatni qanoatlantiruvchi x – noma’lumning qiymatlari mavjud bo‘lsa, u holda a soni modul p bo‘yicha kvadratik chegirma hisoblanadi.
Misol uchun, r=7 bo‘lsa, kvadratik chegirma tashkil etuvchilar: 1, 2 va 4 sonlaridan iborat, ya’ni a =1, a =2 va a=4 qiymatlarda, ushbu taqqoslamalar
1² =1_1(mod 7); 2² =4_4(mod 7); 3² =9_2(mod 7); 4² =16_2(mod 7);
5² =25_4(mod 7); 6² =36_1(mod 7);
o‘rinli.
Noma’lum x ning quyidagi munosabatlarni:
x² _3(mod 7); x² _5(mod 7); x² _6(mod 7),
qanoatlantiruvchi qiymatlari mavjud emas, shuning uchun a =3, a =5 va a=6 sonlari modul 7 bo‘yicha kvadratik chegirma emas, ya’ni berilgan kvadratik taqqoslamalar yechimga ega emas.
Modul p juft bo‘lsa, u holda (p-1)/2 ta kvadratik chegirma mavjud va shuncha kvadratik chegirma mavjud emas, ya’ni ushbu x² _a(mod r)
munosabatni qanoatlantiruvchi x –noma’lum mavjud bo‘ladigan a parametrning mumkin bo‘lgan qiymatlari soni (p-1)/2 ta, bu munosabatni qanoatlantiruvchi x – noma’lum mavjud bo‘lmaydigan a parametrning mumkin bo‘lgan qiymatlari soni ham (p-1)/2 ta. Bundan tashqari, agarda a soni modul p bo‘yicha kvadratik chegirma bo‘lsa, u holda a uchun ikkita kvadrat ildiz mavjud bo‘lib, ulardan biri [0; (p-1)/2] oraliqda, ikkinchisi [(p-1)/2; p-1] oraliqda, shu bilan birga ulardan biri modul p bo‘yicha kvadratik chegirma bo‘ladi va u bosh kvadratik ildiz deyiladi.