Misol-1. n =728 soni tub ko‘paytuvchilari topilsin.
Yechish. Tasodifiy x0 ZnZ –son sifatida
x0 = 2 , f(x)=x2 +1
deb olinsa, u holda
xi f(xi-1) (mod n); i=0,1,2.......
yani x0 = 2, x1=5, x2 =26, x3 = 677, ………
EKUB (x1 - x0 ; n) = EKUB (3; 728)=1
Bu esa 3) shart intervaliga tegishli emas. Shuning uchun boshqa i – qiymatlar uchun hisoblashlarni davom qildiramiz.
EKUB (x2- x1; 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 (x1 - x0 ; n) = EKUB (3; 104)=1 , bu hol bajarilmaydi;
EKUB (x2- x1 ; n) = EKUB ( 21; 104) =1; bu hol ham bajarmadi;
EKUB (x3- x2 ; n) = EKUB ( 651; 104) =1; bu ham bajarmadi;
EKUB (x4- x3 ; n) = EKUB ( 457653; 104) =1; bu ham bajarmadi;
Demak, boshqa j, k –nomerlar uchun tekshiramiz:
j = 2, k = 0 ;
U holda
EKUB (x2 - x0; 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*23 *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 )2 – 4*k*n
biror sonning (natural) kvadrati bo‘ladimi, shuni tekshirish lozim. Agar shunday bo‘lsa, u holda
A= [ ] +d ; V= ;
uchun A2 V2 (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.
Do'stlaringiz bilan baham: |
