0

I was working on a programming problem that eventually reduced to solving the inverse of the following:

$$y \equiv (x \times 2^k )\pmod{p}$$

for $x$, $k$, $p$, $y \in \mathbb{N}$ , $x$ < $p$, and $p$ is prime.

Given that I know $k$, $y$, and $p$, I had to solve for $x$.

I was able to solve the problem by repeatedly dividing by two $k$ times (adding $p$ before doing the division if the number was odd). My real question is if there was a better solution that I wasn't clever enough to figure out.

PMV
  • 101

2 Answers2

2

Using the Euclidean algorithm you can find a solution $a,b$ of the equation $$2^k a + pb = 1$$ very quickly, in which case $x \equiv y \cdot a.$

For example to solve the equation $10 \equiv 4x$ mod $13$, I write

$$13 - 3*4 = 1 \; \Longrightarrow \; 2^2 \cdot (-3) + 13 \cdot 1 = 1$$ so $$x \equiv 10 \cdot (-3) = -30 \equiv 9.$$

user399601
  • 1,711
1

I'm supposing that $p$ is an odd prime, as otherwise this is an uninteresting problem.

Notice that $2 \cdot \frac{p+1}{2} = p+1 \equiv 1 \pmod p$. Then similarly, $2^k \cdot \left(\frac{p+1}{2}\right)^k \equiv 1^k \pmod p$. So I think the fastest way is to compute

$$ y \left(\frac{p+1}{2}\right)^k \pmod p,$$ as this is equal to $$ \left( \frac{p+1}{2}\right)^k 2^k x \equiv \left( p+1 \right)^k x \equiv x \pmod p.$$

So you do one modular multiplication, and the answer is apparent. (This is possible because we know exactly how to invert the operation of multiplying by $2$.)

davidlowryduda
  • 91,687