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

标签：

• Greatest-Common-Divisor
• Prime-Factorization
• One-Way-Functions-and-Reductions

Author

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

Description

$x\in\{0,\ldots,n-1\}$ が $x^2\equiv a\pmod n$ を満たすとき、$x$ を法 $n$ における $a$ の平方根と呼ぶ。

(1) 奇素数 $p$ に対して、法 $p$ での $1$ の平方根は $1,p-1$ のみであることを示せ。

(2) 異なる奇素数 $p,q$ と $n=pq$ に対して、法 $n$ での $1$ の平方根は四つあることを示せ。

(3) $n$ からこの四つの平方根を全て出力する多項式時間アルゴリズムが存在すれば、$n$ の素因数分解を求める多項式時間アルゴリズムが存在することを示せ。最大公約数の計算が多項式時間で行えることは用いてよい。

题目描述

模 $n$ 下的平方根取代表元 $0\le x<n$。

(1) 证明对奇素数 $p$，$x^2\equiv1\pmod p$ 只有 $1,p-1$ 两个解。

(2) 当 $n=pq$，$p,q$ 为不同奇素数时，证明 $1$ 有四个模 $n$ 平方根。

(3) 若能在多项式时间内由 $n$ 求出全部四个平方根，证明也能在多项式时间内分解 $n$。可以使用最大公约数的多项式时间算法。

Kai

(1)

$x^2\equiv1\pmod p$ なら $p\mid(x-1)(x+1)$。$p$ が素数なので $x\equiv1$ または $-1\pmod p$。$p$ は奇数なので両者は異なり、実際にどちらも解である。

(2)

中国剰余定理により、法 $pq$ の解は

$$(x\bmod p,x\bmod q)=(1,1),(1,-1),(-1,1),(-1,-1)$$

の四つの組に一対一に対応する。従って平方根はちょうど四つ。

(3)

仮定したアルゴリズムで平方根を求め、$x\notin\{1,n-1\}$ を一つ選ぶ。この $x$ の符号は法 $p$ と法 $q$ で異なる。従って

$$d=\gcd(x-1,n)\in\{p,q\},\qquad 1<d<n.$$

$d$ と $n/d$ を出力すれば素因数分解となる。平方根の取得、比較、最大公約数および除算はいずれも入力長 $\log n$ の多項式時間で行える。