2

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).

eXPRESS
  • 203

2 Answers2

1

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

zwim
  • 28,563
  • 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?

     – eXPRESS Dec 25 '18 at 14:01
  • Yes, this is it. I admit that generally we use this when $x$ is known, as for solving this kind of problem https://math.stackexchange.com/questions/3042801/how-can-i-calculate-21335525-mod-7387/ 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. – zwim Dec 25 '18 at 19:37
  • See https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for a complete description in most general case. My method is just a simplified version. – zwim Dec 25 '18 at 19:48
  • Thanks for confirmation/information and further materials. :) – eXPRESS Dec 27 '18 at 19:30
0

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$.

lhf
  • 216,483
  • 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. :) – eXPRESS Dec 25 '18 at 11:06