이산 로그

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 개선해주시기 바랍니다. (2017년 10월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

수학에서, 주어진 실수 a와 b에 대해, 로그_b 로그 a는 b = a가 되는^x 숫자 x이다. 이와 유사하게, 모든 그룹 G에서, 거듭제곱^k b는 모든 정수 k에 대해 정의될 수 있으며, 이산 로그_b 로그 a는 b = a가 되는^k 정수 k이다.수론에서, 보다 일반적으로 사용되는 용어는 지수이다: 우리는 r이 m의 원시 근이고 gcd(a,m) = 1이면 r δ a에 대해^x x = ind_r a (mod m) ("a의 지수"를 읽을 수 있다).

이산 로그는 몇 가지 특수한 경우에 빠르게 계산할 수 있습니다.그러나 일반적으로 효율적인 계산 방법은 알려져 있지 않습니다.ElGamal과 같은 공개키 암호학에서 몇 가지 중요한 알고리즘은 신중하게 선택된 그룹에 대한 이산 로그 문제가 효율적인 해결책이 없다는 가정 하에 보안을 기반으로 합니다.

정의.

G를 임의의 그룹으로 합니다.그룹 조작을 곱셈으로 나타내고 ID 요소를 1로 나타냅니다.b를 G의 임의의 원소라고 하자.임의의 양의 정수 k에 대해 식^k b는 b의 곱과 k를 나타낸다.

${\displaystyle b^{k}=\underbrace {b\cdot b\cdots b}_{k\;{\text{cdots}}}.}$

마찬가지로, b는^−k b의⁻¹ 곱과 k배이다.k = 0의 경우 k번째 거듭제곱은 항등식 b⁰ = 1입니다.

a도 G의 원소라고 하자. 방정식^k b = a를 푸는 정수 k를 b에 대한 a의 이산 로그(또는 이 문맥에서는 단순히 로그)라고 한다.k = 로그_b a를 씁니다.

예

10의 거듭제곱

10의 거듭제곱은 유리수의 무한 부분 집합 G = {…, 0.001, 0.01, 0.1, 1, 10, 100, 1000, …}을 형성합니다.이 집합 G는 곱셈 중인 순환 군이고 10은 생성자입니다.그룹의 모든 요소 a에 대해 로그 a를 계산할₁₀ 수 있습니다.예를₁₀ 들어 로그 10000 = 4이고₁₀ 로그 0.001 = -3입니다.이것들은 이산 로그 문제의 예입니다.

실수의 다른 10진수 로그는 정수 이외의 지수를 수반하기 때문에 이산 로그 문제의 인스턴스가 아닙니다.예를 들어, log 53 = 1.724276…은₁₀ 10 = 53을 의미합니다^1.724276….정수지수는 곱과 역수를 사용하여 모든 그룹에서 정의할 수 있지만, 실수의 임의지수는 지수함수와 같은 다른 개념을 필요로 합니다.

고정 실수의 거듭제곱

같은 예는 0이 아닌 임의의 실수 b에도 적용됩니다.거듭제곱은 0이 아닌 실수의 곱셈 부분군 G = {…, b⁻³, b⁻², b⁻¹, b¹²³, …}를 형성한다.G의 모든 요소 a에 대해 로그 a를 계산할_b 수 있습니다.

모듈식 산술

이산 로그의 가장 간단한 설정 중 하나는 그룹(Z_p)^×입니다.이것은 소수 p의 곱셈 모듈 군이다.그 원소는 일치 등급 모듈로 p이며, 두 원소의 군 곱은 원소의 정규 정수 곱에 이어 환원 모듈로 p를 구해도 된다.

이 그룹의 숫자 중 하나의 k번째 거듭제곱은 k번째 거듭제곱을 정수로 구한 다음 p로 나눈 나머지를 구함으로써 계산할 수 있다.관련된 수치가 클 경우 계산 중에 모듈로 p를 여러 번 줄이는 것이 더 효율적입니다.사용되는 특정 알고리즘에 관계없이 이 연산을 모듈러 지수화라고 합니다.예를 들어 (Z₁₇)^×를 고려합니다.이 그룹에서 3을 계산하려면⁴ 3 = 81을 계산한⁴ 다음 81을 17로 나누어 나머지 13을 구하십시오.따라서⁴ 그룹(Z)^×에서₁₇ 3 = 13이다.

이산 로그는 단지 역연산이다.예를 들어, k에 대한 방정식^k 3 13 13 (mod 17)을 고려합니다.위의 예에서 하나의 해는 k = 4이지만 유일한 해는 아닙니다.페르마의 작은 정리로부터 나온 3 follows¹⁶ 1 (mod 17)이므로, n이 정수이면⁴⁺¹⁶ⁿ 3 3⁴ 3 × (3¹⁶) ⁿ13 13 × 1ⁿ 13 13 (mod 17)이 된다.따라서 이 방정식은 4 + 16n 형태의 해를 무한히 많이 가지고 있다.또한 16은 3÷1(mod 17)을^m 만족하는 최소 양의 정수 m이기 때문에, 이것이 유일한 해이다.마찬가지로 모든 가능한 해들의 집합은 k ≤ 4(mod 16)라는 제약조건으로 표현될 수 있다.

정체성의 힘

b가 그룹 G의 항등원소 1인 특별한 경우, 이산 로그_b 로그 a는 1이 아닌 a에 대해 정의되지 않으며, 모든 정수 k는 a = 1에 대해 이산 로그이다.

특성.

거듭제곱은 일반적인 대수적 항등식^{k + l} b = b를^kl 따른다.즉, 함수는

$\displaystyle f\colon \mathbf {Z} \to G}$

