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.
Answer
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)}.$$
No comments:
Post a Comment