05. 모듈러 산술(Modular Arithmetic), 중국인의 나머지 정리 모듈러 산술(Modular Arithmetic) * 암호학에서 굉장히 많이 다뤄지는 부분이므로 잘 이해해야 한다. 모듈러 산술은 나머지 연산을 말한다. 실생활에서 시계의 경우가 대표적인데, 시계가 시간을 표시하는 것은 0에서 부터 11시까지만이다. 12시가 되면 다시 0이되고 13은 1, 14는 2가 되면서 11까지.. 알고리즘/정수론 2014.08.29
04. 최대공약수, 최소공배수 최대 공약수(GCD: Greatest Common Divisor) 두 정수의 공약수중에서 가장 큰 수를 최대공약수라고 하고, 두 정수 m,n에 대한 최대공약수를 gcd(m,n)이라고 표현한다. 최대공약수는 암호학에서 꽤 사용되는 분야이다. 주로, 어떤 수 m,n이 있을 때, 이 두 수가 서로 소인지(공통된 약수가 있는지 없는지.. 알고리즘/정수론 2014.08.28
03. 소수 소수(Prime Number) 소수는, 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수 0.1 0.2는 /소수/로 발음하고, Prime Number인 소수는 /소쑤/로 발음한다. (예전에는 Prime Number는 '솟수'로 썼었는데, 1998년 맞춤법 개정에서 6개의 한자어인 곳간, 찻간, 퇸간, 셋방, 숫자, 횟수를 제외하고는 사이시옷을 쓸.. 알고리즘/정수론 2014.08.27
02.정수, 정수의 나누어짐 정수란? 정수는 자연수(1,2,3...)와 이들의 음수(-1,-2,-3...), 그리고 0(zero)으로 이루어진 수 체계이다. 정수는 덧셈, 뺄셈, 곱셈에 대해 닫혀있고, 나눗셈에 대해서는 닫혀있지 않다. 정수가 어떤 것인지는 그리 중요하지도 않고 헷갈리지도 않을 것이다. 하나 둘 셋...이렇게 셀 수 있는 수이고.. 알고리즘/정수론 2014.08.27
01.정수론이란? 그리고 왜 공부해야 하는가? 정수론은 영어로 Number Theory라 하고, 정수의 성질을 다루는 수학의 한 분야이다. 현대 암호학은 주로 정수론에서 다루어지는 수학적인 성질을 바탕으로하기에, 암호화 알고리즘을 이해하고 구현하기 위해서는 정수론에 대한 공부가 필요하다. 예를들어, 대표적인 비대칭키 알고리즘인 RSA.. 알고리즘/정수론 2014.08.27