Мавзу: Сонларни тубликка текшириш алгоритмлари. Ферма ва Рабин Миллер тести. Режа

Эҳтимолий алгоритмлар
AKS алгоритмигача барча тубликка текширувчи самарали алгоритмлар эҳтимолий
бўлган. Бу усуллар AKS формал стандарт сифатида фойдаланилиши мумкин эди.
Эҳтимолий алгоритмлар натижа тўғрилигига кафолат бермайди. Фақат биз бир қанча кичик эҳтимолликдаги хатоликни олсак, алгоритм тўғри натижа ишлаб чиқишига кафолат беради.
Алгоритмнинг разрядли амаллари мураккаблиги полиномиал қўйилиши мумкин, биз унчалик катта бўлмаган хато қилиш итиёзига эга бўлишимиз мумкин. Бу туркумдаги эҳтимолий алгоритмлар қуйидаги қоидаларга асосланиб туб ёки мураккаб деган натижани
беради:
а. Агар текширилаётган бутун сон ҳақиқатдан туб бўлса, алгоритм аниқ туб сонни қайтаради.
б. Агар текширилаётган бутун сон ҳақиқақтдан мураккаб объект бўлса, алгоритм 1-е эҳтимоллик билан мураккаб объектни қайтаради, аммо э билан туб сонни сонни қайтариши ҳам мумкин. Агар алгоритмни бир неча бор турли параметрлар билан ишласак ёки ҳар хил усуллардан фойдалансак хато эҳтимоллиги яхшиланиши мумкин. Агар алгоритмни 𝑚 марта бажарсак, хато эҳтимоли 𝑚 га камайиши мумкин.

Ферма тести
Биз муҳокама қилаётган биринчи эҳтимоллик усули бу Ферматнинг туб сонларни синаб кўришидир.


Агар 𝒏 туб сон бўлса, у ҳолда тенглик ўринли.
Эътибор беринг, агар н туб бўлса, таққослаш тўғри бўлади. Лекин бу, таққослаш тўғри бўлса, н бу туб сон бўлади дегани эмас. Бутун сон туб ёки мураккаб бўлиши мумкин.
Фермат тести сифатида биз қуйидагиларни аниқлашимиз мумкин:

Туб сонлар Ферса тестини қаноатлантиради. Мураккаб сонлар эҳтимоллик билан ферма тестидан ўтиши мумкин. Експопенсиални ҳисоблаў каби, Ферма тестининг разрядли амаллари мураккаблиги алгоритм мураккаблигига тенг. Агар назорат бир нечта сонларга бўлиб юборилса, эҳтимоллик янада яхши бўлиши мумкин.

Мисол.
561 сони учун Ферма синовини ўтказинг.
Ечим
Асос сифатида 2 сонидаг фойдаланамиз.
2^561-1 = 1 mod 561
Сон Ферма тестидан ўтди, лекин бу туб сон эмас, нимагаки
561 = 33 x 17