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

Аннотация

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