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


Download 174.02 Kb.
bet8/8
Sana12.03.2023
Hajmi174.02 Kb.
#1262631
1   2   3   4   5   6   7   8
Bog'liq
Эҳтимоллик тестлари

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

Айтайлик, 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 –сонини иккита (туб) кўпайтувчига ажратган бўламиз ва алгоритм ўз ишини тугатади.
Download 174.02 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling