폴리그-헬먼 알고리즘 (영어 : Pohlig–Hellman algorithm )은 이산 로그 를 밑의 차수가 소수 인 경우로 귀결시켜 계산하는 알고리즘 이다. 군의 크기(즉, 밑의 차수)가 충분히 매끄러운 정수 인 경우 특히 효율적이다.
폴리그-헬먼 알고리즘
PH
{\displaystyle \operatorname {PH} }
입력: 크기가
n
{\displaystyle n}
순환군 의 생성 원소
g
∈
G
{\displaystyle g\in G}
h
∈
G
{\displaystyle h\in G}
출력: 이산 로그
log
g
h
∈
Z
/
n
{\displaystyle \log _{g}h\in \mathbb {Z} /n}
n
{\displaystyle n}
소인수 분해
n
=
p
1
e
1
⋯
p
r
e
r
{\displaystyle n=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}}
만약
r
=
0
{\displaystyle r=0}
r
=
1
{\displaystyle r=1}
e
1
=
1
{\displaystyle e_{1}=1}
BSGS
(
g
,
h
)
{\displaystyle \operatorname {BSGS} (g,h)}
ρ
(
g
,
h
)
{\displaystyle \rho (g,h)}
BSGS
{\displaystyle \operatorname {BSGS} }
아기걸음 거인걸음 (
ρ
{\displaystyle \rho }
폴라드 로 이산 로그 알고리즘 )이다.
만약
r
=
1
{\displaystyle r=1}
u
←
PH
(
g
⌊
e
1
/
2
⌋
,
h
⌊
e
1
/
2
⌋
)
{\displaystyle u\leftarrow \operatorname {PH} (g^{\lfloor e_{1}/2\rfloor },h^{\lfloor e_{1}/2\rfloor })}
v
←
PH
(
h
g
−
u
,
g
p
1
⌈
e
1
/
2
⌉
)
{\displaystyle v\leftarrow \operatorname {PH} (hg^{-u},g^{p_{1}\lceil e_{1}/2\rceil })}
u
+
v
p
1
e
1
{\displaystyle u+vp_{1}^{e_{1}}}
n
1
←
p
1
e
1
⋯
p
⌊
r
/
2
⌋
e
⌊
r
/
2
⌋
{\displaystyle n_{1}\leftarrow p_{1}^{e_{1}}\cdots p_{\lfloor r/2\rfloor }^{e_{\lfloor r/2\rfloor }}}
n
2
←
n
/
n
1
{\displaystyle n_{2}\leftarrow n/n_{1}}
M
1
{\displaystyle M_{1}}
n
2
{\displaystyle n_{2}}
n
2
{\displaystyle n_{2}}
Z
/
n
1
{\displaystyle \mathbb {Z} /n_{1}}
M
2
{\displaystyle M_{2}}
n
1
{\displaystyle n_{1}}
n
1
{\displaystyle n_{1}}
Z
/
n
2
{\displaystyle \mathbb {Z} /n_{2}}
x
1
←
PH
(
g
n
2
,
h
n
2
)
{\displaystyle x_{1}\leftarrow \operatorname {PH} (g^{n_{2}},h^{n_{2}})}
x
2
←
PH
(
g
n
1
,
h
n
1
)
{\displaystyle x_{2}\leftarrow \operatorname {PH} (g^{n_{1}},h^{n_{1}})}
M
1
x
1
+
M
2
x
2
{\displaystyle M_{1}x_{1}+M_{2}x_{2}}
폴리그-헬먼 알고리즘의 복잡도는 순환군의 크기(즉, 이산 로그의 밑의 차수)가 소수인 경우에 사용하는 알고리즘의 복잡도와
n
{\displaystyle n}
아기걸음 거인걸음 을 사용하는 경우, 폴리그-헬먼 알고리즘의 시간 복잡도는
O
(
ln
n
ln
ln
n
+
∑
i
=
1
r
e
i
p
i
)
{\displaystyle O\left(\ln n\ln \ln n+\sum _{i=1}^{r}e_{i}{\sqrt {p_{i}}}\right)}
(특히
O
(
ln
n
(
ln
ln
n
+
p
)
)
{\displaystyle O(\ln n(\ln \ln n+{\sqrt {p}}))}
O
(
p
)
{\displaystyle O({\sqrt {p}})}
n
{\displaystyle n}
n
=
p
1
e
1
⋯
p
r
e
r
{\displaystyle n=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}}
n
{\displaystyle n}
소인수 분해 ,
p
{\displaystyle p}
n
{\displaystyle n}
플로이드 순환 탐지 알고리즘 을 갖춘 폴라드 로 이산 로그 알고리즘 을 사용하는 경우, 폴리그-헬먼 알고리즘의 기대 시간 복잡도는
O
(
ln
n
ln
ln
n
+
∑
i
=
1
r
e
i
p
i
)
{\displaystyle O\left(\ln n\ln \ln n+\sum _{i=1}^{r}e_{i}{\sqrt {p_{i}}}\right)}
(특히
O
(
ln
n
(
ln
ln
n
+
p
)
)
{\displaystyle O(\ln n(\ln \ln n+{\sqrt {p}}))}
O
(
1
)
{\displaystyle O(1)}
특히, 만약
n
{\displaystyle n}
매끄러운 정수 인 경우 폴리그-헬먼 알고리즘은
n
{\displaystyle n}
준선형 시간 을 갖는다.
스티븐 폴리그(영어 : Steven C. Pohlig )와 마틴 헬먼 이 1978년 논문에서 처음 출판하였다.[ 1]
“
출판된 적은 없지만, 이 새로운 알고리즘은 몇 년 전에 롤런드 실버가, 더 최근에는 리처드 슈로펄과 H. 블록이 독립적으로 발견했다.
Although not previously published, the new algorithm was discovered independently by Roland Silver some years ago, and more recently by Richard Schroeppel and H. Block.
”
↑ 가 나 Pohlig, Stephen C.; Hellman, Martin E. (1978). “An improved algorithm for computing logarithms over
GF
(
p
)
{\displaystyle \operatorname {GF} (p)}
24 (1): 106–110. doi :10.1109/TIT.1978.1055817 . ISSN 0018-9448 . MR 0484737 . Zbl 0375.68023 .
