정수·기초
정수
Integer
기호
ℤ뜻
음의 정수, 0, 양의 정수를 모두 포함하는 수입니다.
언제 쓰나
방향이 있는 개수, 인덱스, 차이, 이산적인 정확한 계산에 사용합니다.
계산 예시
-4, 0, 그리고 27은 정수입니다.수학 참고
정수론 용어와 계산 가이드
정수, 소수, 모듈러 산술, 순환군의 생성원, 이차잉여, 디오판토스 방정식, RSA를 수식과 계산 예시로 설명합니다.
법 7의 생성원 순환
3의 거듭제곱을 반복하면 1로 돌아오기 전에 0이 아닌 모든 잉여를 방문합니다.
법 7의 이차잉여
0이 아닌 잉여를 제곱하면 1, 2, 4만 얻습니다.
55 개 용어
정수·기초
자연수
Natural number
기호
ℕ뜻
수를 세는 데 사용하는 수이며 0의 포함 여부는 사용하는 정의에 따라 달라집니다.
언제 쓰나
증명, 사양, 프로그램에서 자연수를 쓰기 전에 0 포함 여부를 명시합니다.
주의
일부 교재는 자연수를 1부터 정의하므로 사용한 규칙을 확인해야 합니다.
계산 예시
This guide uses ℕ = {0, 1, 2, 3, ...}.정수·기초
절댓값
Absolute value
기호
|a|뜻
정수와 수직선의 0 사이 거리를 음수가 아닌 값으로 나타낸 것입니다.
언제 쓰나
크기, 거리, 오차, 대칭 범위를 나타낼 때 사용합니다.
계산 예시
|-7| = 7 and |5 - 12| = 7.정수·기초
홀짝성
Parity
기호
n mod 2뜻
정수가 짝수인지 홀수인지를 나타내는 성질입니다.
언제 쓰나
조건 분기, 교대 패턴, 증명, 검사값, 비트 논리에 사용합니다.
계산 예시
18 mod 2 = 0, so 18 is even.정수·기초
나눗셈 정리
Division algorithm
기호
a = bq + r뜻
정수 a와 양의 정수 b에 대해 0 ≤ r < b를 만족하는 몫 q와 나머지 r가 유일하게 존재한다는 정리입니다.
언제 쓰나
몫과 나머지, 유클리드 알고리즘, 모듈러 산술의 기초로 사용합니다.
계산 예시
29 = 6 × 4 + 5, so q = 4 and r = 5.약수·배수
약수
Divisor
기호
d | n뜻
어떤 정수 k에 대해 n = dk가 되면 d를 n의 약수라고 합니다.
언제 쓰나
인수 구조, 공약수, 나누어떨어짐을 분석할 때 사용합니다.
계산 예시
6 | 42 because 42 = 6 × 7.약수·배수
배수
Multiple
기호
n = dk뜻
정수에 다른 정수를 곱해 얻는 수입니다.
언제 쓰나
일정, 공통 주기, 순환 시스템, 분모 통일에 사용합니다.
계산 예시
5의 배수에는 0, 5, 10, 15, 그리고 20이 포함됩니다.약수·배수
배수 판정법
Divisibility test
기호
n mod d = 0뜻
긴 나눗셈을 하지 않고 한 정수가 다른 정수로 나누어떨어지는지 판단하는 규칙입니다.
언제 쓰나
빠른 확인, 암산, 입력 검증, 자릿값 구조 설명에 사용합니다.
계산 예시
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.약수·배수
최대공약수
Greatest common divisor
기호
gcd(a, b)뜻
두 정수를 모두 나누어떨어지게 하는 가장 큰 양의 정수입니다.
언제 쓰나
분수 약분, 서로소 판정, 합동식 풀이, 비율 계산에 사용합니다.
계산 예시
gcd(84, 30) = 6.약수·배수
최소공배수
Least common multiple
기호
lcm(a, b)뜻
0이 아닌 두 정수의 공통 배수 중 가장 작은 양의 정수입니다.
언제 쓰나
주기 동기화, 분수 계산, 반복 일정 계산에 사용합니다.
계산 예시
lcm(12, 18) = 36.약수·배수
GCD-LCM 항등식
GCD-LCM identity
기호
gcd(a,b)lcm(a,b)=|ab|뜻
0이 아닌 두 정수의 최대공약수와 최소공배수를 연결하는 관계식입니다.
언제 쓰나
한 값을 알고 있을 때 다른 값을 효율적으로 계산하는 데 사용합니다.
계산 예시
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.약수·배수
유클리드 알고리즘
Euclidean algorithm
기호
gcd(a,b)=gcd(b,a mod b)뜻
나머지 계산을 반복해 최대공약수를 구하는 알고리즘입니다.
언제 쓰나
입력 정수가 큰 경우에도 빠른 GCD 계산에 사용합니다.
계산 예시
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.약수·배수
확장 유클리드 알고리즘
Extended Euclidean algorithm
기호
ax + by = gcd(a,b)뜻
최대공약수와 함께 베주 계수 x, y를 구하는 유클리드 알고리즘의 확장입니다.
언제 쓰나
모듈러 역원을 계산하고 일차 디오판토스 방정식을 풀 때 사용합니다.
계산 예시
35×(-1) + 12×3 = 1 이므로, -1은 35의 계수입니다.약수·배수
서로소
Coprime integers
기호
gcd(a,b)=1뜻
두 정수의 최대공약수가 1일 때 두 수를 서로소라고 합니다.
언제 쓰나
법 n에서 역원이 존재하는지 판단하고 오일러 정리를 적용할 때 사용합니다.
계산 예시
8과 15은 어느 숫자도 소수가 아니지만 서로소입니다.소수·인수분해
소수
Prime number
기호
p뜻
1보다 크고 양의 약수가 1과 자기 자신뿐인 정수입니다.
언제 쓰나
정수 인수분해와 공개 키 암호의 기본 구성 요소로 사용합니다.
계산 예시
2, 3, 5, 7, 그리고 11은 소수입니다.소수·인수분해
합성수
Composite number
기호
n = ab뜻
1보다 크고 1과 자기 자신 외의 양의 약수를 가진 정수입니다.
언제 쓰나
인수분해할 수 있는 정수와 소수를 구분할 때 사용합니다.
계산 예시
21 is composite because 21 = 3 × 7.소수·인수분해
소인수분해
Prime factorization
기호
n=∏pᵢ^aᵢ뜻
정수를 소수의 거듭제곱들의 곱으로 나타내는 것입니다.
언제 쓰나
약수, 최대공약수, 최소공배수, 산술 함수를 계산할 때 사용합니다.
계산 예시
360 = 2^3 × 3^2 × 5.소수·인수분해
산술의 기본정리
Fundamental theorem of arithmetic
기호
n=∏pᵢ^aᵢ뜻
1보다 큰 모든 정수는 인수 순서를 제외하면 유일한 소인수분해를 갖는다는 정리입니다.
언제 쓰나
소수 지수에 기반한 알고리즘과 증명을 정당화할 때 사용합니다.
계산 예시
72 = 2^3 × 3^2는 72의 유일한 소인수분해입니다.소수·인수분해
에라토스테네스의 체
Sieve of Eratosthenes
뜻
발견한 소수의 배수를 차례로 지워 상한 이하의 소수를 구하는 알고리즘입니다.
언제 쓰나
같은 적당한 상한 범위에서 소수 질의를 여러 번 처리할 때 사용합니다.
계산 예시
30까지의 소수를 찾으려면, 2, 3, 그리고 5의 배수를 표시합니다.소수·인수분해
소수 판정
Primality test
뜻
주어진 정수가 소수인지 판단하는 알고리즘입니다.
언제 쓰나
작은 입력에는 시험 나눗셈을, 큰 입력에는 Miller-Rabin 같은 확률적 판정을 사용합니다.
주의
확률적 소수 판정은 여러 번 반복하거나 대상 정수 범위에 맞는 결정적 밑 집합이 필요할 수 있습니다.
계산 예시
시도 나눗셈은 후보 약수만 √n까지 필요합니다.모듈러 산술
합동
Congruence
기호
a ≡ b (mod n)뜻
두 정수의 차가 n으로 나누어떨어질 때 법 n에 대해 합동이라고 합니다.
언제 쓰나
순환 계산에서 정수를 동치인 나머지로 바꾸어 계산할 때 사용합니다.
계산 예시
29 ≡ 5 (mod 12) 이므로, 12는 29 - 5를 나눕니다.모듈러 산술
잉여류
Residue class
기호
[a]ₙ뜻
법 n에 대해 특정 정수와 합동인 모든 정수의 집합입니다.
언제 쓰나
모듈러 값을 개별 수가 아닌 동치류로 다룰 때 사용합니다.
계산 예시
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.모듈러 산술
나머지 연산
Modulo operation
기호
a mod n뜻
n으로 나눈 뒤 대표 나머지를 반환하는 연산입니다.
언제 쓰나
인덱스 순환, 시계 계산, 해시 버킷, 주기 상태에 사용합니다.
계산 예시
(23 + 5) mod 24 = 4.모듈러 산술
모듈러 산술
Modular arithmetic
기호
ℤ/nℤ뜻
잉여류에서 계산하고 결과를 법 n으로 줄이는 산술입니다.
언제 쓰나
암호, 부호 이론, 순환 버퍼, 달력 계산에 사용합니다.
계산 예시
(17 × 19) mod 12 = 11.모듈러 산술
모듈러 역원
Modular inverse
기호
a⁻¹ mod n뜻
ax ≡ 1 (mod n)을 만족하는 x이며 gcd(a,n)=1일 때에만 존재합니다.
언제 쓰나
모듈러 산술의 나눗셈, 합동식 풀이, 암호 알고리즘에 사용합니다.
주의
나누는 수와 법이 서로소인지 확인하지 않고 모듈러 나눗셈을 하면 안 됩니다.
계산 예시
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).모듈러 산술
모듈러 거듭제곱
Modular exponentiation
기호
a^k mod n뜻
매우 커질 수 있는 전체 거듭제곱 값을 만들지 않고 법 n에서 거듭제곱을 계산하는 방법입니다.
언제 쓰나
암호, 소수 판정, 큰 지수 문제에서 반복 제곱법을 사용합니다.
계산 예시
3^13 mod 7 = 3 using repeated squaring.모듈러 산술
일차 합동식
Linear congruence
기호
ax ≡ b (mod n)뜻
일차 모듈러 방정식을 만족하는 정수 x를 구하는 합동식입니다.
언제 쓰나
GCD 조건과 모듈러 역수를 사용하여 해를 결정하고 계산합니다.
계산 예시
3x ≡ 4 (mod 7) 이면, x ≡ 6 (mod 7) 입니다.모듈러 산술
중국인의 나머지 정리
Chinese remainder theorem
기호
x ≡ aᵢ (mod nᵢ)뜻
서로소인 여러 법의 합동식을 결합하면 법들의 곱에 대해 유일한 해를 얻는다는 정리입니다.
언제 쓰나
독립적인 순환 조건을 결합하고 큰 정수 계산을 분할할 때 사용합니다.
계산 예시
x ≡ 2 (mod 3), x ≡ 3 (mod 5)이면, x ≡ 8 (mod 15)입니다.모듈러 산술
오일러 피 함수
Euler's totient function
기호
φ(n)뜻
1부터 n까지의 정수 중 n과 서로소인 정수의 개수입니다.
언제 쓰나
오일러 정리, RSA 키 계산, 기약 잉여계에 사용합니다.
계산 예시
φ(12) = 4이므로, 1, 5, 7, 그리고 11은 12와 서로소입니다.모듈러 산술
오일러 정리
Euler's theorem
기호
a^φ(n) ≡ 1 (mod n)뜻
a와 n이 서로소이면 a를 φ(n)제곱한 값은 법 n에서 1과 합동이라는 정리입니다.
언제 쓰나
지수를 줄이고 모듈러 항등식을 증명하며 RSA 원리를 설명할 때 사용합니다.
계산 예시
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).모듈러 산술
페르마의 소정리
Fermat's little theorem
기호
a^(p-1) ≡ 1 (mod p)뜻
소수 p와 p의 배수가 아닌 a에 대해 a의 p-1제곱은 법 p에서 1과 합동이라는 정리입니다.
언제 쓰나
소수 법에서 역원을 구하고 소수 후보를 판정할 때 사용합니다.
주의
의사소수가 존재하므로 페르마 판정을 통과했다는 사실만으로 소수임을 증명할 수 없습니다.
계산 예시
2^6 ≡ 1 (mod 7).순환군·생성원
군
Group
기호
(G, *)뜻
결합법칙을 만족하는 연산, 항등원, 각 원소의 역원을 갖는 집합입니다.
언제 쓰나
연산을 합성하고 되돌릴 수 있는 산술 구조를 설명할 때 사용합니다.
계산 예시
정수는 덧셈 연산에 대해 0을 항등원으로 하고, a에 대한 역원이 -a인 그룹을 이룬다.순환군·생성원
아벨군
Abelian group
기호
a*b=b*a뜻
군 연산에 교환법칙이 성립하는 군입니다.
언제 쓰나
모듈러 덧셈, 벡터 덧셈처럼 연산 순서가 결과에 영향을 주지 않는 구조에 사용합니다.
계산 예시
(ℤ/nℤ, +)는 아벨 군입니다.순환군·생성원
법 n의 덧셈군
Additive group modulo n
기호
(ℤ/nℤ, +)뜻
법 n의 잉여류에 모듈러 덧셈을 정의한 군입니다.
언제 쓰나
순환 카운터, 주기 상태, 덧셈 합동류를 모델링할 때 사용합니다.
계산 예시
In ℤ/5ℤ, 3+4=2.순환군·생성원
단위원군
Multiplicative group of units
기호
(ℤ/nℤ)×뜻
n과 서로소인 잉여류에 모듈러 곱셈을 정의한 군입니다.
언제 쓰나
모듈러 역원, 원시근, 오일러 정리, 공개 키 암호를 분석할 때 사용합니다.
계산 예시
(ℤ/8ℤ)×={1,3,5,7}.순환군·생성원
순환군
Cyclic group
기호
G=⟨g⟩뜻
하나의 원소를 반복해서 연산하여 모든 원소를 얻을 수 있는 군입니다.
언제 쓰나
군 연산을 지수나 정수배에 대한 산술로 바꾸어 다룰 때 사용합니다.
계산 예시
가환군 ℤ/6ℤ은 1과 5에 의해 생성됩니다.순환군·생성원
생성원
Generator
기호
⟨g⟩=G뜻
군 연산을 반복했을 때 순환군의 모든 원소를 만드는 원소입니다.
언제 쓰나
순환군의 원소를 열거하고 지수 기반 암호 연산을 정의할 때 사용합니다.
주의
같은 원소도 구조에 따라 생성원 여부가 달라지므로 군과 연산을 반드시 명시해야 합니다.
계산 예시
7을 법으로 하는 3의 거듭제곱은 3, 2, 6, 4, 5, 1을 생성하며, 따라서 3은 (ℤ/7ℤ)×를 생성합니다.순환군·생성원
원소의 위수
Order of an element
기호
ord(g)뜻
g의 k제곱이 항등원이 되는 가장 작은 양의 정수 k입니다.
언제 쓰나
원소가 생성원인지 확인하고 반복 주기를 구할 때 사용합니다.
계산 예시
7을 법으로 했을 때, ord(2) = 3입니다. 왜냐하면 2^3 ≡ 1이고, 더 작은 양의 지수로는 같은 결과를 얻을 수 없기 때문입니다.순환군·생성원
원시근
Primitive root
기호
ordₙ(g)=φ(n)뜻
법 n의 단위원군 전체를 생성하는 생성원입니다.
언제 쓰나
0이 아닌 잉여를 거듭제곱으로 표현하고 이산로그를 정의할 때 사용합니다.
계산 예시
3은 7을 법으로 하는 원시근입니다. 왜냐하면 3의 차수는 φ(7)=6이기 때문입니다.순환군·생성원
원시근 존재 조건
Primitive root existence
뜻
법 n의 원시근은 n=1, 2, 4, p^k 또는 2p^k이고 p가 홀수 소수일 때에만 존재합니다.
언제 쓰나
합성수 법에서 원시근을 찾기 전에 존재 여부를 판정할 때 사용합니다.
계산 예시
8은 필요한 조건을 만족하는 형태를 가지지 않기 때문에, 8을 법으로 하는 원시근은 존재하지 않습니다.순환군·생성원
이산로그
Discrete logarithm
기호
g^x=h뜻
생성원 g와 군 원소 h가 주어졌을 때 g^x=h를 만족하는 지수 x를 구하는 문제입니다.
언제 쓰나
Diffie-Hellman, ElGamal, 타원곡선 암호의 안전성 가정을 이해할 때 사용합니다.
주의
이산로그는 작거나 잘못 선택한 군에서는 쉬울 수 있으며 적절한 매개변수에서만 어렵습니다.
계산 예시
생성자가 3인 7을 법으로 하는 합동 연산에서, log₃(5) = 5 입니다. 왜냐하면 3⁵ ≡ 5 이기 때문입니다.순환군·생성원
카마이클 함수
Carmichael function
기호
λ(n)뜻
n과 서로소인 모든 a에 대해 a^m≡1 (mod n)이 되는 가장 작은 양의 정수 m입니다.
언제 쓰나
모듈러 거듭제곱과 RSA 분석에서 φ(n)보다 작은 보편 지수를 구할 때 사용합니다.
계산 예시
λ(8) = 2이므로, 모든 홀수 a에 대해 a² ≡ 1 (mod 8)이 성립합니다.이차잉여
이차잉여
Quadratic residue
기호
x²≡a (mod n)뜻
합동식 x²≡a (mod n)을 만족하는 x가 존재하는 잉여입니다.
언제 쓰나
모듈러 제곱근, 소수 판정, 이차잉여 기반 암호를 분석할 때 사용합니다.
계산 예시
2는 7을 법으로 하는 이차잉여입니다. 왜냐하면 3²≡2이기 때문입니다.이차잉여
이차비잉여
Quadratic nonresidue
뜻
합동식 x²≡a (mod n)에 해가 없는 0이 아닌 잉여입니다.
언제 쓰나
잉여를 분류하고 이차 특성이 정해진 판정법이나 암호 매개변수를 만들 때 사용합니다.
계산 예시
3은 7을 법으로 하는 이차비잉여입니다.이차잉여
모듈러 제곱근
Modular square root
기호
x=√a mod n뜻
x²≡a (mod n)을 만족하는 해 x입니다.
언제 쓰나
점 압축 해제, 정수론 알고리즘, 잉여 기반 암호에 사용합니다.
계산 예시
7을 법으로 하는 2의 제곱근은 3과 4입니다.이차잉여
르장드르 기호
Legendre symbol
기호
(a/p)뜻
홀수 소수 p에 대해 p의 배수 여부와 법 p에서 이차잉여인지 나타내는 0, 1, -1의 값입니다.
언제 쓰나
이차 특성을 판정하고 오일러 판정법과 이차상호법칙을 간결하게 표현할 때 사용합니다.
계산 예시
(2/7)=1 이므로, 2는 7을 법으로 하는 이차잉여입니다.이차잉여
야코비 기호
Jacobi symbol
기호
(a/n)뜻
르장드르 기호를 양의 홀수 합성수 분모까지 곱셈적으로 확장한 기호입니다.
언제 쓰나
n을 먼저 인수분해하지 않고 이차 특성 관련 값을 효율적으로 계산하는 알고리즘에 사용합니다.
주의
야코비 기호가 1이어도 합성수 n에 대해 a가 이차잉여라는 보장은 없습니다.
계산 예시
(5/21)=(5/3)(5/7)=1.이차잉여
오일러 판정법
Euler's criterion
기호
a^((p-1)/2)≡(a/p) (mod p)뜻
모듈러 거듭제곱으로 홀수 소수 법에서 이차잉여 여부를 판정하는 방법입니다.
언제 쓰나
모든 제곱을 나열하지 않고 르장드르 기호를 계산할 때 사용합니다.
계산 예시
p=7일 때, 3^3 ≡ -1 (mod 7)이므로, 3은 이차 비잔여원소입니다.이차잉여
이차상호법칙
Quadratic reciprocity
기호
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)뜻
한 홀수 소수가 다른 홀수 소수 법에서 이차잉여인지 서로 연결하는 정리입니다.
언제 쓰나
큰 르장드르 기호 계산을 더 작은 계산으로 바꿀 때 사용합니다.
계산 예시
3과 11은 모두 4를 법으로 했을 때 3이므로, (3/11)=-(11/3)입니다.이차잉여
이차상호법칙의 보충법칙
Supplementary laws
기호
(-1/p), (2/p)뜻
홀수 소수 법에서 -1과 2의 이차 특성을 결정하는 공식입니다.
언제 쓰나
이차상호법칙과 함께 르장드르 기호 계산을 마무리할 때 사용합니다.
계산 예시
(2/p)=1 이면 p≡1 또는 7 (mod 8)이고, (2/p)=-1 이면 p≡3 또는 5 (mod 8)입니다.이차잉여
Tonelli-Shanks 알고리즘
Tonelli-Shanks algorithm
뜻
홀수 소수 법에서 이차잉여의 모듈러 제곱근을 구하는 알고리즘입니다.
언제 쓰나
법이 소수이고 p≡3 (mod 4)인 간단한 공식을 사용할 수 없을 때 사용합니다.
계산 예시
p=13일 때, Tonelli-Shanks 알고리즘은 x²≡10 (mod 13)에 대해 x=6 또는 7을 찾습니다.이차잉여
합성수 법의 제곱근
Square roots modulo a composite
뜻
소수 거듭제곱 인수별로 제곱근을 구한 뒤 중국인의 나머지 정리로 결합한 값입니다.
언제 쓰나
Rabin 계열 시스템과 합성수 법의 합동식을 분석할 때 사용합니다.
주의
서로 다른 홀수 소수의 곱에서는 하나의 잉여가 여러 제곱근을 가질 수 있어 원하는 근을 고르려면 추가 정보가 필요합니다.
계산 예시
x² ≡ 1 (mod 3) 및 x² ≡ 1 (mod 5)을 풀고, 그 결과를 15을 법으로 하는 부호 선택을 결합합니다.정수 방정식
디오판토스 방정식
Diophantine equation
뜻
정수해만을 구하는 방정식입니다.
언제 쓰나
정수해가 존재하는지 확인하기 위해 가 divisibility, GCD, congruences, 그리고 bounds를 사용합니다.
계산 예시
3x + 5y = 17 has the integer solution x = 4, y = 1.정수 방정식
일차 디오판토스 방정식
Linear Diophantine equation
기호
ax + by = c뜻
미지수가 정수여야 하는 일차방정식이며 gcd(a,b)가 c를 나눌 때에만 해가 존재합니다.
언제 쓰나
정확한 배분, 동전 문제, 일정, 격자 제약을 풀 때 사용합니다.
계산 예시
6x + 9y = 30은 gcd(6,9)=3이 30을 나누므로 해가 존재합니다.응용
RSA 산술
RSA arithmetic
기호
c ≡ m^e (mod n)뜻
모듈러 거듭제곱과 큰 두 소수의 곱을 인수분해하기 어렵다는 성질을 이용한 공개 키 산술입니다.
언제 쓰나
정수론이 암호화와 전자서명을 지원하는 원리를 이해할 때 사용합니다.
주의
작은 예시 값은 학습용일 뿐이며 실제 RSA에는 표준 패딩, 안전한 키 크기, 검증된 라이브러리가 필요합니다.
계산 예시
n=55, e=3, 그리고 m=7인 경우, c=7^3 mod 55=13입니다.