[セットトップ]2つの数の最大公約数
一、二つの数の最大公約数:1、ユークリッドアルゴリズム
ユークリッドアルゴリズムは、2つの整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.その計算原理は以下の定理に依存する:定理:gcd(a,b)=gcd(b,a mod b)は、aがa=kb+rとして表すことができ、r=a mod bはdがa,bの1つの公約数であると仮定し、d|a,d|bがあり、r=a−kbであるため、d|rは(b,a mod b)の公約数であると仮定し、d|b,d|rである.しかし、a=kb+rであるため、dも(a,b)の公約数であるため(a,b)と(b,a mod b)の公約数は同じであり、その最大公約数も必然的に等しい.ユークリッドアルゴリズムはこの原理に基づいて行われていることを証明し、そのアルゴリズムはC++言語で記述されている.
2、Steinアルゴリズムユークリッドアルゴリズムは2つの数の最大公約数を計算する伝統的なアルゴリズムであり、理論的にも効率的にも優れている.しかし、致命的な欠陥があり、この欠陥は大きな素数の時にしか現れない.現在のハードウェアプラットフォームを考慮すると、一般的に整数は最大64ビットであり、このような整数に対して、2つの数の間のモジュールを計算するのは簡単である.ワード長が32ビットのプラットフォームでは、32ビットを超えない2つの整数を計算するモードは、1つの命令周期しか必要ありませんが、64ビット以下の整数モードを計算するのは、いくつかの周期にすぎません.しかし、より大きな素数に対しては、このような計算プロセスはユーザーによって設計されなければならず、64ビットを超える2つの整数のモジュールを計算するために、ユーザーは複数の数除算手算プロセスに類似した試商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費している.現代の暗号アルゴリズムでは,128ビット以上の素数の計算が要求される場合が多く,このようなプログラムの設計は除算と型取りを捨てることを切に望んでいる.SteinアルゴリズムはJ.Stein 1961年に提案され,この方法も2つの数を計算する最大公約数である.ユークリッドアルゴリズムとは異なり,Steinアルゴリズムは整数のシフトと加減法のみであり,これはプログラム設計者にとって福音である.Steinアルゴリズムの正しさを説明するためには、まず、gcd(a,a)=a、すなわち、1つの数とそれ自身の公約数は、その自身のgcd(ka,kb)=k gcd(a,b)、すなわち最大公約数演算と倍乗演算とを交換することができ、特に、k=2の場合、2つの偶数の最大公約数が必ず2でC+/javaを除去して実現できることを説明しなければならない.
二、複数の数の最大公約数:(python実装:配列aの中で最小、2から最小のループを取り出し、その中で最大の配列中のすべての数で割り切れるその数を探し出す、最大公約数)def gcd(a):a.sort()min=a[0]result=1 for i in range(2,min+1): flag = True for j in a: if j % i != 0: flag = False if flag == True: result = i return result
ユークリッドアルゴリズムは、2つの整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.その計算原理は以下の定理に依存する:定理:gcd(a,b)=gcd(b,a mod b)は、aがa=kb+rとして表すことができ、r=a mod bはdがa,bの1つの公約数であると仮定し、d|a,d|bがあり、r=a−kbであるため、d|rは(b,a mod b)の公約数であると仮定し、d|b,d|rである.しかし、a=kb+rであるため、dも(a,b)の公約数であるため(a,b)と(b,a mod b)の公約数は同じであり、その最大公約数も必然的に等しい.ユークリッドアルゴリズムはこの原理に基づいて行われていることを証明し、そのアルゴリズムはC++言語で記述されている.
void swap(int & a, int & b){
int c = a;
a = b;
b = c;
}
int gcd(int a,int b){
if(0 == a ){
return b;
}
if( 0 == b){
return a;
}
if(a > b){
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b){
a = b;
b = c;
}
return b;
} 2、Steinアルゴリズムユークリッドアルゴリズムは2つの数の最大公約数を計算する伝統的なアルゴリズムであり、理論的にも効率的にも優れている.しかし、致命的な欠陥があり、この欠陥は大きな素数の時にしか現れない.現在のハードウェアプラットフォームを考慮すると、一般的に整数は最大64ビットであり、このような整数に対して、2つの数の間のモジュールを計算するのは簡単である.ワード長が32ビットのプラットフォームでは、32ビットを超えない2つの整数を計算するモードは、1つの命令周期しか必要ありませんが、64ビット以下の整数モードを計算するのは、いくつかの周期にすぎません.しかし、より大きな素数に対しては、このような計算プロセスはユーザーによって設計されなければならず、64ビットを超える2つの整数のモジュールを計算するために、ユーザーは複数の数除算手算プロセスに類似した試商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費している.現代の暗号アルゴリズムでは,128ビット以上の素数の計算が要求される場合が多く,このようなプログラムの設計は除算と型取りを捨てることを切に望んでいる.SteinアルゴリズムはJ.Stein 1961年に提案され,この方法も2つの数を計算する最大公約数である.ユークリッドアルゴリズムとは異なり,Steinアルゴリズムは整数のシフトと加減法のみであり,これはプログラム設計者にとって福音である.Steinアルゴリズムの正しさを説明するためには、まず、gcd(a,a)=a、すなわち、1つの数とそれ自身の公約数は、その自身のgcd(ka,kb)=k gcd(a,b)、すなわち最大公約数演算と倍乗演算とを交換することができ、特に、k=2の場合、2つの偶数の最大公約数が必ず2でC+/javaを除去して実現できることを説明しなければならない.
// c++/java stein
int gcd(int a,int b){
if(a<b){//arrange so that a>b
int temp = a;
a = b;
b=temp;
}
if(0==b)//the base case
return a;
if(a%2==0 && b%2 ==0)//a and b are even
return 2*gcd(a/2,b/2);
if ( a%2 == 0)// only a is even
return gcd(a/2,b);
if ( b%2==0 )// only b is even
return gcd(a,b/2);
return gcd((a+b)/2,(a-b)/2);// a and b are odd
} 二、複数の数の最大公約数:(python実装:配列aの中で最小、2から最小のループを取り出し、その中で最大の配列中のすべての数で割り切れるその数を探し出す、最大公約数)def gcd(a):a.sort()min=a[0]result=1 for i in range(2,min+1): flag = True for j in a: if j % i != 0: flag = False if flag == True: result = i return result