二次篩
概要
$ n の因数を求める問題に取り組む。
そのために $ x \neq \pm y~~(\text{mod}~~n) かつ $ x^2 = y^2~~(\text{mod}~~n) を満たす整数 $ x, y を求める。
関数 $ Q(x) に注目する。
$ Q(x) = (x + \lfloor \sqrt{n} \rfloor)^2-n
$ Q(x_1)Q(x_2)\dots Q(x_k) が平方数となるような $ x_1,x_2,\dots ,x_k を見つけることを目標とする。
参考文献