Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let's say, we have a large number $n=181937053$ and $f(x)=x^2+1$. And also we know that $n=12391 \times 14683$.

The problem is that ,using Pollard rho method, can we find the algorithm iteration times need to factor this number? ($x_0,y_0 = 2$)

share|improve this question
I think you're supposed to implement the algorithm, then run it with code that counts the number of iterations until it succeeds. I don't think you'll be able to predict the number of iterations without running it. –  Brock Hansen Mar 1 '14 at 1:13
Brock is correct; you can give a plausibility argument that it should usually take around $O(\sqrt{p})$ iterations (where $p$ is the smaller prime factor), but it looks unlikely you'll be able to say something like "this will take precisely 165 iterations" without actually running it. –  poncho Mar 1 '14 at 4:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.