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?