Skip to content

태그: 정수론

총 5개의 글이 있습니다.

정수론부터 RSA까지

RSA는 대표적인 비대칭 암호화 방식 중 하나이다. RSA의 기반이 되는 정수론 개념과 암호화 원리를 알아보자. 군 RSA를 이해하기 위해선 우선 군(group)이 무엇인지 알아야 한다. 오늘날 RSA를 비롯한 많은 암호화 방식이 군론을 기반으로 한다. 개념은 어렵지 않다. 군이란, 아래 규칙에 맞게 원소의 집합과 연산(덧셈, 곱셈)을 정의한 것이다. 닫힘: 집합 안의 두 원소를 연산했을 때, 그 결과가 군 안에 속해야 한다. 결합법칙: 여러 원소에 대한 연산을 임의의 순서로 수행할 수 있다. (e.g. (a+b)+c = a+(b+c)) 항등원: 특정 원소와 항등원을 연산한 결과가 그 원소 자신이 되어야 한다. (e.g. a+0=a, 이 경우 항등원 0이 군 내에 존재함) 역원: 두 원소를 연산한 결과가

오일러 정리

오일러 피 함수 오일러 피 함수는 1~n 범위 중 n과 서로소인 숫자의 갯수를 구하는 함수이다. 1부터 6까지의 정수 중 6과 서로소인 수는 1, 5 두 개이므로 φ(6) = 2이다. 1부터 10까지의 정수는 모두 11과 서로소이고, 11은 자신과 서로소가 아니므로, φ(11) = 10이다. 1은 자기 자신과 서로소이므로, φ(1) = 1이다. 오일러 정리 오일러 정리는, 정수 a 및 양의 정수 n이 주어졌고 a와 n이 서로소일 때 아래 식이 성립한다는 내용이다. a^φ(n) ≡ 1 (mod n) 페르마 소정리와 유사한 논리로 증명할 수 있다. n과 서로소인 1부터 n까지의 정수를 r₁, r₂, …, r_φ(n)이라 하자. 이들의 개수가 바로 φ(n)개이다. a가 n과 서로소일 때, ar₁, ar

유클리드 호제법

유클리드 호제법 두 정수 a를 b로 나눈 값을 아래처럼 표현하면 (a ≥ b) a = bq + r (단, 0 ≤ r &x3C; b) 다음 정리가 성립한다. (a, b) = (b, r) 즉, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질을 나머지가 0이 될 때까지 반복하면 마지막에 남는 0이 아닌 수가 gcd(a, b)이다. 예시 (1071, 1029)= (1029, 42)= (42, 21)= (21, 0)= 21 따라서 gcd(1071, 1029) = 21 증명 a,b ∈ Z 이고 a ≥ b 라 하자. 두 정수 a를 b로 나눈 값을 아래처럼 표현할 수 있다. a = bq + r, 0 ≤ r &x3C; b (a, b) = d 라고 하고, a = dα, b = dβ 라 해보

베주 항등식

ax + by = gcd(a, b)를 성립하는 x, y는 항상 존재한다. 집합 S = {ax + by 0 | x, y는 정수}를 가정했을 때 S는 공집합이 아니므로, y=0, x=1이면: a×1 + b×0 = a a가 양수면 그대로, 음수면 |a| (x=-1로 조정) 따라서 S는 최소한 하나의 원소를 가짐 S에 있는 가장 작은 원소를 d라고 불러볼 수 있다. a를 d로 나누면 몫 q와 나머지 r로 표현할 수 있을 것이다. a = dq + r (0 ≤ r &x3C; d) 여기서 만약 r이 0보다 크다면 r = a dq= a (as + bt)q= a(1-sq) + b(-tq) 이므로 r도 S의 원소라는 뜻인데, r &x3C; d이므로 d가 최소원소라는 것에 모순된다. 따라서 r = 0이어야

페르마 소정리

소수 m, 임의의 수 a에 대해 아래 식이 성립한다. a^(m-1) = 1 (mod m) 이 식을 활용해 역원을 구할 수 있다. a^(m-1) = a*a^(m-2) = 1 (mod m)즉, a^(m-2)가 a의 역원 증명 a와 서로소인 소수 p에 대해 a, 2a, 3a, …, (p−1)a인 p−1개의 수를 p로 나눴을 때 나오는 나머지는 모두 다르다. 귀류법으로 증명된다. 0&x3C;i&x3C;j&x3C;p인 정수에서 ia와 ja의 나머지가 같다고 하면 ia != ja (mod p)ja ia = 0 (mod p) 위 식이 성립하기 위해선, (j-i)a가 p로 나눠떨어져야 한다. a는 p와 서로소이므로 j-i가 p로 나눠떨어져야 한다. 하지만 조건에 따라 i-j가 p보다 클 수 없다 (i-j &x3C;