A Method to Eliminate Fruitless Cycles for Pollard's Rho Method by Splitting a Seed-point Table for a Random Walk
Shota Kanzawa, Hiromasa Miura, Yasuyuki Nogami, Yuta Kodera, Takuya Kusaka · 2022
The most efficient method for solving ECDLP is the Pollard-Rho method, which is known to be more efficient in solving ECDLP by using skew Frobenius mapping and splitting a seed-point table to eliminate the fruitless cycles, but some fruitless cycles increase non-negligibly. In this paper, we propose a method to further reduce the number of fruitless cycles in the Pollard's rho method using skew Frobenius mapping. We also apply the proposed method to a 21-bit BN curve and confirm its effectiveness.