페르마의 소정리 , 확장 유클리드

페르마의 소정리

https://www.youtube.com/watch?v=uJAoaIeOXJM

 

 

 

 

 

확장 유클리드 

 

Ax + By = GCD(A,B) 가 있을때 만족하는 정수 x, y를 찾는 방법

 

방법 두가지 있음.

 

while 반복문을 이용한 방법.

 

    static void Uclede(long a, long b) {
        // Ax + By = 1 만족하는거 찾기
        long s[] = new long[2];
        long t[] = new long[2];
        s[0] = 1; t[0] =0;
        s[1] = 0; t[1] = 1;
        
        while(a %b != 0) {
            long ss = s[0] - (a/b)*s[1];
            long tt = t[0] - (a/b)*t[1];
            
            s[0] = s[1];
            t[0] = t[1];
            
            s[1] = ss;
            t[1] = tt;
            
            long tmp = b;
            b = a%b;
            a = tmp;
            
        }
    }

 

재귀적인 방법

    public static void euclidean(long B, long p){
        if(B%p>0){
            euclidean(p, B%p);
            temp = y;
            y = x - (B/p)*y;
            x = temp;
        }else{
            x = 0;
            y = 1;
            gcd = p;
        }
    }

 

 

s t 방법은 간단하다. 재귀적인 방법은 눈으로 쫒아가기힘들다 . 

실제로 확장유클리드로 최대공약수를 구하는것을 따라가면 된다.