Шунинг учун, сонни Ферма теоремаси бўйича тубликка синаганда бир қанча а сони танланади. шартни қаноатлантирувчи а сони қанча кўп бўлса, п сонни туб бўлиш эҳтимоли шунча катта бўлади. Лекин шундай мураккаб п сонлар борки, улар учун таққослама п билан туб бўлган ихтиёрий а сонда бажарилади. Бундай сонлар Кармайкл сонлари дейилади. Кармайкл сонлари тўплами чексиз тўплам бўлиб, уларнинг энг кичиги – п=561=3∙11∙17. Шунга қарамай Ферма тести мураккаб сонларни аниқлашда самарали ҳисобланади. Тест ҳар доим туб сонининг тублигини тўғри аниқлайди, аммо мураккаб сонлар учун маълум эҳтимоллик билан нотўғри жавоб териши мумкин. Тестнинг асосий афзаллиги шундаки, у Ферма тестидан фарқли ҳолда Кармайкл сонларини мураккаб сон сифатида аниқлайди. Ушбу тестда Эйлер критерийсидан фойдаланилади. Маълумки, Эйлер критерийсига кўра, агар р билан энг катта умумий бўлувчига эга бўлмаган барча туб соннинг гувоҳлари а учун шарт қаноатлантирилса, р тоқ сони туб сон бўлади. Яъни, мазкур алгоритмда туб сонлар даражалари жадвалининг (р-1)/2 қаторида р билан ўзаро туб бўлган “тублик гувоҳлари” а га тегишли устунда ҳосил бўладиган 1 ва -1 элементларига эътибор қаратилади. Соловэй-Штрассеннинг катта сонларни тубликка синаш алгоритми Таъриф (Лежандр символи). Фараз қилайлик а – бутун сон ва р≠ 2 туб сон. У ҳолда Лежандр символи қуйидагича аниқланади: - агар а р га бўлинса ;
- агар а р модул бўйича квадратик чегирма, яъни а р га бўлинмайди ва шундай бутун х сон мавжудки, бўлса, ;
- агар а р га бўлинмаса ва а р модул бўйича квадратик чегирма бўлмаса, .
Соловэй-Штрассеннинг катта сонларни тубликка синаш алгоритми - p=19 ни Соловэй-Штрассен алгоритми билан тубликка синаймиз:
- k=1,
- оралиқдан тасодифий a=11 танлаймиз.
- ЭКУБ(а,р)= ЭКУБ(11,19)=1
- Демак, шартни бажарилишини текширамиз.
- Таққосласак, демак, , .
Do'stlaringiz bilan baham: |
