4
$\begingroup$

It's easy to show that 3 is a primitive root $\bmod 17$, but how do I use it prove the congruence?

Is there a general way to solve any congruence of the form $a^x \equiv b \pmod{c}$ if you know a primitive root $\bmod c$ and c is big (without brute force)?

$\endgroup$
7
  • $\begingroup$ Well, a way is to try out all the $x$s in the range $[0,15]$:-). A more useful answer is that this is closely related to the notorious discrete logarithm problem. There are more efficient methods than brute force. For example you can utilize the factorization of $\phi(c)$. Note, because your base is not necessarily a primitive root, it is possible that there are no solutions. $\endgroup$
    – Jyrki Lahtonen
    Jun 18, 2015 at 6:44
  • $\begingroup$ so there is no general solution to for bigger c without using brute force ? $\endgroup$
    – Boris Morozov
    Jun 18, 2015 at 7:01
  • 1
    $\begingroup$ Boris, depends on what you call brute force. There are methods significantly faster than testing each and every $x$. That Wikipedia page links to seven types of attacks. But none have a polynomial complexity. This is the reason some cryptographic methods based on the difficulty of the discrete logarithm problem (such as Diffie-Hellman) are considered safe. $\endgroup$
    – Jyrki Lahtonen
    Jun 18, 2015 at 7:05
  • 1
    $\begingroup$ See this earlier answer by yours truly for an example of what using one of the approaches entails. Notice that the example there is not "general". In a homework assignment something lucky must happen for the task to be reasonable :-) $\endgroup$
    – Jyrki Lahtonen
    Jun 18, 2015 at 7:11
  • 1
    $\begingroup$ sorry for ambiguity what i mean is there a way to solve it by hand within reasonable time (30mins) for c > 500 for example . i guess no since polynomial complexity is easy for computer but not for me :D . thanks for explaining ..... i saw this problem in a problem set and thought there is some fast and elegant way to solve it , using euler totient function or some other neat method . but now it makes perfect sense since the next topic in the course was RSA . $\endgroup$
    – Boris Morozov
    Jun 18, 2015 at 7:13

2 Answers 2

Reset to default
4
$\begingroup$

Here if you observe that $7=3^{11}\quad \& \quad 6=3^{15}$ so Putting above we have

$3^{11x}\equiv 3^{15}~ \pmod{17}$

$\implies 3^{11x-15}\equiv 1 \pmod{17}$

3 is primitive root so $11x-15=16n$ for some $n\in \mathbb{Z}$

$\implies x=\dfrac{16n+15}{11}$ will be integer

You can easily see that $n=8$ satifies this ,So $x=13$ will be a solution of given .

There will be more solution of this too.

$\endgroup$
4
  • $\begingroup$ thanks but is there a general way to solve it without using brute force? if c was a bigger number instead of 17 this brute force solution would take very long time . $\endgroup$
    – Boris Morozov
    Jun 18, 2015 at 7:00
  • 1
    $\begingroup$ $7^3 = 3$ is pretty easy to see, and substituting that into the $6=3^{15}$ will get you there quite fast. It still boils down to brute force and lucky guesses, of course. $\endgroup$
    – user208649
    Jun 18, 2015 at 7:08
  • $\begingroup$ If we're allowed to "observe" that $7=3^{11}$ and $6=3^{15}$, why can't we just "observe" directly that $7^{13}=6$? I'm not faulting your answer $-$ I think it's a bad question. $\endgroup$
    – TonyK
    Jun 18, 2015 at 8:23
  • $\begingroup$ TonyK its two step problem . i omitted the first step . so yes your right . first step is proving that 3 is primitive root mod 17 . so at the process you compute $3^{11} \mod 17$ and $3^{15} \mod 17$ and use your previous computations .(you dont need to compute $7^{13}$ so you cant "observe" it) $\endgroup$
    – Boris Morozov
    Jun 18, 2015 at 8:40
1
$\begingroup$

You can reduce the amount of brute force quite significantly. Using an interval $d$ of approximately $\sqrt{c}$, make an "island" of values $a\cdot g^i$ with $i\in \{0,d{-}1\}$, then calculate all $g^{jd}$ and identify the coinciding value.

$\begin{array}{c|c} k\ (d=4) &g^k & a\cdot g^k & b\cdot g^k \\ \hline 0 & 1 & 7 & 6 \\ 1 & 3 & \color{red}{4} & \color{violet}{1} \\ 2 & 9 & 12 & 3 \\ 3 & 10 & 2 & 9 \\ 4 & 13\\ 8 & 16\\ 12 & \color{red}{4}\\ 16 & \color{violet}{1}\\ \end{array}$

giving, $\bmod 17$, $7\cdot 3\equiv 3^{12}$ and $6\cdot 3\equiv 3^{16}$ , so $7\equiv 3^{11}$ and $6\equiv 3^{15}$.

Then we need to find $11x\equiv 15 \bmod 16 (=\phi(17))$, which means finding the inverse of $11\bmod 16$, which here is $3$, giving $x\equiv 15\cdot 3 \equiv 13\bmod 16$.

Obviously for this exercise in small numbers this is more work thn simply calculating the powers of $7 \bmod 17$, but for larger numbers it avoids calculating all powers.

Because $3$ is a primitive root $\bmod 17$, we are guaranteed to find suitable exponents in the first stage.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .