安全素数とべき乗と逆元 - Qiita

A TTP-free mental poker protocol achieving player confidentialityでは$e_r = (e_{r-1})^{K_i^{-1}}$といった、 べき根 のような計算を用いて暗号化や復号化をしている。これを字面通りに行うためには、$e_r = \sqrt[K_i]{e_{r-1}}$という数を求める必要があり、これは（何か効率的な方法があるのかもしれないが）大変になると思われる。 そこで、このプロトコルに利用されるパラメーターの制約とモジュラ数を利用してこのようなべき根を使うことなく計算を行うことを目標とする。 この証明などを考えるにあたって、@mimizunohimonoくんに協力していただいた。 予備知識 この記事を読むためには次のような知識が必要。 安全素数 素数$p, q$が次の式を満すとき、素数$p$を安全素数と言う。