Calculating the discrete logarithms, modulo $p = 1217$

1k Views Asked by At

I'm given a prime number $p = 1217$

I'm also given the following equations:

$ 40 = \log2 \mod 64 $

$ 63 = \log3 \mod 64 $

$ 13 = \log5 \mod 64 $

$ 13 = \log2 \mod 19 $

$ 10 = \log3 \mod 19 $

$ 01 = \log5 \mod 19 $

The question asks to give the answers to

$ \log 2 \mod p-1 $

$ \log 3 \mod p-1 $

$ \log 5 \mod p-1 $

I know the answers are $488, 447, 77$ respectively.

And I know they are the Discrete Logarithms of $2,3,5$ respectively.

However there is no other explanation of how to get this answer.

I've observed that $1217$ is the Lowest common multiple of $64$ and $19$.

I also think the Chinese remainder theorem might be useful here.

It bothers me that we don't know the base of the logarithms and this makes me totally confused.

I would hugely appreciate an explanation on what's going on here, I don't fully understand what the question is asking, let alone how they got to their answer.

Thanks a lot for any help in advance.

EDIT

Here's the table I was given. It's so vague I know.

enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

Let's see what the right question is.

The basic proposition is this. Suppose, given $y$, $b$ and prime $p$, you want to find $x$ such that $b^x \equiv y \mod p$, where $b$ is a primitive root mod $p$. Suppose $p-1 = cd$ with $c$ and $d$ coprime. Then $y^c \equiv b^{xc} \equiv (b^c)^x \mod p$, where $b^c$ is a $d$'th root of $1$ mod $p$. This will determine $x \mod d$. Similarly, $y^d \equiv (b^{d})^x \mod p$ determines $x \mod c$. Then we can use Chinese Remainder Theorem to recover $x \mod cd$.

In this case $p = 1217$ is prime, with $p-1 = 1216 = 64 \times 19$ So the data you're being given here says, in the case $y=2$, that (for the unspecified $b$, which just happens to be $34$) $(b^{19})^{40} \equiv 2^{19} \mod p$, while $(b^{64})^{13} \equiv 2^{64} \mod p$. You conclude that $x \equiv 40 \mod 64$ and $x \equiv 13 \mod 19$, and all you have to do is use Chinese Remainder Theorem to recover $x = 488$.

0
On

Chinese remainder theorem says:

if $a$ and $b$ are co-prime and $pa + qb = 1$ and

$x\equiv n(\mod a)\\ x\equiv m(\mod b)$

then $x\equiv pam+qbn (\mod ab)$

$19*64=1216\\ 27*19-8*64 = 1\\ x\equiv 40(\mod 64)\\ x\equiv 13(\mod 19)\\ x\equiv 13*(-8)*64+40*27*19 (\mod 1216)\\ $