# Pollard Rho Factorization

**Idea.** Pseudo-random walk with Floyd cycle; gcd of differences yields a factor.

```python
import math,random
def pollard(n):
    if n%2==0: return 2
    while True:
        x=random.randrange(2,n-1);y=x;c=random.randrange(1,n-1);d=1
        while d==1:
            x=(x*x+c)%n;y=(y*y+c)%n;y=(y*y+c)%n;d=math.gcd(abs(x-y),n)
        if d!=n: return d
```

**Interview tip.** State the complexity before coding, then walk one small example by hand to show the invariant holds.

*Disclosure: practice note shared by the Linkjob AI team.* For live mock-interview practice see [real-time interview help](https://www.linkjob.ai/).
