cryptohack을 공부하면서 얻은 지식들을 정리하려고 한다.Greatest Common DIvisorGCD 즉 최대공약수에 대한 내용이다. 유클리드 호제법을 이용해서 두 정수의 최대공약수를 구하라고 한다. 이전에 유클리드 호제법을 다루었던 적이 있다.2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除nivr4y.tistory.comdef gcd(a, b): while b > 0: ..

문제중국인의 나머지 정리(CRT)를 알고 있는 사람이라면 바로 해당 정리를 이용해서 문제를 풀어야겠다는걸 알 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동nivr4y.tistory.comCRT는 주어진 법들이 서로소 관계일때만 적용되므로, 일반적인 CRT와는 약간 다르게 바꿔서 함수를 짜야 한다.풀이import sysinput = sys.stdin.readlinedef ext_euc(a, b): if b==0: return a, 1, 0 g, x, y = ext_euc(b, a..

알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동식을 만족하는 유일한 해를 구할 수 있게 해주는 강력한 정리이다.$$x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}$$합동식들의 $a \equiv b \mod m$의 형태에서, 모든 m들은 서로 서로소 관계여야 한다.또한 각 합동식에서 x의 계수가 1이 아닌 경우가 있는데, 그런 경우에는 확장된 유클리드 알고리즘(EEA)를 사용해서 곱셈 역원을 구해서 양변에 곱해준 후 CRT를 적용한다.중..

문제나의 첫 플레티넘 문제이다!! 이전 글에서 확장된 유클리드 알고리즘을 공부한것이 큰 도움이 되었다.2024.09.23 - [BOJ/이론] - Extended Euclidean Algorithm (확장된 유클리드 호제법) Extended Euclidean Algorithm (확장된 유클리드 호제법)확장된 유클리드 호제법이란?2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기  유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호nivr4y.tistory.com문제에서 요구하는 것을 식으로 만들어 보면 다음과 같다.$$ k \cdot x + c \cdot y \equiv 1 \mod c $$이는 확장된 유클리드 알고리즘으로 ..