Speeding Up the Pollard Rho Method on Prime Fields

摘要

We propose a method to speed up the r-adding walk on multiplicative subgroups of the prime field. The r-adding walk is an iterating function used with the Pollard rho algorithm and is known to require less iterations than Pollard's original iterating function in reaching a collision. Our main idea is to follow through the r-adding walk with only partial information about the nodes reached. The trail traveled by the proposed method is a normal r-adding walk, but with significantly reduced execution time for each iteration. While a single iteration of most r-adding walks on F{sub}p require a multiplication of two integers of log p size, the proposed method requires an operation of complexity only linear in log p, using a pre-computed table of size O((log p){sup}(r+1)·log log p). In practice, our rudimentary implementation of the proposed method increased the speed of Pollard rho with r-adding walks by a factor of more than 10 for 1024-bit random primes p.