f(k) = b에^k 의해 정의되는 것은 b에 의해 생성된 G의 부분군 H에 더해지는 정수 Z로부터의 군 동형이다.H의 모든 a에 대해 로그 a가 존재합니다_b.반대로_b H에 없는에 대해서는 로그a가 존재하지 않습니다.

H가 무한이라면 로그 a도 유일하며 이산_b 로그는 군 동형사상에 해당한다.

$\displaystyle \log _{b}\colon H\to \mathbf {Z}.}$

반면, H가 n차수 유한하다면, 로그_b a는 일치 모듈로 n까지만 유일하며 이산 로그는 군 동형사상에 해당한다.

$\displaystyle \log _{b}\colon H\to \mathbf {Z}_{n}$

여기서_n Z는 정수 모듈로 n의 가법군을 나타냅니다.

일반 로그의 일반적인 기저 변화 공식은 여전히 유효합니다.c가 H의 다른 발전기일 경우,

$\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

알고리즘

이산 로그 문제는 계산적으로 다루기 어려운 것으로 간주된다.즉, 일반적으로 이산 로그를 계산하는 효율적인 고전 알고리즘은 알려져 있지 않습니다.

로그 a를 유한군 G로 계산하는_b 일반적인 알고리즘은 원하는 a가 발견될 때까지 b를 점점 더 큰 거듭제곱 k로 올리는 것이다.이 알고리즘은 트라이얼 곱셈이라고 불리기도 합니다.이 방법에서는 그룹 G의 크기에서 선형으로 실행되며 그룹 크기에서 자릿수가 기하급수적으로 증가합니다.따라서 이는 지수 시간 알고리즘이며, 작은 그룹 G에만 적용됩니다.

일반적으로 정수 인수분해를 위한 유사한 알고리즘에서 영감을 얻은 보다 정교한 알고리즘이 존재합니다.이러한 알고리즘은 순진한 알고리즘보다 빠르게 실행되며, 그 중 일부는 그룹 크기의 제곱근에 비례하므로 그룹 크기의 자리수의 절반으로 지수화됩니다.그러나 이들 중 어느 것도 다항식 시간으로 실행되지 않습니다(그룹 크기의 자리 수).

• 베이비 스텝 거인 스텝
• 함수 필드 체
• 지수 미적분 알고리즘
• 숫자 필드 체
• 폴리그-헬만 알고리즘
• 폴라드 로그 알고리즘
• 폴라드 캥거루 알고리즘(일명 폴라드 람다 알고리즘)

Peter Shor에 ^[1]의해 효율적인 양자 알고리즘이 존재합니다.

