Использование детерминированной функции разбиения на множества для распараллеливания ρ-метода Полларда

Елена Григорьевна Качко, Константин Анатольевич Погребняк

Аннотация


В работе предлагается усовершенствованный метод распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования в группе точек эллиптической кривой и в мультипликативной группе конечного поля для систем с общей памятью. Усовершенствование метода достигается за счет построения детерминированной функции разбиения на множества. Такая функция позволяет организовать два независимых сбалансированных вычислительных потока построения блока элементов группы фиксированной длины. Далее анализируются известные функции итерирования точек в алгоритме Полларда и строится обобщенная детерминированная функция разбиения на множества.

Ключевые слова


дискретный логарифм; метод Полларда; эллиптическая кривая

Полный текст:

PDF

Литература


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.




DOI: http://dx.doi.org/10.14529/cmse130305