1
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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