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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.