1
$\begingroup$

Trying out different implementations of the extended GCD, i found out that all of them return the same linear combination factors for $egcd(a,b)$ and $egcd(b,a)$. For example (with this algorithm) I get:

$ egcd(257, 123) = [1,56,-117] $ and $ egcd(123, 257) = [1,-117,56] $

Which is correct, because:

$ egcd(257, 123) = 1 = 257 * (56) + 123 * (-117) $ and $ egcd(123, 257) = 1 = 123 * (-117) + 257 * (56) $

The two numbers are just switched, so their linear combination factors are switched as well.

So when I tried the binary version of the ecgd, i expected the same results. But using this algorithm (chapter 14.4.3) i now get two different linear combinations:

$ egcdBin(257, 123) = [1,56,-117] $ and $ egcdBin(123, 257) = [1,140,-67] $

Of course, both are correct again:

$ egcdBin(257, 123) = 1 = 257 * (56) + 123 * (-117) $ and $ egcdBin(123, 257) = 1 = 123 * (140) + 257 * (-67) $

For different $(a,b)$-pairs I found that sometimes the linear combination of $egcd$ and $egcdBin$ do not match (like above) and sometimes they do:

$ egcdBin(251, 123) = 1 = 251 * (-49) + 123 * (100) $ and $ egcdBin(123, 251) = 1 = 123 * (100) + 251 * (-49) $

which is the same as with the "normal" egcd.

So my question is: Why does the binary ecgd not give the same linear combination as the non-binary version?

Or better: Why does it sometimes produce the same combination and sometimes a different one?

(I know that there are infinite linear combinations possible, I'm just confused that with the binary version you sometimes get different ones.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.