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

Сонли майдон ғалвири усули асослари

Дастлабки Поллард тезкор факторлаш усули томонидан таклиф этилган бўлиб, махсус кўринишдаги сонларни (масалан, Ферма сонларини) факторлаш (SNFS) учун мўлжалланган. SNFS усулида энг катта факторланган натурал сон 227 ўнли хонали рақамларда берилган сондир. Аммо RSA-модуллари махсус кўринишга эга бўлмаганлиги боис, уларни умумлашган сонли майдон ғалвири (GNFS) усули асосида факторлаш мумкин. Ҳозиргача эришилган рекорд натижалар 155 ўнли хонали (512 бит) сонлар учун эришилган. Бу сонни факторлаш учун 8400 mips-йил сарф бўлган.

Ҳозирги кунда сонли майдон ғалвири усули асосида 110 ва ундан ортиқ ўнли хонали узунликдаги модулларни факторлаш учун энг тезкор алгоритмлар ишлаб чиқилган. Квадратик ғалвир усули нисбатан тўппа- тўғри мақсадга элтишга етарли бўлса ҳам, сонли майдон ғалвири усули такомиллашган математик асосларга таяниши билан истиқболлироқдир.

Сонли майдон ғалвири ўз моҳияти бўйича алгоритм эмас, балки бир неча босқичдан таркиб топган алгоритмлар мажмуасидир.

Квадратик ғалвир алгоритмининг мураккаблиги

C₁=O(exp( (ln p)^1/2 (ln ln p)^1/2)) амал билан баҳоланса, сонли майдон ғалвири усулининг мураккаблиги C₂=O(exp(c(ln p)^1/3 (ln ln p)^2/3)) амал билан баҳоланади, бу ерда с1,9223. Сўнги ифодада (ln p)^1/2 ҳади (ln p)^1/3 га айланган, аммо C₂ да нисбатан катта с нинг қатнашиши квадратик ғалвир алгоритми узунлиги 110 ўнли хонали бўлган модуллар қулайлигига сабаб бўлади.

n нинг бинар узунлиги x=log n га тенг олиниши келтирилган усул мураккаблилигини симметрик криптотизимлар калит узунлиги бўйича мураккаблиги билан таққослаш имконини беради.

Қуйида келтирилган 5.1-жадвалнинг биринчи устунида усуллар, иккинчи устунида факторлаш учун амаллар сарфи f(x), учинчи устунида log₂f(x) келтирилган.

5.1-жадвал