Quadratic Sieve
二次筛法通过寻找 x 使 x^2≡y^2 (mod n)，则 gcd(x±y,n) 可能给出因子，是 100 位以下最快分解法。
用途
中等位数（~100 位）整数因子分解的最快算法。
机制
找多组 x_i 使 x_i^2 mod n 为 B-平滑，用线性代数（GF(2)）组合使平方乘积为完全平方。组合得 X^2≡Y^2 (mod n)，gcd(X±Y,n) 可能非平凡。
用例
- 整数因子分解
- 密码分析
- 数论算法
二次筛法通过寻找 x 使 x^2≡y^2 (mod n)，则 gcd(x±y,n) 可能给出因子，是 100 位以下最快分解法。
中等位数（~100 位）整数因子分解的最快算法。
找多组 x_i 使 x_i^2 mod n 为 B-平滑，用线性代数（GF(2)）组合使平方乘积为完全平方。组合得 X^2≡Y^2 (mod n)，gcd(X±Y,n) 可能非平凡。