Python最大公約数のユークリッドアルゴリズムとSteinアルゴリズム

greatest common divisor(最大公約数)
1.ユークリッドアルゴリズム
ユークリッドアルゴリズムは、2つの正の整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.
その計算原理は以下の定理に依存する.
2つの整数の最大公約数は、その中の小さい数と2つの数を除いた残りの数の最大公約数に等しい.
最大公約数(greatest common divisor)はgcdと略す.
gcd(a,b)=gcd(b,a mod b)(a>b、r=a mod b、rが0でないとしてもよい)を転がして除去し、最終結果を得た.
 
証明:
aはa=kb+r(a,b,k,rともに正の整数であり、r
dがa,bの公約数であると仮定し,d|a,d|bと表記し,すなわちa,bはいずれもdで除去できる.
一方、r=a-kbは、両側をdで同時に除算し、r/d=a/d-kb/d=mであり、等式左側からmは整数であることが分かるため、d|r
従ってdもb,a mod bの公約数である
従って(a,b)と(b,a mod b)の公約数は同じであり,その最大公約数も必然的に等しいことが証明された.
 
コード実装:
C++:

int gcd(int a，int b){
    if (a < b)
        std::swap(a, b);
    return b == 0 ? a : gcd(b, a % b);        
}

 
Python:
関数内再帰

1 def gcd(a, b):
2     if a < b:
3         a, b = b, a
4     while b != 0:
5         a,b = b,a%b
6     return a

関数の再帰:

1 def gcd(a, b):
2     if b == 0:
3         return a
4     return gcd(b, a % b)

2.Steinアルゴリズム:
ユークリッドアルゴリズムは2つの数の最大公約数を計算する従来のアルゴリズムであり,理論的にも実際の効率的にも優れている.しかし、致命的な欠陥があり、この欠陥は素数が小さいときには一般的に感じられず、大きな素数のときにしか現れない.
一般的に実際の応用では64ビットを超える整数は少ない(もちろん現在は128ビットが許可されている)が、このような整数については、2つの数の間のモジュールを計算するのは簡単である.ワード長が32ビットのプラットフォームでは、32ビットを超えない2つの整数を計算するモードは、1つの命令周期しか必要ありませんが、64ビット以下の整数モードを計算するのは、いくつかの周期にすぎません.しかし、より大きな素数に対しては、このような計算プロセスはユーザーによって設計されなければならず、64ビットを超える2つの整数のモジュールを計算するために、ユーザーは複数の数除算手算プロセスに類似した試商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費している.現代の暗号アルゴリズムでは,128ビット以上の素数の計算が要求される場合が多く,このようなプログラムの設計は除算と型取りを捨てることを切に望んでいる.
 
証明:
J.Stein 1961年に提案されたSteinアルゴリズムはユークリッドアルゴリズムにおけるこの欠陥をよく解決した.Steinアルゴリズムは整数のシフトと加減法しかなく、Steinアルゴリズムの正確性を説明するために、まず以下の結論に注意しなければならない.
gcd(a,a)=a、すなわち、1つの数とそれ自身の公約数は依然としてそれ自身である.
gcd(ka,kb)=k gcd(a,b)、すなわち最大公約数演算と倍乗演算を交換することができる.特に、k=2の場合、2つの偶数の最大公約数は必ず2で割り切れることを示す.
kとbが互いに質量数である場合、gcd(ka,b)=gcd(a,b)、すなわち、2つの数のうちの1つだけを含む因子は最大公約数に影響しない.特に、k=2の場合、偶数と奇数の最大公約数を計算する場合、偶数を2で割ってもよい.
 
コード実装:
Python:

 1 def gcd_Stein(a, b):  
 2     if a < b:
 3         a, b = b, a
 4     if (0 == b):
 5         return a
 6     if a % 2 == 0 and b % 2 == 0:
 7         return 2 * gcd_Stein(a/2, b/2)
 8     if a % 2 == 0:
 9         return gcd_Stein(a / 2, b)
10     if b % 2 == 0:
11         return gcd_Stein(a, b / 2)
12     
13     return gcd_Stein((a + b) / 2, (a - b) / 2) 

 
 
 
 
転載先:https://www.cnblogs.com/Dragon5/p/6401596.html