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

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

Айтайлик , , n – тоқ ва . Берилган натурал соннинг туб эканлигини аниқлаш эҳтимоллик тести бўйича қуйидаги тартибда олиб борилади. Тасодифий , танланади ва унинг учун маълум бир шартларнинг бажаришлиги текширилади. Агар кўрсатилган шартлардан бирортаси бажарилмаса, у ҳолда n – мураккаб сон деб эълон қилинади.

Агарда барча келтирилган шартлар бажарилса, у ҳолда бу ерда n –сони туб экан деган хулоса келиб чиқмайди. Бироқ “n –сони, маълум бир эҳтимоллик билан туб сон”- деб юритилади. Ана шундай тестлардан бири бўлган ва бугунги кунда амалда кенг фойдаланиб келинаётган Соловей – Штрассен тести ҳакида тўхталиб ўтамиз. Унинг учун эса қуйидаги тасдиқлар ўринли:
Теорема 1. n – тоқ мураккаб сон. У ҳолда шартни :
1) ЭКУБ (a, n)=1;
2)
қаноатлантирувчи бутун a – лар сони n/2 – дан ошмайди.
Бу ерда - Якоби символи.
Натижа 1. Агар n – туб бўлса, у ҳолда 1), 2) шартлар барча , -лар учун бажарилади.
Агарда n – мураккаб бўлса, у ҳолда тасодифан олинган , - учун 1), 2) шартларнинг бажарилиш эҳтимоллиги ½ - дан ошмайди.
Шунинг учун ҳам, k – та тасодифий , учун Теорема 1 – нинг 1), 2) шартларини бажарилишини текширамиз, агар барчасида ўринли бўлса, яъни n – мураккаб эмаслиги аниқланса, у ҳолда берилган n – сони - эҳтимоллик билан туб сон экан деб эьлон қилинади.
Мисол 1. n=7 , туб ёки туб эмаслиги юқоридаги тест орқ али текширилсин
Ечиш. ,
1) ЭКУБ(2,7)=1; 2) ;
демак, .
энди ҳоли учун:
ЭКУБ(3, 7)=1;
,
яъни бажарди.
Энди учун: ЭКУБ(4,7)=1


яъни 2) шарт ҳам ўринли демоқчимиз. Энди учун: ЭКУБ(5,7)=1


.
.
яъни 2) шарт ҳам ўринли экан.
Энди учун:
ЭКУБ(6,7)=1.
,
яъни 2) шарт ҳам ўринли демоқчимиз.
У ҳолда
n=7 , k=6, - эҳтимоллик билан ёки яна ҳам аниқроқ қилиб айтсак, n=7 – сони туб деган хулосага келамиз.