Эҳтимоллик тестлари

Шерман – Леман усули

Айтайлик, 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 )² – 4*k*n
бирор соннинг (натурал) квадрати бўладими, шуни текшириш лозим. Агар шундай бўлса, у ҳолда
А= [ ] +d ; В= ;
учун А² В² (mod n)
таққослама ўринли ҳамда қуйидаги шарт бажарилиши
1< ЭКУБ (А В; n) < n;
текшириш керак.
Агар бу шарт ўринли бўлса, у ҳолда берилган n –сонини иккита (туб) кўпайтувчига ажратган бўламиз ва алгоритм ўз ишини тугатади.