[암호수학1] 유클리드 알고리즘 이론~코딩

유클리드 알고리즘(Euclidean algorithm)이란?

유클리드 알고리즘(유클리드 호제법)은 자연수 2개의 최대공약수를 구하는 하나의 알고리즘이다.

유클리드 알고리즘을 쓰면, a와 b의 공약수들을 나열하지 않고, 연산만으로 a와 b의 최대공약수를 구할 수 있다.

---

유클리드 알고리즘 계산법

gcd(a,b)=a와 b의 최대공약수
최대공약수(Greatest Common Divisor, GCD)

유클리드 알고리즘

유클리드 알고리즘 예시

유클리드 알고리즘 코딩 [파이썬]

def gcd(m,n):
    if m<n:
        m,n=n,m
    if n==0:
        return m
    if m%n==0:
        return n
    
    else:
        return gcd(n,m%n)

print(gcd(2740, 1760)) #출력:20

---

유클리드 확장 알고리즘

두 정수 a와 b가 주어졌을 때, gcd(a,b)를 계산할 수 있을 뿐만 아니라,

s*a+s*b=gcd(a,b)를 만족하는 s와 t를 구할 수 있다.

유클리드 확장 알고리즘

유클리드 확장 알고리즘 예시

유클리드 확장 알고리즘 코딩 [파이썬]

def UCL(r1,r2,s1=1, s2=0, t1=0, t2=1):
    while r2>0:
        q=r1//r2
        print('q={}'.format(q))
        
        r=r1-r2*q
        print('r1={}, r2={}, r={}'.format(r1, r2, r))

        s=s1-s2*q
        s1=s2; s2=s
        print('s1={}, s2={}, s={}'.format(s1, s2, s))

        t=t1-t2*q
        t1=t2; t2=t
        print('t1={}, t2={}, t={}\n'.format(t1, t2, t))

        r1=r2; r2=r

        if r2==0:
            return r1, s1, t1
    
    
a=161
b=28
gcd1,s,t=UCL(a,b)

print("a={}, b={}.\n".format(a,b)) 
print("a*s+b*t=gcd(a,b)\n{}*{}+{}*{}={}".format(a,s,b,t,gcd1))

실행 결과

---

그런데 만약 10*x+5*y=30처럼 (x,y)의 해가 많다면??

[암호수학1] 유클리드 알고리즘 + 디오판투스 방정식 (특수해와 일반해 구하기)

https://sh1256.tistory.com/91?category=992139

[암호수학1] 유클리드 알고리즘 + 디오판투스 방정식 (특수해와 일반해 구하기)