主題
Search

半-GCD

給定整數 a 和 b，它們各自接近 2n 位，a 和 b 的半-GCD 是一個 2×2 矩陣

[u v; u^' v^']

行列式等於 -1 或 1，使得 ua+vb=r 且 u^'a+v^'b=r^'，其中 r 和 r^' 各自的位數接近 n。

半-GCD 是透過執行大約一半的歐幾里得演算法來計算最大公約數 GCD(a,b) 而得到的。存在一種高效的演算法來計算兩個大數的半-GCD，當遞迴應用時，它可以比使用歐幾里得演算法更快地計算最大公約數。

參見

歐幾里得演算法, 最大公約數

此條目由 David Terr 貢獻

使用 探索

參考文獻

Aho, A. V.; Hopcroft, J. E.; 和 Ullmann, J. D. 資料結構與演算法. Reading, MA: Addison-Wesley, 1987.Sedjelmaci, S. M. “加速歐幾里得演算法。” 2004 年 ISAAC 海報演講，7 月 4-7 日，西班牙桑坦德坎塔布里亞大學。http://www.risc.uni-linz.ac.at/issac2004/poster-abstracts/abstract27.pdf.

在 中被引用

半-GCD

引用為

Terr, David. “半-GCD。” 來自 —— 資源，由 Eric W. Weisstein 建立。 https://mathworld.tw/Half-GCD.html

主題分類