0
$\begingroup$

Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean Algorithm to find the multiplicative inverse of the element 254 in this field.

$\endgroup$
0
2
$\begingroup$

For such small numbers, brute force search will do: by definition $a^{-1}\bmod p$ is the integer $x$ in $[0,p)$ with $a\,x\bmod p=1$. The desired $x$ can be found by trial and error. This requires less than $p$ additions, tests, and subtractions, noting we can move from one candidate $x$ to the next using that $((a\,(x+1))\bmod p)\,=\,((((a\,x)\bmod p)+x)\bmod p)$.


One of the most recommendable and fastest classical algorithms is the (half) extended Euclidean algorithm. In crypto, we sometime prefer that variant avoiding negatives. There also are binary variants. Essentially, these find unknown $x$ solving the Bézout identity $a\,x+p\,y=1$ for given $a$ and $p$, and some immaterial unknown $y$.


Yet another method uses $x\gets a^{p-2}\bmod p$. It's applicable when $p$ is prime and integer $a$ is not a multiple of $p$. It follows from Fermat's little theorem. This uses less than $2\log_2(p)$ modular multiplications, using binary modular expoentiation. The method is extensible to any group of known order.

$\endgroup$
2
  • $\begingroup$ Using brute force as suggested, with 254x ≡ 1 (mod 257) I arrived at 171. Is this correct? $\endgroup$
    – hollyjolly
    Mar 18 at 15:27
  • $\begingroup$ 254×171 = 257×169 + 1, thus the result is OK, congratulations. But I advise trying one of the extended Euclidean algorithms; it's much faster. $\endgroup$
    – fgrieu
    Mar 18 at 15:43

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.