1-Мавзу: Туб сонлар ва уларни генерациялаш усуллари Криптология кафедраси


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


Download 0.8 Mb.
bet5/6
Sana27.01.2023
Hajmi0.8 Mb.
#1131330
1   2   3   4   5   6
Bog'liq
1 мавзу Туб сонлар ва уларни генерациялаш усуллари

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

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

  •  

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

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

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

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

  •  

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

Таъриф (Лежандр символи). Фараз қилайлик абутун сон ва р≠ 2 туб сон. У ҳолда Лежандр символи қуйидагича аниқланади:

    • агар а р га бўлинса ;
    • агар а р модул бўйича квадратик чегирма, яъни а р га бўлинмайди ва шундай бутун х сон мавжудки, бўлса, ;
    • агар а р га бўлинмаса ва а р модул бўйича квадратик чегирма бўлмаса, .
  •  

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

  • p=19 ни Соловэй-Штрассен алгоритми билан тубликка синаймиз:
  • k=1,
  • оралиқдан тасодифий a=11 танлаймиз.
  • ЭКУБ(а,р)= ЭКУБ(11,19)=1
  • Демак, шартни бажарилишини текширамиз.
  • Таққосласак, демак, , .
  •  

Download 0.8 Mb.

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




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