Ask Your Question

Inverse of a number modulo 2**255 -19

asked 2018-09-24 19:26:43 +0200

ZacariasSatrustegui gravatar image

updated 2018-11-04 19:56:35 +0200

slelievre gravatar image

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.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2018-09-25 09:47:01 +0200

slelievre gravatar image

updated 2018-09-25 09:47:34 +0200

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$.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-09-24 19:26:43 +0200

Seen: 1,888 times

Last updated: Nov 04 '18