Assimmetrik shifrlash algoritmlarining matematik asosi

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 jarayoniga sarflanadigan vaqt ham ortib boradi. Shunday bo‘lsada, ko‘paytuvchilarga ajratish jarayonini tezlashtiruvchi quyidagi algoritmlar mavjud:

1. 
   Sonli maydon umumiy G‘alvir usuli - o‘nli 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‘nli sanoq tizimida 110 tadan kam bo‘lmagan razryadli (raqamli) sonlarni ko‘paytuvchilarga ajratishning ma’lum bo‘lgan eng samarali (tez, kam vaqt sarflanadigan) algoritmi;
   
3. 
   Elliptik egri chiziq usuli - o‘nli sanoq tizimida tub ko‘paytuvchilarining razryadi (raqamlari soni) 43 tadan ko‘p bo‘lmagan sonlarni ko‘paytuvchilarga ajratishda foydalaniladi;
   
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 songa berilgan sonni qoldiqsiz bo‘linishi yoki bo‘linmasligi 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 yuqori darajada aniqlik bilan aniqlab beradi. Kriptobardoshliligi yetarli darajada katta razryadli sonni tub ko‘paytuvchilarga ajratish masalasining murakkabligiga asoslangan ochiq kalitli kriptoalgoritmlar mavjud.