1
$\begingroup$

I am trying to find $d$ given $e$ and $\varphi(n)$. I found a solution online but I don't really understand why it works.

sage: bezout = xgcd(e, phi); bezout 
(1, 4460824882019967172592779313, -1667095708515377925087033035)

sage: d = Integer(mod(bezout[1], phi)) ; d
4460824882019967172592779313

sage: mod(d * e, phi)
1

Found an explanation of this online

ex + φ(n)y = gcd(e,φ(n))
           = 1
Re-arrange:
ex = -φ(n)y + 1

ex mod φ(n) = 1, so x = d

but I get why the second line of code is needed if $x=d$ then d = bezout[1].Why is there a mod by $\varphi(n)$ again to obtain $d$?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

This is about the XGCD implementation of Sagemath.

XGCD(a, b)
Return a triple (g,s,t) such that g=s⋅a+t⋅b=gcd(a,b).
g, s, t - such that g=s⋅a+t⋅b
Note There is no guarantee that the returned cofactors (s and t) are minimal.

Since the returned cofactors are not guaranteed to be minimal, it is the user's responsibility to reduce the value to be less than $\varphi(n)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.