[암호수학] Euclidean Algorithm 구현

Euclidean Algorithm

(유클리드 알고리즘)

GCD(최대공약수)

를 구하기 위한 알고리즘으로 위의 규칙을 바탕으로 

이러한 식을 도출해 증명 할 수 있다.

자바에 익숙해져야 할 것 같아서 자바로 코딩 해 보았다.

package 암호수학;
import java.util.*;
 
public class EuclideanAlgorithm {
    public void cal(int a, int b){
        int[] q = new int[50];
        int[] r = new int[50];
        int i = 0; int cnt = 0; int gcd = 0;
        int[] s = new int[50];
        int[] t = new int[50];
        s[0]=1; s[1]=0; t[0]=0; t[1]=1;
        r[0] = a; r[1] = b;
        while(true){
            cnt+=1;
            q[i+1]= r[i]/r[i+1];
            r[i+2] = r[i]%r[i+1];
            if(i>=2){
                s[i]=s[i-2]-q[i-1]*s[i-1];
                t[i]=t[i-2]-q[i-1]*t[i-1];
            }
            if(r[i+2]==0){
                gcd = r[i+1];
                s[cnt]=s[cnt-2]-q[cnt-1]*s[cnt-1];
                t[cnt]=t[cnt-2]-q[cnt-1]*t[cnt-1];
                break;
            }
            i+=1;
        }
        for(i=0; i<cnt; i++){
            System.out.println(r[i]+" = "+r[i+1]+"*"+q[i+1]+"+"+r[i+2]+"       s= "+s[i+1]+"       t= "+t[i+1]);
        }
        System.out.println("gcd =  "+gcd+" => "+s[cnt]+"*"+r[0]+" + "+t[cnt]+"*"+r[1]);
    }
    
    public static void main(String[] args) {
        int a,b;
        EuclideanAlgorithm Al = new EuclideanAlgorithm();
        Scanner scan = new Scanner(System.in);
        System.out.print("a, b = ? ");
        a = scan.nextInt();
        b = scan.nextInt();
        Al.cal(a, b);    
    }
}

(252, 198)

(9274, 4853)

완성