Tt va kt ” fakulteti 4 – bosqich ax-11-17 guruh talabasining

Усуллар мураккаблиги

Усуллар	f(x)	log2f(x)
Танлаб бўлиш	2^x /x	x- log2 x
Квадратик ғалвир	2^c (log2x) ^½, бу ерда c=x^1/2	x^1/2(log2x) ^1/2
Сонли майдон ғалвири	21.9223d (log2x) 2/3, бу ерда d=x^1/3	1.9223 x^1/3 (log2x) ^2/3

Келтирилган жадвалдан субэкспоненциал мураккабликка эга бўлган квадратик ғалвир ва сонли майдон ғалвири усуллари асимптотик мураккаблик нуқтаи назаридан экспоненциал мураккабликка эга бўлган алгоритмлардан устунлиги билан белгиланиши, бироқ полиномиал мураккабликка эга алгоритмлар билан рақобатлаша олмаслиги аён бўлади.

5.1-расмда танлаб бўлиш (1), квадратик ғалвир (2) ва сонли майдон ғалвири (3) усуллари бўйича тузилган алгоритмлар мураккабликларининг х, яъни модуль бинар узунлигига нисбатан ўзгариш графиги келтирилган.

Шуни қайд этиш лозимки, квадратик ғалвир усули сонли майдон ғалвири усулидан 390 битли модулларни факторлашда мураккаблик бўйича устунликка эга. Шунингдек, 4-расм асосида симметрик алгоритмлар шифрлаш калити узунлигига мос факторлаш мураккаблигини берувчи RSA алгоритми модулининг битлар сонини аниқлаш мумкин. Масалан, 390 битли RSA- модулни факторлаш 60 битли симметрик тизим шифрлаш калитини топиш мураккаблигига тенг.