Алгоритм бажарилиш кетма-кетлиги қуйидагидан иборат

Поллард усули

Айтайлик , n - жуфт бўлмаган мураккаб сон, бўлувчиси катта бўлмаган. Р – орқали n –соннинг энг кичик туб бўлувчисини белгиласак. Поллард усулининг моҳияти шу бўлувчини топишдан иборат.

Алгоритм бажарилиш кетма-кетлиги қуйидагидан иборат :

1. 
   Айтайлик,
   

z = [ n^{1 / 4}] +1 , y = z² > n^1/2.
2. n ва у! сонларининг энг кичик умумий карралисини топамиз:
ЭКУК( n , у! ) = n* у! / ЭКУБ ( n , у! ) .
3. Маьлумки у! сони берилган n сонининг энг кичик туб бўлувчиси Р –га бўлинади,
чунки Р n^1/2 < y .
4. У ҳолда берилган соннинг энг кичик туб бўлувчиси P -эканлиги жавоб қилиб берилади.

Полларднинг усули 1975 йилда Дж. Поллард томонидан топилган бўлиб,

F₈ = 2²⁵⁶ +1 Ферма сонининг туб кўпайтувчилари аниқланилган.
Айтайлик, n N биздан шу сонни туб кўпайтувчиларга ажратиш масаласи сўралаётган бўлсин. Бу усулнинг моҳияти қуйидагидан иборат:
1)f(x) – кўпхад даражаси икки ёки ундан катта бўлган, масалан f(x)=x² +1 деб олинади.
2) Тасодифий х₀ Zn танланади.
3) Қандайдир фиксирланган (маьлум бўлган) j, k –номерлар учун қуйидаги шартларнинг бажаришлиги текширилади:
1 < ЭКУБ(х_j –x_k ; n) < n
токи, n –сонининг туб кўпайтувчилари топилмагунча.
Бу ерда, агар j –сони
2^h j < 2^h+1, h N
бўлса, у ҳолда к = 2^h -1 кўринишда олиш мақсадга мувофиқ..


Мисол

Ечиш. Тасодифий х₀ Zn –сон сифатида

х₀ = 2 , f(x)=x² +1
деб олинса, у ҳолда
x_i f(x_i-1) (mod n); i=0,1,2.......
яьни х₀ = 3, х₁=5, х₂ =27, х₃ = 671, ………
ЭКУБ (х₁ - х₀ ; n) = ЭКУБ (3; 8051)=1
Бу эса 3) шарт интервалига тегишли эмас. Шунинг учун бошқа i – қийматлар учун ҳисоблашларни давом қилдирамиз.
ЭКУБ (х₂- х₁; n) = ЭКУБ ( 87; 8051) =97;
Демак, бошқа j, k –номерлар учун текширамиз:
j = 2, k = 0 ;
У ҳолда
ЭКУБ (х₂ - х₀; n) = ЭКУБ ( 97; 8051) = 87
ва 1< 87 < 97 шарт бажарилди.
8051=87*97