1-Мавзу: Очиқ калитли шифрлаш алгоритмлари Криптология кафедраси

Аммо п сон мураккаб бўлганда, шундай а топиладики, таққослама бажарилмайди, бундай а сон п соннинг мураккаблигига гувоҳ дейилади, бунда таққослама бажарилган аввалги а сон эса, п соннинг тублигига “сохта гувоҳ” дейилади.

•  

Ферманинг катта сонларни тубликка синаш алгоритми

Мураккаб бутун сон п=341(=11∙31) сон 2 асос бўйича псевдотуб дейилади, чунки таққослама бажарилади.

Аммо 3 асос бўйича ҳисобланса .

Демак, а=2 тубликка “сохта тублик гувоҳи” ва а=3 эса мураккаблик гувоҳи бўлади.

Шунинг учун, сонни Ферма теоремаси бўйича тубликка синаганда бир қанча а сони танланади. шартни қаноатлантирувчи а сони қанча кўп бўлса, п сонни туб бўлиш эҳтимоли шунча катта бўлади.

Лекин шундай мураккаб п сонлар борки, улар учун таққослама п билан туб бўлган ихтиёрий а сонда бажарилади. Бундай сонлар Кармайкл сонлари дейилади. Кармайкл сонлари тўплами чексиз тўплам бўлиб, уларнинг энг кичиги – п=561=3∙11∙17. Шунга қарамай Ферма тести мураккаб сонларни аниқлашда самарали ҳисобланади.

•  

Соловэй-Штрассеннинг катта сонларни тубликка синаш алгоритми

Тест ҳар доим туб сонининг тублигини тўғри аниқлайди, аммо мураккаб сонлар учун маълум эҳтимоллик билан нотўғри жавоб териши мумкин. Тестнинг асосий афзаллиги шундаки, у Ферма тестидан фарқли ҳолда Кармайкл сонларини мураккаб сон сифатида аниқлайди.

Ушбу тестда Эйлер критерийсидан фойдаланилади. Маълумки, Эйлер критерийсига кўра, агар р билан энг катта умумий бўлувчига эга бўлмаган барча туб соннинг гувоҳлари а учун шарт қаноатлантирилса, р тоқ сони туб сон бўлади.

Яъни, мазкур алгоритмда туб сонлар даражалари жадвалининг (р-1)/2 қаторида р билан ўзаро туб бўлган “тублик гувоҳлари” а га тегишли устунда ҳосил бўладиган 1 ва -1 элементларига эътибор қаратилади.

•