1. 계산 수론에서, 어려운 문제들
ㅇ 수론에서, 수치적으로 해결이 쉽지 않은 주요 문제들 셋(3)
- 이산 대수 문제 (Discrete Logarithm Problem, DLP)
- 타원 곡선 상의 이산 대수 문제 (Elliptic Curve Discrete Logarithm Problem, ECDLP)
- 정수 인수분해 문제 (Integer Factorization Problem, IFP)
ㅇ 이들은, 단방향 함수 (On-way Function)의 일종으로 간주됨
- 例) RSA에서, 소인수분해의 어려움 등
2. 유한체 상의 이산 대수 문제 (Discrete Logarithm Problem, DLP)
ㅇ y = gx mod p
- g,x,p를 알고서, y를 구하기(계산하기)는 쉽지만,
- y,g,p를 알고서, x를 구하는 문제의 어려움
. 즉, 지수 계산의 역 연산인 로그 계산의 어려움 ( x = loggy )
ㅇ Diffie-Hellman 알고리즘에 응용된 문제
3. 타원 곡선 상의 이산 대수 문제 (Elliptic Curve Discrete Logarithm Problem, ECDLP)
ㅇ 타원 곡선 상의 한 점과 그 점의 배수 간의 관계에서, 배수를 구하는 문제의 어려움
4. 정수 인수분해 문제 (Integer Factorization Problem, IFP) : 소인수 분해
ㅇ 정수 인수분해의 어려움