Факторизациялоо алгоритмдердин салыштырмалуу анализи = Comparative analysis of integer factorization algorithms

Көптөгөн ачык ачкычтуу криптосистемалардын негизи катары колдонулган натуралдык санды факторизациялоо проблемасы заманбап компьютерлер үчүн да оор маселе болуп саналат. Биз бул иште С программалоо тилинде GMP китепканасын колдонуп, 4 алгоритмди иштеп чыктык жана бул алгоритмдердин иштөө убакыттарын салыштырдык. Алгоритмдер ар кандай өлчөмдөгү сандарды, ошондой эле факторлорунун ортосунда ар кандай аралык болгон сандарды факторизациялоо үчүн колдонулду.Биздин жыйынтыктар 296 биттик санды факторлорго ажыратууда Поллард rho алгоритминин эң бат иштешин, ошол эле учурда, факторлордун ортосундагы аралык кичине болгон учурда Ферма алгоритминин эң бат иштешин көрсөттү. Мындай сандар үчүн Брент алгоритминин жай иштегени байкалды, бирок бул алгоритм Ферма алгоритми натыйжа бере албаган учурларда ийгиликтүү жыйынтык бере алды. -

Keywords: Натуралдык сандын факторизациясы, GMP,Тривиалдык бөлүү, Ферма алгоритми, Поллард rho алгоритми, Брент алгоритми =

Integer factorization problem, which is used as the basis in many public key cryptosystem, is generally thought to be hard problem even on a modern computers. In this work we implement 4 integer factorization algorithms using GMP library on c++ and compare the running time of these algorithms. Algorithms were used to factor numbers of different sizes, as well as for number with different distance between factors. Our results showed that for numbers up to 296 bits the Pollard rho algorithm is the fastest one, while Fermat algorithm is fast when distances between factors are small. Brent algorithms appeared to run slower for this rage of numbers, however it succeeded to factor numbers which Fermat algorithm fail to factor.