# Finding Multiplicative Inverse In Field

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.

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.