About the complexity of Pollard's p-1 method

Question

I'm currently working on a project for a computational math subject, which is about different algorithms on factoring and I'm having a little problem with the analysis of the complexity of Pollard's p-1 method.

The problem is the following: given a number $N$ which we want to factor and a bound $B$, this method has mainly three steps for factoring $N$:

1. Calculating $m=lcm(1,2,\dots,B)$

2. Calculating $a^m\;(mod\;N)$ for some $a$ coprime to $N$

3. Calculating $gcd(a^m-1,N)$

I have found and checked the calculations, that step $1.$ takes $O(B\log B)$ steps. Also, step $2.$ takes $O(\log m)\sim O(B)$ steps, which I've checked and found on several sources. And finally step $3.$ takes $O(\log N)$ steps.

So, after all this (I don't have a lot of experience working with complexity), I assumed that the complexity of the algorithm would be the 'sum' of the complexity of each step, which would be $O(B\log B+\log N)$ assuming it makes any sense summing them like that (I ignored the $O(B)$ since $O(B\log B)$ is bigger).

But the problem is that according to Wikipedia the complexity is $O(B\log B\log\log N)$, and I've also seen in other sources $O(B(\log N)^2)$, but they are not quite similar I think.

If anyone knows what I have wrong, or perhaps if it is somehow right, I'd appreciate some help. Thanks in advance!

Answer 1

You are making a lot of big and dangerous assumptions here and there, which is leading you to an incorrect result.

Just a couple things to get you started:

1. You cannot just "sum" the complexity of each step. That means each step runs individually, independent to each other. The algorithm, at least the one described on Wikipedia, does not run its steps individually. Remember that each steps, at least the one of Wikipedia, are actually dependent on each other, and the algorithm is just "compartmentalized" into individual steps for clarity.
2. Please cite your sources: where is your algorithm or at least an implementation of it? What are these "several sources" you are talking about? The algorithm that you are describing (or at least a part of it) is not really identical to the one on Wikipedia, so they are going to have a different runtime complexity.

Before you jump into calculating the complexity of your algorithm, I would suggest that you: (1) Try running your algorithm by hand to understand how it works; what are the inputs and the expected outputs? Does your algorithm produce the correct outputs? (2) Now try running the algorithm on Wikipedia by hand. Does it run differently than you expected? (3) Now what can you say about the complexity of your algorithm?