千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2023年8月実施 専門 B10

标签：

• Greatest-Common-Divisor
• Quotient-Ring-Chinese-Remainder-Theorem-Decomposition-and-Unit-Group

Author

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

Description

(1) $p$ を奇素数、$a$ を $p$ と互いに素な平方剰余とする。$a$ の平方根が法 $p$ でちょうど二つあることを示せ。また $p\equiv3\pmod4$ ならば $a^{(p+1)/4}$ が平方根の一つであることを示せ。

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

(3) 関数 $s(n,a)$ は (2) の平方根四つを返し、平方剰余でなければ $(0,0,0,0)$ を返すとする。$s$ の多項式時間アルゴリズムが存在すれば、相異なる素数の積 $n$ を素因数分解する多項式時間アルゴリズムも存在することを示せ。

题目描述

(1) 证明奇素数模下非零平方剩余恰有两个平方根；当 $p\equiv3\pmod4$ 时给出并验证根 $a^{(p+1)/4}$。(2) 证明两个不同奇素数的积为模数时，可逆平方剩余恰有四个根。(3) 若能以多项式时间输出全部四根，证明可以以多项式时间分解这类模数。

Kai

(1)

一つの根を $r\ne0$ とすると、$x^2=r^2$ は $(x-r)(x+r)=0$ と同値である。$\mathbb F_p$ は体なので根は $r,-r$ のみで、$p$ が奇数だから相異なる。

また $a=r^2$ より Fermat の小定理から $a^{(p-1)/2}=r^{p-1}=1$。従って

$$\left(a^{(p+1)/4}\right)^2=a^{(p+1)/2}\equiv a\pmod p.$$

(2)

法 $p,q$ のそれぞれで二つの根を独立に選べる。中国剰余定理によって各組が法 $pq$ の一つの根に一意に対応するため、根は $2\cdot2=4$ 個である。

(3)

$a=1$ として $s(n,1)$ を計算する。四つの根のうち $x\not\equiv\pm1\pmod n$ を一つ選ぶ。中国剰余定理により $x$ は一方の素数を法として $1$、他方を法として $-1$ である。したがって

$$d=\gcd(x-1,n)$$

は $p,q$ のいずれか一方であり、$1<d<n$。$n/d$ と合わせて素因数分解を得る。根の列挙と Euclid の互除法は入力長 $\log n$ の多項式時間で実行できる。$n$ が偶数の場合は先に因子 $2$ を取り出せばよい。