LoginSignup
0

法が素数の時のn乗根を求める

Last updated at Posted at 2023-10-24

結論

$\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$乗根を総当たりすることである。そこで、SageMathnth_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}
$$

となる。

実装

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


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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0