Quadratic residuosity problem - crypto-writeup-public

和訳すると「平方剰余問題」？

ある $a, N \in \mathbb{Z}$ が与えられたときに $a$ が $n$ の平方剰余か、すなわち、 $a \equiv b^2 \mod N$ なる $b$ が存在するかを判定する問題。通常 $N = pq$ で、 $p, q$ 不明

なんか難しいらしい。（直感的には平方剰余である数とそうでない数の数に偏りがあるような気がするが、その実1 : 1）

当然 $a, p$ が与えられてquadratic residueかどうかを見るのは容易なので、Nが素因数分解できればこの問題は解ける。( $\left(\frac{a}{p}\right) = 1, \left(\frac{a}{q}\right) = 1$ のとき $\left(\frac{a}{N}\right) = 1$ なので（これはjacobi記号

$QR * QR = QR$

$QR * QNR = QNR$

$QNR * QNR = QR$