2
$\begingroup$

I'm trying to find the smallest integer $x$ such that $2^x \equiv 166 \pmod {330}$. It is result of a problem I am solving and I am wondering is there a way to find suitable $x$ without trying all possible values?

I've noticed that $x=20$ works.

Even some algorithm (it is part of the programming task and there will be way bigger numbers given) which would reduce at least the values I have to try somehow (not go from 1 up to 20).

$\endgroup$
1
$\begingroup$

Whenever you have $a^x\equiv b\pmod{n}$ it all depends whether $n$ is prime or composed. In case $n$ is composed you can reduce the problem by using little Fermat theorem.

e.g. if $n=pq$ then you get the system

$\begin{cases} a^{x}\pmod{p}\equiv(a\pmod{p})^{x\pmod{p-1}}\pmod{p}\equiv {a_1}^{x_1}\pmod{p}\\ a^{x}\pmod{q}\equiv(a\pmod{q})^{x\pmod{q-1}}\pmod{q}\equiv {a_2}^{x_2}\pmod{q}\end{cases}$

In our case, since $2$ is small already, $a=a_1=a_2=2$ do not change, but since $p,q$ are smaller you get less tries to perform to search for $x_1$ and $x_2$.

Once you get them, you can apply LCM or CRT to get $x$.

Unfortunately for prime numbers $p$, you cannot reduce further and if they are large, then you get to try all values.

There are however algorithms like baby-step giant-step to achieve discrete logarithm, but these are not easy and straightforward: https://en.wikipedia.org/wiki/Discrete_logarithm

$\endgroup$
  • $\begingroup$ I am not sure if I follow correctly. If you would not mind checking my steps on next example: 2^x = 2704 mod 5406 5406 -> 2 * 3 * 17 * 53 (p = 102; n = 53 for example) $\begin{cases} 2^{x}\pmod{102}\equiv(2\pmod{102})^{x\pmod{101}}\pmod{102}\equiv 1\\ 2^{x}\pmod{53}\equiv(2\pmod{53})^{x\pmod{52}}\pmod{53}\equiv 8\\ 2^{x1}\pmod{102}\equiv 1\\ 2^{x2}\pmod{53}\equiv 8\\\end{cases}$ 102 is not prime so I recursively continue solving? And stop for 53 since its prime? So I get basically equation for each prime in n and solve each one and find LCM for those numbers? $\endgroup$ – eXPRESS Dec 25 '18 at 14:01
  • $\begingroup$ Yes, this is it. I admit that generally we use this when $x$ is known, as for solving this kind of problem math.stackexchange.com/questions/3042801/… but it could be also used for equations. Here $53$ is quite smaller compared to $5406$ so $x_2$ is easier to find. If the $a_i$ are constant the lcm works fine, but if not, it is a little more complicated to find the correct power back, you have to use CRT with $(p_i-1)$ mods. $\endgroup$ – zwim Dec 25 '18 at 19:37
  • $\begingroup$ See en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for a complete description in most general case. My method is just a simplified version. $\endgroup$ – zwim Dec 25 '18 at 19:48
  • $\begingroup$ Thanks for confirmation/information and further materials. :) $\endgroup$ – eXPRESS Dec 27 '18 at 19:30
0
$\begingroup$

Write $330 = 2 \cdot 3 \cdot 5 \cdot 11$.

Then $2^x \equiv 330/2 + 1 \bmod 330$ iff $2^x \equiv 0 \bmod 2 $ and $2^x \equiv 1 \bmod p $ for $p=3,5,11$.

The order of $2$ mod $3$ is $2$.

The order of $2$ mod $5$ is $4$.

The order of $2$ mod $11$ is $10$.

Therefore, $x$ is a multiple of $lcm(2,4,10)=20$.

$\endgroup$
  • $\begingroup$ Thank you very much, but if I see correctly it yields n! options where n is count of numbers in LCM right? Hopefully that is gonna be enough for the huge numbers I will be given. :) $\endgroup$ – eXPRESS Dec 25 '18 at 11:06

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.