十三年后，用Perl分解整数
内容提要
Perl模块Math::Prime::Util::GMP将升级至0.55版，以新的自初始化二次筛法（SIQS）取代旧实现，使大整数分解更快、更省内存且支持更大规模。作者基于Hugo van der Sanden的改进版开发出独立程序msiqs，性能可与YAFU等专业软件竞争，八线程分解RSA-100约需4分43秒。Perl接口保持不变，模块线程安全。
延伸解读
Perl用户无需改代码即可受益
Math::Prime::Util::GMP 0.55 将旧二次筛法替换为新的自初始化二次筛法（SIQS），对适合该算法的大整数，分解速度更快、内存占用更低，且能处理更大规模。Perl 接口保持不变，用户仍可通过 factor() 直接传入十进制字符串，无需构造 Math::BigInt 对象。模块自动使用 GMP 后端，升级后现有代码即可获得性能提升。
从模块改进到独立程序msiqs
作者将新实现独立为 msiqs，一个基于 C/GMP 的库和命令行程序，支持多线程和断点续算。在 2021 款 M1 Pro 笔记本上，八线程分解 RSA-100 约需 4 分 43 秒。与 YAFU 等专业软件相比具有竞争力，尽管 msiqs 没有手写汇编或显式 SIMD 代码，而 YAFU 在 x86 上有针对性优化。
线程模型的选择与限制
为避免混合 Perl 线程和 C pthreads，作者将 Perl 模块设计为串行但线程安全。用户若需并行，可通过 Perl 线程或 MCE 运行独立任务。这意味着模块本身不利用多核加速单次分解，但多任务场景下仍可安全并发。独立程序 msiqs 则直接支持多线程，适合需要单次分解加速的用户。
开发过程中的协作与工具变化
Hugo van der Sanden 的 SIMPQS2 改进（合并部分结果、改进最终阶段求解器、降低内存）成为重要开发检查点，虽未进入正式发布版。作者还大量使用 OpenAI Codex 进行算法讨论、实现、代码审查、调试和实验，这与以往开发流程有很大不同。msiqs 和 YAFU 均在活跃开发中，后续比较可能变化。
Q&A
Math::Prime::Util::GMP 0.55 版本对大整数分解有什么改进？
0.55 版本用新的自初始化二次筛法（SIQS）替换了旧的二次筛法实现，使得对于难以分解的数字，分解速度显著加快、内存占用更少，并且能处理更大规模的整数。
如何在 Perl 中使用 Math::Prime::Util 来分解一个大整数？
可以使用 Math::Prime::Util 的 factor 函数，直接传入大整数的十进制字符串即可，无需构造 Math::BigInt 对象。例如：use Math::Prime::Util qw(factor); my $n = "861718837045131266076605675795055735226483972739042530561207"; print join(" * ", factor($n)), "\n"; 如果安装了 GMP 后端，模块会自动使用它。
msiqs 是什么？它与 YAFU 相比性能如何？
msiqs 是一个独立的整数分解程序，包含 C/GMP 库和命令行工具，支持多线程和断点续算。它的性能可与专业软件 YAFU 竞争，例如在 2021 款 M1 Pro 笔记本上使用 8 个线程分解 RSA-100（100 位数字）约需 4 分 43 秒。
新的 SIQS 实现与旧的二次筛法相比有哪些优势？
新的 SIQS 实现覆盖了旧实现（包括 TinyQS 和 SIMPQS）的适用范围，并且在旧实现的有效范围内速度更快，还能处理更大的输入。同时，内存使用也更少。
Hugo van der Sanden 对新的分解实现有什么贡献？
Hugo van der Sanden 在 2024 年提交了改进版 SIMPQS2，解决了作者自 2013 年以来关注的问题：合并有用的部分结果、改进最终阶段的求解器以及降低内存使用。他的工作成为新 SIQS 开发的重要检查点，尽管 SIMPQS2 从未出现在正式发布的模块版本中。
Perl 模块的线程安全性如何？如何并行运行多个分解任务？
Perl 模块本身是串行但线程安全的。你可以使用 Perl 线程或 MCE 来并发运行独立的分解任务，而不是混合使用 Perl 线程和 C pthreads。
