主题
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 贡献

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

半-GCD

引用为

Terr, David. “半-GCD。” 来自 MathWorld——Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/Half-GCD.html

主题分类