我想通过阅读CLR算法书来学习RSA密码学的数论。我在看练习31.2-5，它声称1 + log Φ（b/gcd（a，b））的界限。Euclid的GCD算法的运行时间？
完整的问题是：
如果A> B> = 0，表明调用EUCLID(a,b)使得至多1 +登录 Φ b递归调用。改进这个绑定到1 + log Φ（b/gcd（a，b））。
有谁知道如何显示这个？已经有几个其他的问题和答案在这个网站上的欧几里得算法，但没有一个人似乎有这个确切的答案。
这是我如何解决了第一部分。我仍在处理第二个
我们知道Euclid算法的运行时间是涉及的步骤数（本书的pg）的函数。设k是所需递归步骤的数量。 因此B> = F K + 1> =φK -1 B> =φK -1 以日志以得到k，我们有 登录φB> = k-1个 1 +φ登录B> = K 因此，运行时间为O（1 +φ登录b）
表明，如果Euclid(a,b)需要超过N步骤，然后 a>=F(n+1)和b>=F(n)，其中F(i)是i个斐波那契数 。
这可以通过Induction轻松完成。
证明≥ φ N-1，再由感应 。
使用步骤1和2的结果，我们具有B- ≥≥ φ N-1
以对数两侧， 日志 φ b ≥ N-1。
因此证明，正≤ 1 + 日志 φ b
第二部分平凡如下。
EUCLID(ka,kb)中的递归调用次数与EUCLID(a,b)中的递归调用次数相同，其中k是某个整数。 （b/gcd（a，b））。因此，该界限被改进为1 + log φ（b/gcd（a，b））。
您是否遇到第一部分或第二部分任务的问题？ – 2012-01-30 07:53:07
此外，欧几里德算法是那个 - 与除法和余数或减法？ – 2012-01-30 07:56:10
如果内存服务，Knuth（第2卷）对Euclid的GCD算法的复杂性有相当广泛的公开。 – 2012-01-30 07:56:32