2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

Misol-1. n =728 soni tub ko‘paytuvchilari topilsin.
Yechish. Tasodifiy x₀ ZnZ –son sifatida
x₀ = 2 , f(x)=x² +1
deb olinsa, u holda
x_i f(x_i-1) (mod n); i=0,1,2.......
yani x₀ = 2, x₁=5, x₂ =26, x₃ = 677, ………
EKUB (x₁ - x₀ ; n) = EKUB (3; 728)=1
Bu esa 3) shart intervaliga tegishli emas. Shuning uchun boshqa i – qiymatlar uchun hisoblashlarni davom qildiramiz.
EKUB (x₂- x₁; n) = EKUB ( 21; 728) =7;
Yani 3) shart intervaliga tushdi. Demak, 729:7=104. U holda bitta tub ko‘paytuvchisi 7 ekan. Keyingi hisoblashlarni n = 104 uchun bajarish yetarli.
EKUB (x₁ - x₀ ; n) = EKUB (3; 104)=1 , bu hol bajarilmaydi;
EKUB (x₂- x₁ ; n) = EKUB ( 21; 104) =1; bu hol ham bajarmadi;
EKUB (x₃- x₂ ; n) = EKUB ( 651; 104) =1; bu ham bajarmadi;
EKUB (x₄- x₃ ; n) = EKUB ( 457653; 104) =1; bu ham bajarmadi;
Demak, boshqa j, k –nomerlar uchun tekshiramiz:
j = 2, k = 0 ;
U holda
EKUB (x₂ - x₀; n) = EKUB ( 24; 104) = 8
va 1< 8 < 104 shart bajarildi.
Natijada 104: 8 = 13 bo‘lib, bevosita tekshirish mumkinki 13 soni tub son, javob esa 728 = 7*8*13= 7*2³ *13.
Sherman – Leman usuli

Aytaylik, n-juft bo‘lmagan va n > 8 butun son. Algoritm quyidagi qadamlardan iborat.

1-Qadam. Barcha a = 2,3,4………,[(n)^1/3 ] sonlar uchun n : a bajarilishi tekshirib ko‘riladi.
Agar qaysidir bir a – uchun n : a bajarilsa, u holda faktorizatsiya masalasi hal bo‘lib, algoritm qadami shu yerda to‘xtatiladi. Aks holda esa keyingi qadamga o‘tiladi.
2-Qadam. Barcha k = 1,2,3….[(n)^1/3 ] va d = 0,1,2,..... , [(n)^1/6 / (4* )] +1 uchun quyidagi son:
( [ ] +d )² – 4*k*n
biror sonning (natural) kvadrati bo‘ladimi, shuni tekshirish lozim. Agar shunday bo‘lsa, u holda
A= [ ] +d ; V= ;
uchun A² V² (mod n)
taqqoslama o‘rinli hamda quyidagi shart bajarilishi
1< EKUB (A V; n) < n;
tekshirish kerak.
Agar bu shart o‘rinli bo‘lsa, u holda berilgan n –sonini ikkita (tub) ko‘paytuvchiga ajratgan bo‘lamiz va algoritm o‘z ishini tugatadi.