千葉大学理学研究科基盤理学専攻数学・情報数理学コース 2016年8月実施専門 B11

标签：

Author

祭音Myyura (co-authored with GPT 6 Astra)

異なる奇素数 $p,q$ に対し $n=pq$ とし、 $e_1,e_2$ は相異なる素数で、どちらも $\varphi(n)$ と互いに素とする。 $f(x,e)=x^e\bmod n$ と定める。

$0<m<n,\gcd(m,n)=1$ のとき、 $n,e_1,e_2,f(m,e_1),f(m,e_2)$ を入力として $m$ を出力する多項式時間アルゴリズムが存在することを示せ。互いに素な整数の逆元を多項式時間で計算できることは用いてよい。

令 $n=pq$ ，其中 $p,q$ 为不同奇素数。 $e_1,e_2$ 为不同素数，均与 $\varphi(n)$ 互素。设 $0<m<n$ 且 $\gcd(m,n)=1$ 。

证明：由 $n,e_1,e_2,m^{e_1}\bmod n,m^{e_2}\bmod n$ 可以在多项式时间内恢复 $m$ 。允许使用模逆元的多项式时间算法。

暗号文を $c_1=m^{e_1}\bmod n,c_2=m^{e_2}\bmod n$ とする。相異なる素数 $e_1,e_2$ は互いに素なので、拡張 Euclid 法で

ue_1+ve_2=1

を満たす整数 $u,v$ を求める。 $m$ と $n$ は互いに素だから $c_1,c_2$ も法 $n$ で可逆であり、負の冪は模逆元の冪として計算できる。

そこで

M=c_1^u c_2^v\bmod n

を $0\le M<n$ の代表元として出力する。すると

M\equiv m^{ue_1+ve_2}=m\pmod n.

$m$ も同じ範囲にあるので $M=m$ 。

拡張 Euclid 法、模逆元、二進法による繰り返し二乗法はいずれも入力のビット長の多項式時間で実行できる。従って求めるアルゴリズムは多項式時間である。