ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 25 Sep 2018 09:47:01 +0200Inverse of a number modulo 2**255 -19https://ask.sagemath.org/question/43738/inverse-of-a-number-modulo-2255-19/ 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.Mon, 24 Sep 2018 19:26:43 +0200https://ask.sagemath.org/question/43738/inverse-of-a-number-modulo-2255-19/Answer by slelievre for <p>I don't understand this code to solve the inverse of a number:</p>
<pre><code>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)`
</code></pre>
<p>Finally, If I want to put: $\frac{2}{3}$ I can to do this: <code>aux=2*inv(3)</code></p>
<p>What does the variable <code>e</code> mean?</p>
<p>Could you explain me this code, please?</p>
<p>Thank you so much.</p>
https://ask.sagemath.org/question/43738/inverse-of-a-number-modulo-2255-19/?answer=43749#post-id-43749Since $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$.Tue, 25 Sep 2018 09:47:01 +0200https://ask.sagemath.org/question/43738/inverse-of-a-number-modulo-2255-19/?answer=43749#post-id-43749