Inverse of a number modulo 2**255 -19

savecancel

Since $q$ is a prime here, $\mathbb{Z}/q$ is a field, usually denoted by $F_q$.

All its nonzero elements are invertible, and form a group under multiplication. This group is called the multiplicative group of this field, or its group of units.

This group has order $q-1$ (since it contains all nonzero elements of $F_q$), so every nonzero element $x$ in $F_q$ satisfies $x^{q-1} = 1$, which can be written as $x^{q-2} \cdot x = 1$, so we get that for any nonzero $x$ in $F_q$, $x^{q-2}$ is the multiplicative inverse of $x$.

The function expmod(b, e, m) (for "exponentiation modulo") computes $b^e$ modulo $m$. Here the arguments of this function are named to reflect their role (basis, exponent, modulus).

Finally, the function inv just computes $x^{q-2}$ modulo $q$.