Daily Plan

更新: 5/3/2025 字数: 0 字 时长: 0 分钟

• [ ]
• [ ]

Daily Study

更新: 5/3/2025 字数: 0 字 时长: 0 分钟

AI智能体 + 自动化测试/响应/攻击

https://zhuanlan.zhihu.com/p/676807643

Daily Problem

更新: 5/3/2025 字数: 0 字 时长: 0 分钟

SIQS（Self-Initializing Quadratic Sieve）是一种用于大整数分解的高效算法。它是基于二次筛选法（Quadratic Sieve，QS）的改进版本，特别适合分解百位数左右的整数。SIQS算法的基本流程如下：

1. 选择参数：算法开始时，首先选择合适的参数，包括筛选区间的大小和多项式的选择。
2. 选择平滑基：选择一个称为“平滑基”的小质数集合。平滑基的大小取决于要分解的数的大小。一个数如果可以完全由平滑基中的质数分解，则称该数为“B-平滑”。
3. 寻找多项式：SIQS使用一系列多项式来生成可以被筛选的数。这些多项式根据特定的方法选取，以确保它们产生的值有较高概率是B-平滑的。
4. 筛选：使用筛选过程来寻找B-平滑数。这一过程涉及在多项式生成的数值中寻找可以完全由平滑基中的质数分解的数。
5. 线性代数：一旦找到足够多的B-平滑数，算法将这些数的对数表示形式进行线性代数处理，以找出它们之间的关系。
6. 求解方程组：通过高斯消元或其他方法求解线性方程组，以寻找满足特定条件的数的集合。
7. 后处理：使用找到的数的集合来重构原始大整数的因子。这通常涉及取平方根和计算最大公约数（GCD）操作。
8. 验证和迭代：最后，算法会检验找到的因子是否正确。如果没有成功分解，算法可能需要调整参数并重新尝试。