Stein 算法

Stein算法
术语名称	Stein算法
英语名称	Stein's algorithm
别名	binary Euclidean algorithm, binary GCD algorithm

本条目没有一致可信的中文译名。

Stein算法(Stein's algorithm)，是辗转相除法在进行大数运算时的一种工程实现。

主要思想是由于大数的高精度带余除法是一个复杂度较高的计算，约去只在一个操作数中含有的质因数。由于硬件上用移位代替除法是常见且高效的手段，且容易判定是否整除，通常的优化中仅对 2 进行处理，单步内也用减法代替辗转相除单步的带余除法转化成带 2 的，因此也称为二进制最大公因数算法。

算法

原理

[math]\displaystyle{ \operatorname{gcd}(a, b) = \begin{cases} 2 \operatorname{gcd}\left(\frac{a}{2}, \frac{b}{2}\right) &, 2 \mid a, 2 \mid b \\ \operatorname{gcd}\left(\frac{a}{2}, b\right) &, 2 \mid a, 2 \not\mid b \\ \operatorname{gcd}\left(a, \frac{b}{2}\right) &, 2 \not\mid a, 2 \mid b \\ \operatorname{gcd}\left(a, a - b\right) &, 2 \not\mid a, 2 \not\mid b \end{cases} }[/math]

伪代码

过程 Stein算法
别名 steins_algorithm
参数 a, b : 整数 // 被求最大公因数的两个数
返回 : 自然数 // 最大公因数

令 r ← 1

循环
当 b ≠ 0 时
执行
    如果 2 | a 且 2 | b 那么
        令 a ← a / 2, b ← b / 2, r ← 2 r
    如果 2 | a 且 非 2 | b 那么
        令 a ← a / 2
    如果 非 2 | a 且 2 | b 那么
        令 b ← b / 2
    如果 非 2 | a 且 非 2 | b 那么
        令 b ← b - a
继续循环

令 r ← r a

返回 r

实现中，判断整除 2 使用按位与运算实现，除以 2 使用右移运算， r 也处理成左移运算，此外只有减法运算，和普通的运算相同。

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解