# About the complexity of Pollard's p-1 method

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!

• The big problem of the p-1-method , although occasionally remarkably successful , is that it has a little chance to find even rather small factors in a reasonable amount of time. This was drastically improved by establishing the ECM-method. Commented Nov 4, 2022 at 9:11
• Yes, the project we are doing is studying several factoring algorithms, analyzing their complexity and how to optimize them. The algorithms are (i might miss some): p-1 and rho methods, both from Pollard, then Lenstra's ECM, the quadratic sieve, Fermat's (which is the one in which you assume there are two close factors of the number), and possibly another one I'm forgetting. Commented Nov 9, 2022 at 1:28
• The only algorithm I remember not in your list (besides trial division, which we should omit) is SQUFOF. Commented Nov 9, 2022 at 7:55
• I'll take a look someday, but the project is due in two days hehe, so we won't be able to include it; we have a lot to work on yet. Thanks anyways!! Commented Nov 9, 2022 at 20:07

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?

• I don't have the sources at hand, but they were around 3/4, that some where from this website and another one was the paper from a student, the link to the paper is: math.mcgill.ca/darmon/courses/05-06/usra/charest.pdf which i found quite useful Commented Nov 1, 2022 at 1:12
• Wikipedias algorithm is almost the same as mine, except that instead of saying $lcm(1,2,\dots, B)$ they wrote down a formula for it that is pretty intuitive. But aside from that the only difference is that they didn't consider $a^m-1 \;(mod\; N)$, but in general it is the same. Commented Nov 1, 2022 at 1:15
• Also, I can confirm that the algorithm runs correctly and ouputs factors of the number, when the gcd isn't 1 Commented Nov 1, 2022 at 1:15
• I think that I do understand the algorithm, but I just don't have background or much understanding on complexity, and my professor asked for analysing the complexity of each algorithm. Commented Nov 1, 2022 at 1:22
• I must point out that $lcm(1, 2, ..., B)$ is actually not the same as what is used on the Wikipedia. Moreover, there are many ways that $lcm()$ itself can be implemented (e.g. brute force division or Sieve of Eratosthenes, etc.). There is no way to know that purely based on what you described on your question. Even your paper that you linked points out that using $lcm()$ is a different way of implementing Pollard's algorithm. This is one of your "dangerous assumptions" that I was talking about. Commented Nov 1, 2022 at 3:56