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

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

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

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

•  

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

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

•  

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

• k=2,
• оралиқдан тасодифий a=5 танлаймиз.
• ЭКУБ(а,р)= ЭКУБ(5,19)=1
• Демак, шартни бажарилишини текширамиз.
• Таққосласак, демак, , .
• Бундан қуйидагича хулосага келиш мумкин: 19 сон 1-2-2 эҳтимоллик билан туб сон бўлади.

•  

Рабин-Миллернинг катта сонларни тубликка синаш алгоритми

Рабин – Миллернинг катта сонларни тубликка синаш тести ҳозирги кунда носимметрик криптотизимларда модул ҳосил қилишда кенг қўлланилади. Бу алгоритм кучли псевдотуб сонларни синаш алгоритми сифатида тан олинган. У n -1 ни, яъни модулни битта камайтирилган қийматини 2s*r кўринишда ифодалашга асосланган. Бунда s ─ n -1 ни иккига бўлинишлар сони, r – тоқ сон.

“n - сони тубми?” деган саволга, “туб” ёки “мураккаб” деган жавоб олишга қаратилган бўлади.

• n -1 = 2s*r кўринишда ёзиб олинади, бунда r - тоқ сон;
• шартни қаноатлантирувчи а сон тасодифий танланади;
• ни ҳисобланади;
• Агар (у=1 ёки у=n -1) бўлса, у ҳолда кейинги итерацияга ўтиш.
• ҳисобланади;
• ;
• Агар (у=1) бўлса, у ҳолда “мураккаб сон” қайтарилади;
• Агар бўлса, у ҳолда “мураккаб сон” қайтарилади;
• Акс ҳолда “Туб сон” қайтарилади.

•