안녕하십니까 코딩 파인애플입니다
유클리드 알고리즘
유클리드 호제법...두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 알고리즘입니다
암호학에서의 유클리드 호제법은 RSA 암호같은 공개키 암호 시스템에서 키와 복호화할 때 필요한 역원을 계산하는 확장 유클리드 알고리즘의 바탕이 됩니다
최대공약수 (GCD) 는 두 양의 정수를 나누는 가장 큰 수 입니다
만일 gcd(a,b) = 1 일 경우 a와 b는 서로소이라 일컫습니다
참고로 a,b가 서로 다른 두 소수일 경우, 항상 서로소가 성립됩니다
이를 파이썬 코드로 구현하면 다음과 같습니다
def gcd(a,b):
while b:
a, b = b, a % b
return a
a, b = map(int,input().split())
print(gcd(a,b))
확장 유클리드 알고리즘
얘는 그냥 유클리드 알고리즘에서 조금 더 복잡해진 친구입니다
그냥 유클리드 알고리즘일 경우 큰 수를 작은 수로 나누고, 나머지로 계속 나누기를 반복합니다
67 // 59 = 1... 8
59 // 8 = 7... 3
8 // 3 = 2... 2
3 // 2 = 1... 1
2 // 1 = 2... 0 여기까지 나머지가 0이 되기 직전의 나머지가 (1) 이 gcd입니다.
하지만 다음과 같은 식에서 1이 되려면 어떻게 해야할까요 59 × u + 67 × v = 1
그러기에 확장 유클리드 알고리즘의 경우 위 연산을 역순으로 계산합니다
나눗셈 식을 나머지 = 큰 수 - 몫 * 작은 수 형태로 다시 써올라가 아래부터 위로 대입합니다
이를 반복하면 다음과 같이 됩니다
3 // 2 = 1... 1 => 1 = 3 - 1 * 2
8 // 3 = 2... 2 => 2 = 8 - 2 * 3
59 // 8 = 7... 3 => 3 = 59 - 7 * 8
67 // 59 = 1... 8 => 8 = 67 - 1 * 59이어서 나머지 = 위의 식에 하나씩 대입합니다 (나머지 값인 2,3,8 순서로 대입)
1 = 3 − 1 * (8 − 2 * 3) = 3 * 3 − 1 × 8
1 = 3 * (59 - 7 * 8) - 1 * 8 = 3 * 59 - 22 * 8
1 = 3 * 59 - 22 * (67 - 1 * 59) = 25 * 59 - 22 * 67
= 59 × u + 67 × v = 1 일 때, 59 * 25 + 67 * (−22) = 1 이므로
= u = 25, v = -22이를 파이썬 코드로 나타내면 다음과 같습니다
def extended_gcd(a, b):
old_r, r = a, b
old_u, u = 1, 0
old_v, v = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q*r
old_u, u = u, old_u - q*u
old_v, v = v, old_v - q*v
return old_r, old_u, old_v
a, b = map(int,input().split())
g, u, v = extended_gcd(a, b)
print(g, u, v)(사실 저도 좀 이해가 안됩니다) (유클리드 해병)
모듈러 연산
모듈러 연산은 그냥 새로운 연산자 하나 배운다는 셈 치면 쉽습니다
단순 어떤 숫자를 다른 숫자로 나눈 나머지를 구하는 연산이기 때문입니다
주로 mod를 써서 나타내며 컴퓨터에서는 '%' 를 통해 나타냅니다
print( 12 % 5 ) # 2
print( 43 % 3 ) # 1
print( 27 % 8 ) # 3하지만 만일 mod p 일 경우 p가 소수라면 어떻게 될까요
페르마의 소정리
거듭제곱을 나머지 연산이랑 같이 쓸 때 생기는 재밌는 규칙입니다
p가 소수이고, a가 p의 배수가 아니라면 -> a^p-1 ≡ 1 (mod p)
항상 이 식이 성립됩니다
이를 조금 응용하면 다음과 같은 재밌는 식이 나오기도 합니다
3^17 % 17
= 3^16 ≡ 1 * 3 ≡ 3 (페르마의 소정리에 의하여)
과 같이 응용이 가능합니다
p가 소수일 때, 집합 {1, 2, 3, ..., p-1}의 모든 원소에 어떤 수 a(단, a는 p의 배수 아님)를 곱하고 mod p를 취하면, 그 결과들은 순서만 원래 집합 {1, 2, ..., p-1}과 완전히 똑같은 원소들이 나오기 때문에 페르마의 소정리가 성립되게 됩니다.
이상으로 글을 마치겠습니다 감사합니다
+추신 : 여러분이 좋아하시는 버튜버 짤로 도배해봤는데 뭐...평소에 아는 짤만 싸지르다가 버튜버를 거의 몰라갖고 그냥 좀 엉망진창이 된 느낌이라 썩 유쾌하진 않습니다.
