我想通過閱讀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