题目简述：若你获得“超能力”：固定$n$，对任意$a$，可以快速求出$x in [0, n)$（若存在），使得$x^2 equiv a pmod n$，若存在多个$x$满足条件，则返回其中一个（对固定的$a$返回固定的$x$）。给定$n leq 2^{1024}$，求其质因数分解。保证$n$是至多$10$个不同质数之积。
解：code
令$f(a)$表示通过“超能力”获得的$x$（若存在），使得$x^2 equiv a pmod n$。
随机选择$x in [1, n-1]$，令$y = f(x^2)$。
设$n = p_1 p_2 dots p_k$，其中$p_1, p_2, dots, p_k$是互不相同的质数，由中国剩余定理（Chinese Remainder Theorem）得
$$ y^2 equiv x^2 pmod n Longleftrightarrow egin{cases} y^2 equiv x^2 pmod {p_1} \ vdots \ y^2 equiv x^2 pmod {p_k} end{cases} $$
对每个质数$p_i$，$y^2 equiv x^2 pmod {p_i}$的解为$y equiv x pmod {p_i}$或$y equiv -x pmod {p_i}$。因此
$$ f(x^2) equiv pm x pmod {p_i}. $$
于是，
$$ Pr Big[ f(x^2) equiv x pmod{p_i} Big| p_i ot| x Big] = frac 1 2, $$
再由中国剩余定理可得
$$ Pr Big[ f(x^2) equiv x pmod n Big| gcd(x,n) = 1 Big] = frac 1 {2^k}. $$
也即，若$x$与$n$互质，即$gcd(n, x) = 1$，则我们可以通过“超能力”得到$y eq x$的概率为$1 - 2^{-k}$。
注：若把$x$与$n$互质的条件去掉，则类似可有
$$ Pr Big[ f(x^2) equiv x pmod n Big] leq frac 1 2. $$
假设得到了一个$y = f(x^2) eq x$，则$x^2 equiv y^2 pmod n$，则必定有$n = n_1n_2$，其中$n_1, n_2 > 1$，使得$x equiv y pmod {n_1}$但$x otequiv y pmod {n_2}$，即$n_1 | (x-y)$但$n_2 ot| (x-y)$，又$gcd(n_1,n_2) = 1$，故$gcd(n, x-y) = n_1$。此时，我们已将$n$分解为更小的两个数的乘积。重复这个操作$k-1$次，便能得到$n$的质因数分解。
注：由于对称性，$gcd(n, x-y)$与$gcd(n, x+y)$在概率上性质是一样的。在$n$分解成若干个正整数之积后，以上分析依然适用于分解$n$的因子的情形。