Pollard Rho Factor Steps

Problem

Count Floyd cycle steps until Pollard rho finds a non-trivial factor of n using f(x) = x * x + c mod n.

Start tortoise and hare at 2, advance the hare twice per round, and stop when gcd(abs(x - y), n) is a non-trivial factor. Return the step count, or 0 when n < 4, the sequence cycles without a factor, or the gcd reaches n.

Hint

The difference sequence collides modulo a hidden prime factor long before modulo n.

Test cases

case 1

in: [8051,1]

expected: 3

case 2

in: [10403,1]

expected: 9

case 3

in: [91,1]

expected: 1

case 4

in: [97,1]

expected: 0

case 5

in: [15,1]

expected: 1

Starter codePython

import math


def pollard_rho_steps(n, c):
    # Your code here
    pass

5 test cases · run your code against them in the editor