G를 n개의 요소를 갖는 유한 순환 집합이라고 하자. 그것은 그룹이 곱셈적으로 쓰여진 것으로 간주합니다. b를 G의 생성기라고 하고 G의 각 요소 g는 g =b k 형식으로 작성할 수 있습니다. 어떤 정수 k에 대해.
더욱이, g를 정의하는 두 개의 정수는 합동 모듈로 n이 될 것입니다. 기능 로그를 나타낼 수 있습니다.b :G → Zn (여기서 Zn k 모듈로 n의 합동 클래스를 g에 생성하여 정수 모듈로 n)의 고리를 나타냅니다. 이 함수는 b를 기반으로 하는 이산 알고리즘으로 알려진 그룹 동형화입니다.
수학, 특히 추상 대수학 및 그 응용 분야에서 이산 대수는 일반 알고리즘의 이론적 유사체로 설정됩니다. 특히, 일반 알고리즘 로그a (b)는 방정식 a x 의 해입니다. =b 실수 또는 복소수.
마찬가지로 g 및 h가 유한 순환 그룹 G의 요소이면 방정식 g x 의 해 x =h는 그룹 G에서 h의 밑수 g에 대한 이산 로그로 알려져 있습니다.
이산 로그는 정수론에서 큰 역사를 가지고 있습니다. 원래 그들은 유한 영역의 계산에 기본적으로 사용되었습니다. 그러나 IFP(Integer Factorization Problem)와 같이 다소 모호했습니다.
공개 키 암호 시스템 구현에 필수적인 가장 중요한 도구는 이산 로그 문제(DLP)입니다. DLP에 보안을 기반으로 하는 몇 가지 인기 있는 최신 암호 알고리즘이 있습니다. 이 문제의 복잡성을 기반으로 합니다. Diffie-Hellman은 1976년에 잘 알려진 Diffie-Hellman 키 계약 방식을 제안했습니다.
예시
-
이산 로그는 그룹에서 가장 배우기 쉽습니다(Zp ). 이것은 곱셈 모듈로, 소수 p에서 합동 클래스(1,….., p – 1)의 그룹입니다.
-
이 그룹에 있는 숫자 중 하나의 k번째 거듭제곱을 찾아야 하는 경우 k번째 거듭제곱을 정수로 찾은 다음 p로 나눈 나머지를 구하면 됩니다.
-
이 과정을 이산 지수화라고 합니다.
-
예를 들어, (Z17 ) x . 3 4 를 계산할 수 있습니다. 이 그룹에서는 먼저 3 4 을 계산할 수 있습니다. =81이므로 81을 17로 나누어 나머지 13을 얻을 수 있습니다.
-
따라서 3 4 =그룹의 13(Z17 ) x . 이산 로그는 역연산일 뿐입니다. 예를 들어, 방정식 3 k 를 취할 수 있습니다. =13(mod 17) k.
-
여기서 k =4는 솔루션입니다. 3 16 이후 ≡ 1(mod 17), n이 정수이면 3 4+16n 도 따릅니다. ≡ 13 x 1 n ≡ 13(모드 17).
-
따라서 방정식은 4 + 16n 형식의 몇 가지 해를 무한히 갖습니다. 게다가 16은 3 m 을 충족하는 가장 작은 양의 정수 m이기 때문입니다. ≡ 1(mod 17), i. 이자형. , 16은 (Z17에서 3의 차수입니다.) ) x , 유일한 해결책이 있습니다. 유사하게, 해는 k ≡ 4 (mod)16으로 정의될 수 있습니다.
-
일반 이산 로그를 계산하기 위한 효율적인 알고리즘이 없습니다.logb g는 알려져 있습니다.