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) 페르마 소정리와 유사한 논리로 증명할 수 있다. 1. n과 서로소인 1부터 n까지의 정수를 r₁, r₂, ..., r_φ(n)이라 하자. 이들의 개수가 바로 φ(n)개이다.

유클리드 호제법

유클리드 호제법 두 정수 a를 b로 나눈 값을 아래처럼 표현하면 (a ≥ b) a = bq + r (단, 0 ≤ r a와 b의 정수 계수 결합(integer linear combination)으로 표현 가능하다고도 표현한다. 단계별로 확인해 보면, 패턴이 반복적으로 유지된다. 첫 번째 단계 a = b·q₀ + r₀ 정리하면 r₀ = a b·q₀ r₀ = 1·a + (-q₀)·b 따라서 s₀ = 1, t₀ = -q₀ 두 번째 단계 b = r₀·q₁ + r₁ 정리하면 r₁ = b q₁·r₀ 위에서 r₀ = a b·q₀ 이므로 r₁ = b q₁(a b·

베주 항등식

`ax + by = gcd(a, b)`를 성립하는 x, y는 항상 존재한다. 1. 집합 `S = {ax + by 0 | x, y는 정수}`를 가정했을 때 S는 공집합이 아니므로, `y=0`, `x=1`이면: `a×1 + b×0 = a` a가 양수면 그대로, 음수면 |a| (x=-1로 조정) 따라서 S는 최소한 하나의 원소를 가짐 S에 있는 가장 작은 원소를 d라고 불러볼 수 있다. 2. a를 d로 나누면 몫 q와 나머지 r로 표현할 수 있을 것이다. a = dq + r (0 ≤ r 따라서 r = 0이어야 한다. 즉, a는 d로 나누어 떨어진다. 같은 방법으로 b도 d로 나누어 떨어지는 것을 알 수 있다.

페르마 소정리

소수 m, 임의의 수 a에 대해 아래 식이 성립한다. a^(m-1) = 1 (mod m) 이 식을 활용해 역원을 구할 수 있다. a^(m-1) = a*a^(m-2) = 1 (mod m) 즉, a^(m-2)가 a의 역원 증명 1. a와 서로소인 소수 p에 대해 a, 2a, 3a, ..., (p−1)a인 p−1개의 수를 p로 나눴을 때 나오는 나머지는 모두 다르다. 귀류법으로 증명된다. 0 [알고리즘 분류: 페르마의 소정리]( 여담: 알고리즘 문제에서 결과를 10^9+7로 나눈 나머지로 출력시키는 이유 백준 등 프로그래밍 문제에서 결과를 10^9+7로 나눠