0

I'm curious about the best possible computational time complexity of solving a linear congruence of the form

$$ A p + C \equiv 0 \pmod {2^b} $$

where $A$, $b$ and $C$ are all positive integers and $p$ is the variable we are looking for. $A$ is coprime with $2^b$. Also $2^b$ can be arbitrarily large, but $A$ is approximately the same magnitude.

Update I'm only looking for a rough estimate. Actually I'm more interested if this can be done in polynomial time depending on $b$. (Modulo is constant time, addition is $\mathcal{O}(b)$, multiplication is $\mathcal{O}(b^2)$.)

Bill Dubuque
  • 272,048
Gergely Nagy
  • 1
  • You asked for computational time complexity for a solution, but did not tell use what time complexity assumptions you are using for arithmetic operations. – Somos Mar 05 '21 at 20:26
  • In a sense it does not make too much difference, but let's assume that addition is $\mathcal{O}(b)$, multiplication is $\mathcal{O}(b^2)$. Modulo with $2^b$ is a constant time operation. – Gergely Nagy Mar 06 '21 at 19:33

0 Answers0