2

$x$ is fixed odd positive integer value. $n$ and $w$ are fixed positive integer values. $a$ is positive integer value.

I am interested for $n=41$ and $w=160$, but would appreciate a general algorithm.

I know how to find any $a$ for which $a^n \equiv x \pmod{2^w}$. Algorithm requires $w$ steps:

  1. Let $a\leftarrow1$
  2. Iterate $i$ from 1 to $w-1$ and for each $i$ do:
    • if $a^n \equiv x \mod(2^{i+1})$, do nothing.
    • otherwise assign $a \leftarrow a+2^i$

Is this algorithm giving the smallest value $a$ for which $a^n \equiv x \pmod{2^w}$? How to find smallest $a$ for which $a^n \equiv x \pmod{2^w}$?

desowin
  • 23

1 Answers1

2

Note that here, the exponent $n$ is odd, while the order of every element modulo $2^w$ divides $\phi(2^w)=2^{w-1}$. Since $n$ and $2^{w-1}$ are relatively prime, the solution to $a^n=x\pmod{2^w}$ exists and is unique modulo $2^w$. So if you have a solution $a<2^w$, then it is indeed the smallest positive solution.

Another way of solving these problems is to find integers $y$ and $z$ for which $ny+2^{w-1}z=1$ (always possible when $n$ and $2^{w-1}$ are relatively prime), for then $$ (x^y)^n = x^{ny} = x^{1-2^{w-1}z} = x\cdot(x^{2^{w-1}})^z \equiv x\cdot1^z = x\pmod{2^w} $$ (where the congruence is due to Euler's theorem). Therefore $a\equiv x^y\pmod{2^w}$ is the solution. Both finding $y$ (from the extended Eucliden algorithm) and computing $x^y\pmod{2^w}$ are extremely fast when implemented correctly.

Greg Martin
  • 78,820
  • How do I choose and/or find $v$? – desowin May 10 '16 at 06:21
  • Eep, I had variable-name drift. Fixed now. – Greg Martin May 10 '16 at 07:16
  • Is it possible to get solution that would work also for even values of $x$? – desowin May 10 '16 at 16:21
  • If $x$ is even then $a$ has to be even; if $x$ is not a multiple of $2^w$, then the power of $2$ dividing $a^n$ has to be exactly the same as the power of $2$ dividing $x$. So just factor out those powers of $2$ explicitly, and the problem reduces to a problem with odd numbers and a smaller value of $w$. (And if $x$ is a multiple of $2^w$, then you're just solving $a^n\equiv0\pmod{2^w}$ which is very easy.) – Greg Martin May 10 '16 at 17:48
  • I have implemented it for even numbers and I am not getting correct results. If $x$ is even and $x/2$ is odd, I calculate $y$ for which $ny+2^{w-2}z=1$ and then I compute $a=2((x/2)^y \pmod {2^{w-1}})$. But then $a^n \equiv (x2^{40}) \pmod {2^{w+40}}$. $n$ and $w$ remains unmodified ($n=41$, $w=160$). What am I doing wrong? – desowin May 11 '16 at 17:33
  • Say $x$ is divisible by $2^v$ with $0 < v < w$. Then $a$ must be even, and the power of $2$ dividing $a^n$ must be exactly $2^v$. So there are only finitely many $n$ for which a solution even exists, namely the divisors of $v$. (To emphasize: $n$ has finitely many possible integer values, not values modulo something.) I suggest considering each such $n$ separately. – Greg Martin May 11 '16 at 20:05
  • My error was that I thought power of 2 dividing $a$ should be $2^{v}$, but it is the power of 2 dividing $a^{n}$ that should be $2^{v}$. – desowin May 12 '16 at 13:10