# Complexity of Pollard's p-1 method

I'm working on the complexity of various integer factorization algorithms and am kind of stuck on the complexity of Pollard's p-1 method. (I'm using Prime Numbers - A Computational Perspective by Crandall & Pomerance; as well as some notes by P. Montgomery)

In the p-1 method we are given $n$ and we choose a smoothness bound $B$, and then calculate $M$ as the product of prime powers less or equal than $B$. We then calculate $a^M \mod n$.

Now, as Montgomery's notes say (and I've verified this), the amount of modular multiplications is $O(\log M) \approx O(B)$. However, this is supposedly an exponential algorithm, and this is where I'm stuck (or at least unsure). I'm not very known with verifying time complexity outside of simply interpreting L-notations, so I tried to turn $O(B)$ into the L-notation.

Now, my first assumption: we have to use the $B$ required in the worst case. Worst case would be $n = pq$ both prime, with $(p-1)/2$ and $(q-1)/2$ both prime. In this case we'd have to pick $B \approx \sqrt{n}/2$. This gives us $O(\sqrt{N})$.

I tried transforming this from Big-O notation to L-notation by saying $O(\sqrt{N})$ would be approximately $c\sqrt{N}$ (my second assumption. Probably not really allowed, but I'm going to pull the $c$ into a $o(1)$ soon). Then, I used the $\exp(\log(x)) = x$ identity to say that this is equal to

$\exp(\log(c) + 1/2 \log(N)) = \exp([\log(c)/\log(N) + 1/2 ]\log(N))$

Here, I say that $\log(c)/\log(N)$ is $o(1)$ (third assumption) and thus I get for the complexity:

$\exp(1/2 + o(1)]\log(N))$

Which is clearly exponential due to the $\log(N)$.

So, now I'm wondering if my three assumptions are correct, if so if there's a way to prove them, if not if there's another way to show the complexity is exponential.

Thanks.

-

I think your reasoning is fine. The time complexity is actually slightly larger than $O(B)$. After your first assumption, you are done, since $\sqrt{n}$ eventually exceeds $(\log{n})^k$ for all $k$.