Mirzo ulug’bek nomidagi

Kvadratik ayirmalar. Agar p - tub son va 0<a< p bo‘lib, ushbu x mod p = a munosabatni qanoatlantiruvchi x - noma’lumning qiymatlari mavjud bo‘lsa, u holda a soni modul p bo‘yicha kvadratik ayirma deyiladi.
Agarda a soni modul p bo‘yicha kvadratik ayirma 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 ayirma bo‘ladi va u bosh kvadratik ildiz deyiladi.
Yasovchi (Tuzuvchi). Berilgan r -tub son va g<p uchun, g -yasovchi (tuzuvchi) yoki modul p bo‘yicha primitiv ildiz deyiladi, agarda 1 <b < p -1 shartni qanoatlantiruvchi har bir b soni uchun, ushbu g^a modp = b tenglikni qanoatlantiruvchi a soni mavjud bo‘lsa.
Tub ko’paytuvchilarga ajratish. Berilgan sonni ko‘paytuvchilarga ajratish deganda, uning tub ko‘paytuvchilarini topish tushuniladi. Berilgan sonni ko‘paytuvchilarga ajratish sonlar nazariyasining eng dastlabki masalalaridan biri hisoblanadi. Berilgan sonni (yoki to‘plamni) biror amal yoki xususiyatga ko‘ra uning tashkil etuvchilari orqali ifodalanishi, shu sonni (yoki to‘plamni) faktorlash

(ajratish) deyiladi. Sonni ko‘paytuvchilarga ajratish qiyin jarayon emas, ammo ko‘paytuvchilarga ajratilishi kerak bo‘lgan sonning qiymati kattalashib borishi bilan, uni ko‘paytuvchilarga ajratish jaryoniga sarflanadigan vaqt ham ko‘payib boradi. Shunday bo‘lsada, ko‘paytuvchilarga ajratish jarayonini tezlashtiruvchi quyidagi algoritmlar mavjud:

1. 
   sonli maydon umumiy G’alviri usuli - o‘nlik sanoq tizimida 110 ta va undan ko‘p razryadli (raqamli) sonlarni ko‘paytuvchilarga ajratishning ma’lum bo‘lgan eng samarali (tez, kam vaqt sarflanadigan) algoritmi;
   
2. 
   kvadratik G’alvir usuli - o‘nlik sanoq tizimida 110 tadan kam bo‘lmagan razryadli (raqamli) sonlarni ko‘paytuvchilarga ajratishning ma’lum bo‘lgan eng samarali (tez, kam vaqt sariflanadigan) algoritmi;
   
3. 
   elliptik egri chiziq usuli - o‘nlik sanoq tizimida tub ko‘paytuvchilarining razryadi (raqamlari soni) 43 tadan ko‘p bo‘lmagan sonlarni ko‘paytuvchilarga ajratishda foydalanilgan;
   
4. 
   Pollardning Monte-Karlo usuli - amalda kam ishlatiladi;
   
5. 
   uzuliksiz kasrlar usuli - qo‘llashga ko‘p vaqt sarflanadi;
   
6. 
   tanlab bO’lish usuli - eng dastlabki usullardan bo‘lib, ko‘paytuvchilarga ajratilishi kerak bo‘lgan (berilgan) sonning kvadrat ildiziga teng va undan kichik bo‘lgan har bir tub sonni berilgan sonni qoldiqsiz bo‘lishi yoki bo‘lmasligi tekshirib chiqilishi natijasida, berilgan sonni tub ko‘paytuvchilari aniqlanadi.
   

Tub sonlar generatsiyasi (ishlab chiqarish). Ochiq kalitli kriptoalgoritmlar asoslari yaratilishida tub sonlarning xossalaridan foydalaniladi. Biror berilgan sonni tub ko‘paytuvchilarga ajratish, uni tub yoki tub emasligini aniqlashga nisbatan murakkab bo‘lgan masala. Yetarli katta razryaddagi toq sonni tasodifiy tanlab olib, uni ko‘paytuvchilarga ajratish bilan tub yoki tub emasligini aniqlashdan ko‘ra, uning tubligini biror mavjud usul bilan tekshirish osonroq. Buning uchun turli ehtimollik testlari mavjud bo‘lib, sonning tubligini berilgan darajadagi ishonch bilan aniqlab beradi. Kriptobardoshliligi yetarli darajada katta razryadli sonni tub ko‘paytuvchilarga ajratish masalasining murakkabligiga

asoslangan ochiq kalitli kriptoalgoritmlar mavjud.
Chekli maydonlarda diskret logarifmlash. Kriptografiyada birtomonli (teskarisi yo‘q) funksiya sifatida biror modul n bo‘yicha darajaga ko‘tarish amalini bajarishni hisoblashdan foydlalaniladi: