### Binary egcd的正确性分析
[
]
大家如果阅读这个算法有问题，应该大多都出现在repeat里面的那两个while，特别是s和t不能同时被2整除的时候。都被2整除，大家应该能懂。

要理解这里，关键点还是我常强调的，别想太多，动笔算一算！

其次，大家有没有注意到那两个变量$a$和$b$在整个算法过程中都不变？这里就是我CINTA书里面强调的：$a$和$b$只是占位符，并不直接参与计算。那这里为什么出现了$a$和$b$？

说到这里，我们回想一下egcd在做什么？一直在保持 $as + bt = r$这一类型等式的成立。所以，$a$和$b$不变。现在$r$要除2，等式的左边要干啥？保持平衡啊！怎么才平衡，凑数！比如：
$$(as + bt)/2 = r/2$$
但是，$s$或$t$不能同时被2整除时，失败！
于是，想到(怎么想到的，算法里面不是这样做的吗？哈哈哈...)
$$(as + bt)/2 + ab/2 - ab/2 = r/2$$
变形得到
$$ a (s + b)/2 + b(t - a)/2 = r/2$$

问题是，你怎么确保$(s + b)$和$(t - a)$一定被2整除？
这里其实我也没想到更好的说明办法，那就分情况讨论嘛。
1、a和b同为奇数时；因为r为偶数，所以，s和t必须同为偶数或者奇数。可得！
2、a为奇数，b为偶数时；因为r为偶数，所以，这里我偷个懒，大家自己分析。

其他都比较容易。但是复杂性分析还是不容易的。有同学说，与gcd算法一样，其实不一样。为什么？注意那个repeat主循环，每次迭代r和r'只是做一次减法，注意，这里真是减法，不是gcd里面的mod运算。所以gcd分析里面每一次减半的结论其实是没有了！怎么办呢？