1
$\begingroup$

I am stuck in a problem, where i have to compute discrete logarithm without use of brute force. Here is the problem:

Given is a prime number $p=21495809$. Find $x$, if $7^{x}=14750571\, mod\, p$.

First i saw that we can factor $14750571=3\times 11\times 443\times 1009$. I guess i have to work somehow with the Chinese Remainder Theorem, but i don't know how to apply it for this problem, because the number $p$ is a prime number. Another observation was $7^{p-1}\equiv 1\, mod\, p$ by Fermat's little theorem, but it doesn't bring anything.

Does anyone see an approach how to solve this problem? I would be glad to read your comments and ideas. Thank you in advance!

$\endgroup$
4
  • $\begingroup$ The answer is 1312. $\endgroup$
    – TBrendle
    Nov 8, 2013 at 23:02
  • 2
    $\begingroup$ what are they doing in your class? $\endgroup$
    – Will Jagy
    Nov 8, 2013 at 23:05
  • 1
    $\begingroup$ An approach would be to compute $7,7^2,7^3,\dots$ modulo $p$ until you get the answer. This will be somewhat faster if you program a computer to do it than if you try it with pencil and paper. $\endgroup$ Nov 8, 2013 at 23:12
  • $\begingroup$ In class we didn't have yet any particular algorithms like Pohling-Hellman or baby giant step...So, it must be possible to calculate it in another way. How about calculating $x=log_{7}1475057 \, mod\, p=log_{7}3(mod\, p)+log_{7}11(mod\, p)+log_{7}443(mod\, p)+log_{7}1009(mod\, p)$, where i try to calculate every term and find $x$ as a sum of the terms? Does it make sense at all? $\endgroup$
    – Lullaby
    Nov 9, 2013 at 23:50

1 Answer 1

2
$\begingroup$

I guess that you are supposed to take advantage of the fact that $p-1=2^{19}\cdot41$. With nothing else to go by, let's see where that takes us.

Is $7$ a primitive root? A round of repeated squaring (assuming you are allowed to use WA or a suitable CAS for this) shows that $$7^{(p-1)/41}=7^{2^{19}}\equiv4720468\pmod p.$$ As $p\equiv1\pmod4$ the law of quadratic reciprocity tells us that $$ 7^{(p-1)/2}\equiv\left(\frac7p\right)=\left(\frac p7\right)=\left(\frac 67\right)=-1\pmod p. $$ This proves that $7$ is, indeed, a primitive root.

The factorization of $p-1$ tells us that $G=\Bbb{Z}_p^*$ is isomorphic to a direct product of cyclic groups $G\cong C_1\times C_2$ of respective orders $41$ and $2^{19}$. Here $C_1$ is generated by $7^{2^{19}}$ and $C_2$ is generated by $7^{41}\equiv5651199$. With $a=14750571$ we have $$ a^{41}\equiv 20030855\in C_2. $$

While repeatedly squaring $a$ modularly, a phenomenal piece of luck strikes (suspected something like this, for otherwise this could become quite a chore). Namely $$ a^{2^{13}}\equiv-1\pmod p. \qquad(1) $$ This means that $a$ is of order $2^{14}$ in $G$, so $a\in C_2$. Congruence $(1)$ actually shows that the base-7 discrete logarithm of $a$ has to be an odd multiple of $32\cdot41=1312$.

So we know that $a$ will be a power of $7^{1312}\equiv 14750571$. Well, well, TBrendle already told us this bit, so... Let me conclude by outlining how we could do the rest, if we had had $7^{1312}\equiv b\not\equiv a$. We know that $$ a\equiv b^s, $$ where $s=1+\sum_{i=1}^{13} s_i2^i$, and $s_i\in\{0,1\}$ for all $i$. We can calculate whether $s\equiv1$ or $3\pmod4$ by checking whether $(ab^{-1})^{2^{12}}=(b^{s-1})^{2^{12}}\equiv 1$ or $-1\pmod p$. This gives us $s_1$. Then we can figure out $s_2$ similarly by calculating $(ab^{-1-2s_1})^{2^{11}}$ and so on. This process can be speeded up producing, e.g. a look-up-table of eighth roots of unity in $G$ (or sixteenth - all depending how you tune it up).

If we hadn't had more than our share of luck we would have had to figure out all 19 bits of the discrete logarithm of $a$ in $C_2$. Then a similar (but shorter) calculation would have been carried out in the group $C_1$ of roots of unity of order $41$. After both of these we would then have used the Chinese Remainder Theorem to combine the logarithms from $C_1$ and $C_2$.

Moral: When attacking DLPs you use Chinese Remainder Theorem for factors of $p-1$. After all, the discrete logarithm takes values in the ring $\Bbb{Z}/(p-1)\Bbb{Z}$.

$\endgroup$
4
  • $\begingroup$ Dear Jyrki, you're a genius! Thank you very very much for your wonderful "algebraic" solution :) $\endgroup$
    – Lullaby
    Nov 10, 2013 at 21:07
  • $\begingroup$ May i ask a question? How did you get find that the congruence (1) gave you that $32\cdot 41=1312$, where did $2^5=32$ come from? Thank you again for the great help! $\endgroup$
    – Lullaby
    Nov 10, 2013 at 22:04
  • $\begingroup$ $1312=(p-1)/2^{14}$ And we knew that $a$ has order $2^{14}$. $\endgroup$ Nov 10, 2013 at 22:06
  • $\begingroup$ Then it's clear. Great! :) Thanks a lot! $\endgroup$
    – Lullaby
    Nov 10, 2013 at 22:07

You must log in to answer this question.

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