結論

$\mod p$における整数$s$の$q$乗根は計算量$O(\sqrt{q})$で求められる。この記事では、Johnston氏によるA Generalized qth Root Algorithmで説明されている方法について解説する。

注意事項

A Generalized qth Root Algorithmの内容を私が読解し、日本語で書いただけの記事である。したがって、情報が完全に正確であるとは保証しない。

きっかけ

この項はアルゴリズムの内容とは関係ないので、必要ない人は読み飛ばしてもよい。

きっかけは以下の問題に出会ったことである。

babyRSA(ISITDTU CTF 2023)

from Crypto.Util.number import bytes_to_long
from FLAG import flag

p1 = 401327687854144602104262478345650053155149834850813791388612732559616436344229998525081674131271
p2 = 500233813775302774885494989064149819654733094475237733501199023993441312997760959607567274704359
p3 = 969568679903672924738597736880903133415133378800072135853678043226600595571519034043189730269981
e1 = 398119
e2 = 283609
e3 = 272383

c = bytes_to_long(flag)
c = pow(c, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)

print(f"{c = }")
# c = 104229015434394780017196823454597012062804737684103834919430099907512793339407667578022877402970

この問題の解法の1つは、$\mod p$で$c$の$e$乗根を総当たりすることである。そこで、SageMathにnth_rootというn乗根を求める関数が存在し、仕組みが気になって調べてみた。

理論の説明

元のpaperに書いてあることを日本語で説明するだけなので、英語を読めるならばそちらを参照した方が正確である。

文字の定義

$G$を位数$p-1$の乗法群とし、$s \in G$を、$q$乗根を求めたい元とする。簡単のため、$q$を素数とし、$|G|$は$q$で割り切れるものとする。また、$g$を$G$の生成元とする。

ここで「$|G|$は$q$で割り切れる」という仮定に違和感を覚えた方もいるかもしれないが、もし$\gcd(|G|, q)=1$ならば、次のようにして簡単に$\sqrt[q]{s}$を求められるからである。

Eulerの$\phi$関数を用いて$d = q^{-1} \mod \phi(p)$とする。また、$dq = 1 \mod \phi(p)$であるから、適当な整数$k$を用いて、$dq = 1 + k\phi(p)$と表せる。

Eulerの定理より、$(\sqrt[q]{s})^{\phi(p)}=1 \mod p$なので、

$s^d = ((\sqrt[q]{s})^q)^d = (\sqrt[q]{s})^{dq} = (\sqrt[q]{s})^{1 + k\phi(p)} = \sqrt[q]{s} \cdot ((\sqrt[q]{s})^{\phi(p)})^k = \sqrt[q]{s}$より、求める値を得る。

$|G|$が$q$で割り切れない場合、$d = q^{-1} \mod \phi(p)$の存在が保証され、しかもそれが高速に計算できるため、このように高速に解を求めることができる。

近似

$g^t$が$s$の$q$乗根と考えれば、ある整数$t$を用いて
$$
s = g^{qt}
$$
と表せる。

ここで、近似するための整数$x$、$z$を考え、
$$
s^x = g^t(g^z)^t
$$

とする。

ここで、底を$g$としたときの指数を比較して

$$
qtx = t(1+z)
$$

したがって

$$
x = \frac{1+z}{q}
$$

この式から、

$(1+z)$は$q$で割り切れる必要がある。
$z \equiv -1\mod q$である必要がある。
$z$と$q$は互いに素である必要がある。
ことが分かる。

よって、$(p-1)$の最も大きな約数であって、$q$と互いに素であるものは、
$$
\frac{p-1}{q^k}
$$
と表される。ただし$k$は$q^k$が$(p-1)$を割り切る最大の指数。

よって、
$$
z = \frac{p-1}{q^k}
$$

また、
$$
x = \frac{1+z}{q}
$$

とできる。

誤差項の修正

$$
s^x = g^t(g^z)^t
$$

において、誤差項は$(g^z)^t$である。

ここで、元$g^z$の位数は$q^k$である。ちなみに、もし$k=1$ならば、この近似はすでに$q$乗根となっている。

底を$g^{\frac{p-1}{q^{k-1}}}$として、$s^{\frac{p-1}{q^k}}$の離散対数を求めると、$t \mod q^{k-1}$が求められる。($s=g^{qt}$を考えると理解できると思う)

よって、$s^x = g^t(g^z)^t$より誤差項を排除して、求める$q$乗根$u$は

$$
u = s^x(g^z)^{-t}
$$

となる。

実装

アルゴリズムの手順は以下のようになる。

もし $s^{\frac{p-1}{q}} \mod p \not\equiv 1$ならば終了する。$q$乗根は存在しない。(フェルマーの小定理を考えればよい)
$h = \frac{p-1}{q}$とする。
$h \mod q = 0$である間、$h$の値を$h=\frac{h}{q}$と更新する。
$z=h$, $x=\frac{1+z}{q}$とする。
$v \equiv s^x \mod p$とする。
何らかの離散対数問題を解くアルゴリズムを用いて、$(g^{hq})^t = s^h$となる$t$を求める。
$\sqrt[q]{s} \equiv vg^{-xt}である。$