# Running time complexity of finding maximal power of divisor that divides natural number

Given $$n \in \mathbb{N}$$, a divisor $$p\vert n$$, I would like to efficiently find $$e\in\mathbb{N}$$ with $$p^e \vert n$$, and $$e$$ maximal with this property. I will assume that multiplication/division of two $$b$$-digit numbers has time complexity $$O(b^{\log_{3}{5}})$$. (Ie. I use the Toom-Cook algorithm.) Then it can be shown that the naive repeated division approach has a complexity that's worse than $$O(\log^{2}(n))$$.

An alternative I considered is performing a binary search like algorithm on $$\{0, 1, ... \log{n}\}$$, where I assume that $$\log{n}$$ is given. This means that instead of checking all $$\log{n}$$ candidate powers, it suffices to consider only $$\log{\log{n}}$$ elements of the above set of possible powers. For each candidate power $$p^f$$ a division $$p^f \vert n$$ is required, which can be performed in $$O(b^{\log_{3}{5}})$$. We only need to compute the maximal power of $$p$$, $$p^{\log{n}}$$ as we can store intermediate powers (even if we use repeated squaring , precisely because a binary search is performed on our search space). The cost of computing $$x^y$$ via repeated squaring is $$O((y \log{x})^{\log_{3}{5}})$$. Hence the overall complexity of this approach is $$O(\textit{exponentation_cost} + \textit{division_costs}) = O((\log{n} \log{p})^{\log_{3}{5}} + \log{\log{n}} \cdot (\log{n})^{\log_{3}{5}})$$

Now supposing that $$p$$ is small relative to $$n$$, that is $$p \in O(\log{n})$$, then the above expression belongs $$O((\log{n} \log{\log{n}})^{\log_3{5}})$$, which isn't too bad.

My questions are:

1. Does the above analysis look sensible?
2. Is there a standard/better way to do this?

Here is one more approach you could consider, depending on whether you care more about theoretical running time or pragmatic solutions:

1. Use binary search to find the smallest $$k$$ such that $$p^{2^k}|n$$ but $$p^{2^{k+1}}\not|n$$.

2. Compute $$m = (n/p^{2^k}) \bmod p^{2^k}$$.

3. Recursively find the smallest $$i$$ such that $$p^i|m$$ but $$p^{i+1}\not|m$$.

(In the third step, you know $$0 \le i < 2^k$$, so you have a narrower range for your search, and $$m$$ is smaller than $$n$$, so you are working with smaller numbers.)

Then it follows that the solution to your problem is $$e=2^k + i$$.

Note that $$k \le \lg {\log n \over \log p}$$, so you can find $$k$$ with binary search in $$O(\log \log {\log n \over \log p})$$ steps, where each step does a single trial division. In the worst case, $$m$$ might not be much smaller than $$n$$, so this might not save you much. But in many cases, $$m$$ will be vastly smaller than $$n$$, so step 3 is a lot easier than the original problem. In particular, on average $$m$$ will be on the order of magnitude of $$\sqrt{n}$$ or less, so heuristically we might expect that after $$\lg \lg n$$ recursions we're dealing with constant-sized numbers, and heuristically we might expect the total running time to be dominated by step 1. This won't always be true in the sense of worst-case complexity, though.

If p divides n and p > sqrt(n) then the maximum power is 1 :-)

Note that if the maximum power is large then p must be small, and the time for division is substantially shorter. I’d first want to know what the practical use of this is. For example if p is 10 digits an n is random, it is very unlikely that the largest power is not 1. If p=2 is start by calculating n modulo 2^30.