Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.