Шерман – Леман усули
Айтайлик, n-жуфт бўлмаган ва n > 8 бутун сон. Алгоритм қуйидаги қадамлардан иборат.
1-Қадам. Барча а = 2,3,4………,[(n)1/3 ] сонлар учун n : а бажарилиши текшириб кўрилади.
Агар қайсидир бир а – учун n : а бажарилса, у ҳолда факторизация масаласи ҳал бўлиб, алгоритм қадами шу ерда тўхтатилади. Акс ҳолда эса кейинги қадамга ўтилади.
2-Қадам. Барча к = 1,2,3….[(n)1/3 ] ва d = 0,1,2,..... , [(n)1/6 / (4* )] +1 учун қуйидаги сон:
( [ ] +d )2 – 4*k*n
бирор соннинг (натурал) квадрати бўладими, шуни текшириш лозим. Агар шундай бўлса, у ҳолда
А= [ ] +d ; В= ;
учун А2 В2 (mod n)
таққослама ўринли ҳамда қуйидаги шарт бажарилиши
1< ЭКУБ (А В; n) < n;
текшириш керак.
Агар бу шарт ўринли бўлса, у ҳолда берилган n –сонини иккита (туб) кўпайтувчига ажратган бўламиз ва алгоритм ўз ишини тугатади.
Do'stlaringiz bilan baham: |