I have three numbers x, a, and c, where both a and c are odd numbers. The number x is the output of the following function:

$$ x = a^b\!\!\!\!\!\!\!\mod{c} $$

I am attempting to determine whether the input exponent, b, was an odd or even number based on the knowledge of the three values, a, c, and x. Is there a way to deduce the parity of the exponent b using this information?

  • 1
    $\begingroup$ Hint: consider adding in the Q your thoughts about the Jacobi symbol $\left(\frac a c\right)$. $\endgroup$
    – fgrieu
    Oct 27, 2023 at 5:56
  • $\begingroup$ And note that, parity doesn't help to solve DLog. It is just a leak as in DH $\endgroup$
    – kelalaka
    Oct 27, 2023 at 6:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.