Мавзу: Сонларни тубликка текшириш алгоритмлари. Ферма ва Рабин Миллер тести. Режа

Мавзу: Сонларни тубликка текшириш алгоритмлари. Ферма ва Рабин Миллер тести.


Режа

1. Бўлиш назарияси алгоритми

2. AKS алгоритми
3. Ферма тести
4. Миллера-Рабина тести

Сонларни тубликка текшириш
Агар биз Мерсел ва Ферма формулалари каби алгоритмлардан туб сон ҳосил қилсак, олинган сон туб сон эканлигига кафолат бера олмаймиз. Хўш биз қагдай қилиб криптографияда катта туб сонларни ҳосил қилишимиз мумкин? Биз фақат ихтиёрий катта сонни оламиз ва уни туб эканлиги аниқловчи синов ўтказамиз.
Жуда катта туб сонларни тўғри ва эффектив ҳосил қилувчи, уни туб ёки мураккаб сон эканлигини аниқловчи ишончли алгоритмни ҳосил қилиш доимо сонлар назариясида ва криптографияда муаммо бўлган. Бироқ, яқинда ўтказилган тадқиқотлар (биз ушбу бўлимда муҳокама қиладиган) жуда истиқболли кўринади.
Ушбу муаммони ҳал қиладиган алгоритмларни иккита кенг тоифага бўлиш мумкин - детерминистик алгоритмлар ва эҳтимолий алгоритмлар. Қуйида иккала тоифанинг баъзи вакиллари.
А детерминистик алгоритм ҳар доим тўғри жавобни беради.
Эҳтимоллар алгоритми кўп ҳолларда тўғри жавобни беради, аммо ҳамма ҳолатларда ҳам эмас.


Детерминиcимк алгоритмлар
Тубликка текширувчи детерминиcимк алгоритмлар,бутун сонни қабул қилади ва чиқишда туб сон ёки туб сон ёки мураккаб сон деган характеристикани беради. Бир қанча вақтгача барча детерминистик алгоритмлар катта туб сонларни топиш учун самарасиз бўлган Қисқача янги кўринишни намойиш қилар эканмиз, ушбу алгоритмлар уларни янада истиқболли қилади.

Бўлиш назарияси алгоритми
Энг элементар детерминистик туб сонларни текшириш бу бўлиш билан текшириш. Биз барча бўлувчи сонлар сифатида дан кичиларидан фойдаланамиз. Агар бу сонлардан исталгани 𝑛 га бўлинса, ҳолбуки 𝑛 мураккаб.



Алгоритм 12.1да бўлиш бўйича тубликка синаш жуда самарали ва примитив формада акс эттирган

Алгоритм фақатгина тоқ сонларни текширса янада самарали ишлаши мумкин. У яна 2 ва сонлар оралиғидаги туб сонлар жадвалидан фойдаланилса янада самарали бўлиши мумкин. 12.1 алгоритмдаги арифметик амаллар сони — га тенг. Агар биз ҳар бир арифметик амал фақат бир битдаги амаллардан фойдаланилишини қабул қилсак, у ҳолда 12.1 алгоритм разрядли амали мураккаблиги га тенг, бу ерда n_b – битлар сони 𝑛 даги. Катта тизимларда, 𝑂 мураккаблик кўрсаткичи,муракаблик экспоненсиал O(2ⁿ) даражада баҳоланиши мумкин. Бошқа сўз билан айтганда бўлиш синови агар nb катта сон бўлса самарасиз ҳисобланади.
Фараз қиламиз, 𝑛 200 битга тенг. Қандай сондаги разряд амалини бўлиш алгоритмида амалга ошириш керак?

Бу алгоритм битли амалининг мураккаблиги— . Бу шуни англатадики, алгоритм бир қанча 2¹⁰⁰бит амалларни ўтказади. Агар алгоритм секундига 2³⁰та амални бажариш тезлигига эга бўлса, у ҳолда синовни ўтказиш учун 2⁷⁰ сония керак бўлади