Given a number set of integers $\mathbb{Z}$, how do I find the inverse of a given number?

I am trying to test an algorithm to extract the $k$ and $x$ values from the Elgamal Signature algorithm given that $k$ is repeated.

What I have is $k$ congruent to $(m_1 - m_2)\times(s_1 - s_2)^{-1} \mod p - 1$ given $k$ is used twice.

I am not sure how to calculate the mod inverse though? _ Is the above formula the same thing as $((m_1 - m_2) \mod p -1 \times (s_1 - s_2)^{-1} \mod p -1) \mod p -1$

I am not sure if it is any different since I am doing a mod inverse.

PS. I am a programmer, not a mathematician so please elaborate.

  • 2
    $\begingroup$ Use the Extended Euclidean Algorithm, e.g. see here $\endgroup$ – Bill Dubuque Nov 19 '18 at 20:36
  • $\begingroup$ I know how to find a mod inverse. But if I have a number A*B^-1 mod p-1 is that equivalent to A mod p-1 * B mod p-1 mod p-1. That is what I found online but I wasn't sure. $\endgroup$ – User Nov 19 '18 at 20:39
  • $\begingroup$ $ab$ is invertible $\iff a,b$ are invertible $\iff a,b\,$ are coprime to the modulus. When so we have $(ab)^{-1}\equiv b^{-1}a^{-1}\,$ by $\ b^{-1}a^{-1} (ab) \equiv b^{-1}(a^{-1}a)b\equiv b^{-1}b \equiv 1\ $ (inverses are always unique) $\endgroup$ – Bill Dubuque Nov 19 '18 at 20:58
  • $\begingroup$ So what if I have a number * an inverse mod p -1. How would I break that down? $\endgroup$ – User Nov 19 '18 at 21:01
  • $\begingroup$ Calculate the inverse then modular_multiply the two as you would any pair of (modular) integers - using the mod prodcut rule $\endgroup$ – Bill Dubuque Nov 19 '18 at 21:05

Yes, the two formulas you wrote in the question give the same output.

More generally, as Bill Dubuque points out in the comments, you can usually just take mods at each step, instead of doing the whole computation and then modding at the end. However, exponentiation is a notable exception; you can reduce the base but generally not the exponent $$ a^k \bmod n \quad=\quad (a\bmod n)^k \bmod n \qquad\neq\qquad (a\bmod n)^{(k \bmod n)}.$$

  • $\begingroup$ This answer exists primarily to remove this question from the Unanswered list; please upvote (or give Best Answer) to complete the process. $\endgroup$ – aleph_two Dec 22 '18 at 5:06

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.