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



Download 1,76 Mb.
bet2/4
Sana21.02.2022
Hajmi1,76 Mb.
#60803
1   2   3   4
Bog'liq
Mustaqil ish (Sonni tublikka tekshirish)

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

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


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

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



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


Download 1,76 Mb.

Do'stlaringiz bilan baham:
1   2   3   4




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

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish