C++で拡張ユークリッド互除法

こんにちは、Sayahamittです。

だいぶご無沙汰してしまいましたが久々のブログ更新です。

2つの整数の最大公約数を高速に求められるユークリッド互除法をなんとなく実装してみました。

意味は…ないです…w

もしかしたらそのうち簡単なRSA暗号とかもやってみるかも。

テクニカルなコーディングはできないので、教科書に書いてあったアルゴリズムをそのままクラスとして実装しました。

#include <iostream>
#include <stdlib.h>

class euclidean{
private:
	int u[3];
	int v[3];
	int t[3];
	
public:
	euclidean(int a, int b){
	  int _u[]={1,a,0};
		int _v[]={0,b,1};

		std::copy(_u,_u+sizeof(_u),u);
		std::copy(_v,_v+sizeof(_v),v);
		
		proc();
	}
	~euclidean(){}

	int getGCD(){
		return u[1];
	}

	int getR1(){
		return u[0]; 
	}

	int getR2(){
		return u[2];
	}

private:
 	bool step(){
		if(v[1]!=0){
			int w = u[1]/v[1];
			
			for(int i=0; i<3; i++){
				t[i]=u[i]-v[i]*w;
				u[i]=v[i];
				v[i]=t[i];
			}
			return true;
		}
		return false;
	}

	void proc(){
		while(true){
			if(!step()){
				break;
			}
		}
	}
};

int main(int argc,char const* argv[]){
	if(argc != 3){
		std::cout<<"exe int1 int2"<<std::endl;
		return 0;
	}
	int i = atoi(argv[1]);
	int j = atoi(argv[2]);
	
	euclidean a(i,j);
	std::cout<<a.getGCD()<<std::endl;
	
	return 0;
}

なんのヒネリもありません。

euclideanクラスのコンストラクタ引数に最大公約数を得たい2数を与えるとユークリッド互除法によって最大公約数を計算し、その値がgetGCD()メソッドで取得できます。

また、getR1(), getR2()メソッドで、元の2数をa,bとした時に

aR1 + bR2 = GCD(a,b)

となるR1とR2が得られます。

これを使うとRSA暗号の処理とかが書けるのでちょっと面白いかもと思って書いてみました。

ではでは～ ノシ