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

Question

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?

Answer 1

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.

Answer 2

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.