初来科锐学习，在某次看雪CTF赛中，遇到RSA算法加密，而RSATool无法快速的对上百位的大数进行分解，事后通过老师的指导，了解到看雪工具栏版块有分解大整数的工具PPSIQS，好奇其中原理，于是查阅相关资料，了解到这款工具利用的是二次筛法算法分解的大整数。特别感谢钱老师，姚老师的悉心教导，于是写下这篇笔记以记录心得。

       我们知道很多密码系统的安全性依赖于大整数因子分解问题的困难性。比如RSA加密算法，其破解的核心其实就是分解其中的大数，找到其两个质因子。
对于一般的数位位数较小的情况（几十bit的数量级），常用的分解整数的方法是试除法。而当数位达到百bit数量级时，试除法因为其效率低下，明显不适合大数分解。
解决较大的整数分解问题，有椭圆曲线算法、特殊数域筛法、二次筛法等，而二次筛法是500bit及以下整数分解时，已知的最快算法。

       我自己没有找到很好的介绍二次筛法中文资料。因此作文一篇，在此简单介绍下二次筛法。由于无法输入数学公式，部分内容以截图的形式呈现。

       了解二次筛法前，需要先了解下费马分解法，因为二次筛法是来源于费马分解法的。

       在费马分解法发明之前的很长一段世间，人们只会使用试除法分解大数，而费马分解法的发明，使得分解大数效率大大提高。费马分解法的具体操作是怎样的呢？

       其实很简单，以分解大数N为例，在费马分解法中，我们并不直接去找N的质因子。而是试图先找一对具有以下关系的平方数：

如果能找到以上关系的x、y，那我们可以继续变形得到：

       这相当于说明(x+y)*(x-y)能够被N整除，那么(x-y)中一定有与N共有的公约数。通过欧几里得算法，可以很快地找到(x-y)与N的最大公约数，自然就是N的分解了。

       所以，在费马分解法的指导下，我们的问题转变了，我们只需要找到 x^2≡y^2 (mod N) 关系即可。然而，如果盲目去尝试，这样的x,y也是很不容易找到的……

       二次筛法的发明，就是帮助我们有步骤地、有效地找到满足以上条件的x、y关系。

       在二次筛法中，我们先构造一个二次函数：

       其中x是从0开始的任意整数。之所以构造一个这样的二次函数，是因为它天然地满足一些我们期待的要求（可以帮助我们进行N分解），理由如下：

       以上式子的右边，已经是一个平方数了，所以，我们的问题进一步简化和明确，只需要Q(x)是一个（模N的）平方数，即可用费马分解法分解。

       如何比较高效地寻找Q(x)，确保它是一个平方数呢？联想到所有的整数都可以分解成质数的幂的乘积形式。所谓平方数，其实就是所有质因子的幂是偶数的的情况（如400 = 2^4 * 5^2）。

       在二次筛法中，我们并不试图去直接找满足平方数要求的Q(x）,而是先找一系列能够被某个质数集合完全分解的数，再由这些数，拼凑出Q(x)来。
而“某个质数集合”，称为“因子基”（Factor Base）。能够被因子基中的质数完全分解的数，我们称为其是“光滑的”（Smoothness）。

       比如，我们选在{2, 5}作为因子基，则400相对于这个因子基就是光滑的，而30相对于这个因子基就是不光滑的。

       这时，右边已经符合平方数，而左边，因为Q(xi)都是光滑的，我们只要选择适合的Q(xi)相乘，确保乘积结果的所有质因子的幂是偶数即可，这个过程本质上是解一个线性方程的过程。

        我们来简单看一下利用二次筛法分解N = 15347。

       通过上表我们不难看出很明显Q(3)直接满足条件。那么我们就有：

       一般运气没那么好，并不能直接得到Q(x)，而是构造来的，比如，我们剔除掉Q（3），用剩余几个Q（x_i）来构造。剩余几个Q（x_i）的指数矩阵S：

       我们想要找到矩阵R：

       解以上线性方程得到：

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)