1
$\begingroup$

I am given the following information:

Given $p=234917, g=281$, we want to determine the $b<400$ such that $g^b\equiv 92646 \mod p$. Furthermore, note that $p-1=2^2\cdot11\cdot 19\cdot 281$. Also, it is given as a hint that $g$ has order $117458=2\cdot11\cdot19\cdot281$. Lastly it is given somewhere earlier that $281$ is the order of the subgroup generated by $19452$.

I am able to solve this problem using Pohlig-Hellman, but I cannot figure out why the hint has anything to do with it. Is there another method that allows easy solving of this problem that uses this information?

$\endgroup$

1 Answer 1

2
$\begingroup$

The hint seems to just point you to using Pohlig-Hellman. We can use this approach whenever the order of our base element is smooth, in this case $g$ which has smooth order $2\cdot11\cdot19\cdot281$. Note that in your case every element will have smooth order, since the group has smooth order itself. This is not necessarily true.

For example take $$q=2^2\cdot11\cdot19\cdot281\cdot1329227995784915872903807060280347812+1,$$ which is much less smooth. It contains the element $$r=53150523888507461622439950315390442339087$$ of order $q-1$, which is not smooth (for some definition of smooth, of course). It also contains $$s=179329567444559024290726203799323921549272$$ of order $2\cdot11\cdot19\cdot281$.

So in $(\Bbb Z/q\Bbb Z)^*$ we could use Pohlig-Hellman for a discrete logarithm with base $s$, but not with base $r$ (or only partially).

$\endgroup$

You must log in to answer this question.

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