효율적인 고전 알고리즘은 특정 특수한 경우에도 존재합니다.예를 들어, 덧셈하는 정수 모듈로 p의 군에서, 거듭제곱^k b는 곱 bk가 되고, 등식은 정수의 합치 모듈로 p를 의미한다.확장 유클리드 알고리즘은 k를 빠르게 찾습니다.

Diffie와 함께-Hellman 순환군 계수 a prime p를 사용하여 Pohlig를 사용하여 이산 로그를 효율적으로 계산할 수 있습니다.Hellman 그룹의 순서(p-1)가 충분히 매끄럽다면, 즉 큰 소수 인자가 없다.

정수 인수분해와의 비교

이산 로그 계산과 정수의 인수분해는 별개의 문제이지만 다음과 같은 특성이 있습니다.

• 둘 다 유한 아벨 그룹에 대한 숨겨진 부분군 문제의 특별한 경우이다.
• 두 문제 모두 어려운 것 같습니다(비표준 컴퓨터에서는 효율적인 알고리즘이 알려져 있지 않습니다).
• 양자 컴퓨터에서의 효율적인 알고리즘이 알려져 있다.
• 한 문제의 알고리즘은 종종 다른 문제에 적응합니다.
• 두 문제의 난이도는 다양한 암호 시스템을 구축하는 데 사용되어 왔다.

암호화

이산대수를 계산하는 것이 명백히 어려운 그룹이 있다.일부 경우(예: 그룹(Z_p)^×의 큰 소수 부분군)에는 최악의 경우로 알려진 효율적인 알고리즘이 없을 뿐만 아니라, 평균 사례의 복잡성은 무작위 자가 감소성을 사용하여 최악의 경우만큼 어렵다는 것을 보여줄 수 있다.

동시에 이산 지수의 역문제는 어렵지 않다(예를 들어 제곱에 의한 지수를 이용하여 효율적으로 계산할 수 있다).이 비대칭은 정수 인수분해와 정수 곱셈 사이의 비대칭과 유사합니다.양쪽 비대칭(및 다른 단방향 함수)이 암호화 시스템의 구축에 악용되었습니다.

이산 로그 암호화(DLC)에서 그룹 G의 일반적인 선택은 순환 그룹(Z_p)(^×예를 들어 ElGamal 암호화, Diffie-)이다.유한 필드에 걸친 타원 곡선의 Hellman 키 교환 및 디지털 서명 알고리즘 및 순환 하위 그룹( 타원 곡선 암호법 참조).

일반적으로 이산 로그 문제를 해결하기 위해 공식적으로 알려진 알고리즘은 없지만, 숫자 필드 체 알고리즘의 처음 세 단계는 유한 로그가 필요한 G의 특정 요소가 아닌 그룹 G에만 의존합니다.특정 그룹에 대해 이 세 단계를 미리 계산함으로써,^[2] 그 그룹에서 특정 로그를 얻기 위해 첫 번째 세 단계보다 훨씬 적은 계산 비용이 드는 마지막 단계만 수행하면 됩니다.

많은 인터넷 트래픽은 1024비트 이하의 소수의 그룹(예를 들어 RFC 2409에 규정된 Oakley 소수 순서의 순환 그룹) 중 하나를 사용하고 있는 것으로 나타났습니다.Logjam 공격은 이 취약성을 이용하여 512비트 소수(export grade)^[2]인 그룹을 사용할 수 있는 다양한 인터넷 서비스를 손상시켰습니다.

Logjam 공격의 저자들은 1024비트 프라임에서 개별 로그 문제를 해결하기 위해 훨씬 더 어려운 사전 계산이 미국 국가안보국(NSA)과 같은 대규모 국가 정보 기관의 예산 범위 내에 있을 것으로 추정한다.Logjam의 저자들은 널리 재사용되는 1024개의 DH 소수에 대한 사전 컴퓨팅이 NSA가 현재 암호화를 ^[2]상당 부분 해독할 수 있다는 NSA 문서의 유출 배후에 있다고 추측하고 있다.

레퍼런스

추가 정보

• 리처드 크랜달, 칼 포메런스5장 소수: Springer, 2부 컴퓨터 관점.
• Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3rd ed.), London: CRC Press, ISBN 978-1-58488-508-5

「 」를 참조해 주세요.

• A. W. Faber 모델 366
• 퍼시 러드게이트와 아일랜드 대수