합동 방정식 풀이기

입력 매개변수

방정식 유형

계수 a ax ≡ b (mod m)의 a

상수 b ax ≡ b (mod m)의 b

법 m 법 (양의 정수여야 함)

빠른 예시:

계산 결과

매개변수를 입력하고 "방정식 풀이"를 클릭하세요

알고리즘 설명:

1. 일차 합동 방정식 ax ≡ b (mod m):

해의 존재 조건:방정식에 해가 존재할 필요충분조건은 gcd(a, m)이 b를 나누는 것 (즉, b가 gcd(a, m)으로 나누어 떨어짐)
해의 개수:해가 존재하면 법 m에 대해 d = gcd(a, m)개의 서로 다른 해가 있음
풀이 방법:
1. d = gcd(a, m) 계산
2. d가 b를 나누는지 확인, 나누지 않으면 해 없음
3. 방정식의 양변을 d로 나눔: (a/d)x ≡ (b/d) (mod m/d)
4. 확장 유클리드 알고리즘을 사용하여 법 m/d에 대한 a/d의 역원 계산
5. x₀ = a' × (b/d) mod (m/d) 계산
6. 일반해: x = x₀ + k(m/d), k = 0, 1, ..., d-1

2. 지수 합동 방정식 a^x ≡ b (mod m) (이산 로그 문제):

문제 설명:a, b, m이 주어졌을 때 a^x ≡ b (mod m)을 만족하는 최소 음이 아닌 정수 x 찾기
해의 존재 조건:
- gcd(a, m) = 1이고 b가 법 m에서 a가 생성하는 순환군의 원소이면 해가 존재함
- 검증 방법: b를 찾거나 전체 순환이 완료될 때까지 a의 거듭제곱을 열거
풀이 방법:
- 작은 범위에서 무차별 대입 검색:x = 0, 1, 2, ...를 해를 찾거나 검색 한계에 도달할 때까지 열거
- Baby-step Giant-step 알고리즘:시간 복잡도 O(√m), 중간 크기 문제에 적합
- Pollard의 rho 알고리즘:큰 소수 법에 적용 가능
주기성:x₀가 해이면 x = x₀ + kφ(m)도 해 (φ(m)은 오일러 피 함수)

3. 응용 시나리오:

암호학:RSA, Diffie-Hellman 키 교환, ElGamal 암호화
정수론 연구:원시근, 이차 잉여, 중국인의 나머지 정리
난수 생성:선형 합동 생성기 (LCG)
해시 함수:해시 테이블에서 모듈러 연산의 응용
경쟁 프로그래밍:빠른 거듭제곱, 모듈러 역원, 정수론 문제

알고리즘 복잡도:

일차 합동 방정식:O(log m) (확장 유클리드 알고리즘의 복잡도)
지수 합동 방정식 (무차별 대입):O(n), n은 검색 한계
지수 합동 방정식 (BSGS):O(√m), 추가 공간 필요

중요 정리:

베주의 항등식:방정식 ax + my = gcd(a, m)은 항상 정수 해를 가짐
페르마의 소정리:p가 소수이고 gcd(a, p) = 1이면 a^(p-1) ≡ 1 (mod p)
오일러의 정리:gcd(a, m) = 1이면 a^φ(m) ≡ 1 (mod m)
중국인의 나머지 정리:합동 방정식의 시스템을 풀 수 있음