Inverse of a number module 2**255 -19

Question

I don't understand this code to solve the inverse of a number:

b = 256; q = 2**255 - 19

def expmod(b,e,m): if e == 0: return 1 t = expmod(b,e/2,m)**2 % m if e & 1: t = (t*b) % m return t

def inv(x): return expmod(x,q-2,q)

Finally, If I want to put: $\frac{2}{3}$ I can to do this: aux=2*inv(3)

What does the variable e mean?

Could you explain me this code, please?

Thank you so much.

Answer 1

Presumably, the number $p:=2^{255}-19$ is prime. Then $x^{p-1}\equiv 1\pmod p$ for all $x\not\equiv 0\pmod p$ (Little Fermat). Hence we find $x^{-1}\bmod p$ by computing $x^{p-2}$. The function $\operatorname{expmod}(x,y,m)$ computes $x^y\bmod m$ by using these observations:

• $x^0\equiv 1\pmod m$
• $x^{2k}\equiv x^k\cdot x^k\pmod m$
• $x^{2k+1}\equiv x^{2k}\cdot x\pmod m$.