USING A DETERMINISTIC PARTITIONING FUNCTION FOR POLLARD’S RHO METHOD PARALELLIZATION
DOI:
https://doi.org/10.14529/cmse130305Keywords:
discrete logarithm, Pollard’s rho method, elliptic curveAbstract
An improved method for parallelization of Pollard’s algorithm for solving the discretelogarithm problem in a group of elliptic curve points and in a multiplicative group of a Galois field for shared memory systems is suggested in the paper. Improvement of the method is achieved by constructing a deterministic partitioning function. Such a function allows to organize two independent load balancing computational threads for building a block of group elements of fixed length. Also we analyze advanced iteration functions for Pollard’s algorithm and build generic deterministic partitioning function.
References
Bai, S. On the efficiency of Pollard’s rho method for discrete logarithms / S. Bai, R. P. Brent // Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), January 22–25, 2008, Wollongong, NSW, Australia, Proceedings. CRPIT, 77. Harland J. and Manyem P.,
Eds. ACS. P. 125–131.
Качко, Е.Г. Параллельный метод Полларда решения задачи дискретного логарифмирования в группе точек эллиптической кривой / Е.Г. Качко, К.А. Погребняк // Па-
раллельные вычислительные технологии (ПАВТ–2012): труды международной научной конференции (Новосибирск, 26–30 марта, 2012 г.). – Челябинск: Издательский центр ЮУрГУ, 2012. – С. 723.
Горбенко, И.Д. Методы распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования для систем с общей памятью / И.Д. Горбенко, Е.Г. Качко, К.А. Погребняк // Высокопродуктивные вычисления (HPC–UA’2012): труды международной научной конференции (Киев, 8–10 октября, 2012 г.). – Киев: НАНУ, 2012. – С. 152–157.
Горбенко, И.Д. Параллельный метод Полларда решения задачи дискретного логарифмирования в мультипликативной группе поля Галуа / И.Д. Горбенко, Е.Г. Качко, К.А. Погребняк // Современные проблемы информационной безопасности на транспорте
(СПИБТ–2012): материалы всеукраинской научно-технической конференции с международным участием (Николаев, 29–30 ноября, 2012 г.). – Николаев: НУК, 2012. – С. 9–11.
