USING A DETERMINISTIC PARTITIONING FUNCTION FOR POLLARD’S RHO METHOD PARALELLIZATION

Abstract

An improved method for parallelization of Pollard’s algorithm for solving the discrete
logarithm 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.