3

Let $a,b,c\in\mathbb{Z}$. Assume that $a,c\leq 2^p$ and $b\leq 2^q$ - that is, the bit sizes of $a$ and $c$ are bounded by $p+1$ and the bit size of $b$ is bounded by $q+1$. Can I decide whether $$ a^b=c $$ in poly$(p,q)$-time? Can I decide $a^b=c$ in poly$(p,\log q)$-time?

It is clear that I am not allowed to compute $a^b$ as the size of $a^b$ is exponential in $q$. On the other hand, my intuition says it must be correct: If $q$ is small (compared to $p$), then I can compute $a^b$. Otherwise, it is big, and either $a$ has big bit size so $a^b$ cannot be equal to $c$, or it is small so the bit size of $a^b$ does not actually exceed $p$. I think this argument can be made rigorous. On the other hand, I have no idea if I can actually solve the problem in poly$(p,\log q)$-time. I guess it is not actually correct.

Levent
  • 4,804
  • 1
    You may find this helpful: https://www.geeksforgeeks.org/check-if-a-number-is-power-of-another-number/ – VIVID Oct 07 '20 at 10:21
  • 1
    Doesn't apply here, because as the OP says, they do not want to consider multiplication an O(1) operation. – Bananach Oct 07 '20 at 12:45

1 Answers1

1

I think this problem can be solved in $O(p^3)$ steps.

First, I assume $a,b,c \ge 0$ (the other cases either reduce to this, or for $b < 0$ have only very simple solutions).

$a=0, a=1$ are again simple to solve, as are $b=0, b=1$.

Now calculate $a^2=a\times a, a^3=a^2\times a,\ldots$ by simply multiplying the previous power by $a$ again, until you either reach $a^b$, or your calculation leads to a number $>2^p$.

If you reach $a^b$, compare it with $c$ and decide. If your calculation reaches a number $>2^p$, then obviously $a^b > c$.

Each multiplication is using 2 numbers $\le 2^p$, so at most $p+1$ binary digits, resulting in $O((p+1)^2)=O(p^2)$ time effort for a multiplication. Since $a\ge 2$, we have that $a^{p+1} \ge 2^{p+1} > 2^p$, so the algorithm ends at the latest after you calculated $a^2,\ldots, a^{p+1}$, which are at most $p$ multiplications.

That means you have at most $p$ multiplications each taking $O(p^2)$ time, giving you $O(p^3)$ time. The comparison (if necessary) takes $O(p)$ time, so is not relevant.

In effect you were right that a big $b$ leads to an "early exit" because the power becomes so big. As can be seen above, $b>p$ is already too big, so the algorithm doesn't need to take $q$ into account at all, at least when just looking if a polynomial time algorithm exists.

Ingix
  • 14,494
  • Thank you for the nice answer, I am also very happy that $q$ does not appear in the complexity. I'll check more carefully and then accept. However, I have a small question: You keep multiplying with $a$, though you can also repeatedly square, i.e. $a,a^2,a^4...$ which would probably result in a $O(p^2\log p)$. What do you think? – Levent Oct 08 '20 at 09:51
  • Yes, that works as well. I tried for the "simple" approach first, and that worked.I think you might also be able to get all the squares in $O(p^2)$ time, as the earlier numbers can't use all the $p$ bits (in fact, will have much less than $p$ bits), so have lower complexity to square. Similar the product of the squares (to get $a^b$) should have complexity $O(p^2)$, not $O(p^2\log p)$, if you start with the small numbers that have way less bits. – Ingix Oct 08 '20 at 12:20