因子分解方面进展

数论爱好者

想找一个因子分解的软件，有时找到也白枉然，技术门槛太高。
他们为何不做一个完整的软件包，一次性安装好后就能够用。
下面这个文章请AI翻译它的使用说明，末尾提到有些分解理论的书籍，感兴趣的可以读一下。

研究进展：
软件中提到：可以分解的数，限制在不超过 275 位十进制数字。即因子大小在137位左右。

Msieve：一个用于分解大整数的库
杰森•帕帕多普洛斯

简介
Msieve是我努力理解并优化如何使用最强大的现代算法来分解整数的成果。

这份文档对应的是Msieve库1.53版本。
不要期望仅仅通过阅读它就能成为分解整数的专家。
我列出了一份相对完整的参考资料清单，如果你想要将代码视为不仅仅是解决你的分解问题的黑箱，那么你可以也应该查阅这些资料。

Msieve的功能
分解是将大数表示为小数乘积的研究（一半是数学，一半是工程学，一半是艺术）。
如果我发现15=3*5，我就对数字15进行了一次整数分解。

随着要分解的数字变大，完成其分解的难度呈爆炸式增长，以至于你可以发明依赖分解难度的密钥代码，并合理期望你的加密数据保持安全。
有许多算法可以执行整数分解。

Msieve库几乎从头开始实现了其中的大多数算法，并依赖可选的外部库来完成其余部分。
所有输入都会使用试除法和PollardRho算法进行处理；如果结果小于25位数字，那么会使用微小的自定义例程进行分解。

对于更大的数字，代码会切换到GMP-ECM库并运行P-1、P+1和ECM算法，花费用户可配置的精力来执行。
如果这些方法不能完全分解输入数字，库就会切换到重型武器。

除非另有说明，Msieve会运行自我初始化的二次筛法算法，如果这还不能分解输入数字，那么你遇到的就是库的问题了。

如果你知道自己在做什么，Msieve还包含一个完整的数域筛法实现，这已经帮助完成了一些已知的最大规模的公开分解工作。
关于二次筛法实现的具体信息包含在Readme.qs中，而数域筛法变体的描述在Readme.nfs中。
可以提供给库处理的数字的最大位数在编译时就已经确定。
目前代码可以处理大约310位数字以内的数字；然而，你应该记住，我不期望该库能够仅靠自身完成大于约120位数字的分解。
较大尺寸的输入只能真正通过数域筛法来处理，而Msieve的NFS筛选代码在处理大于此规模的问题时，其效率和稳定性都不足以应对。
只要使用其他开源软件包中的NFS筛选工具，Msieve就能够完成非常大的NFS分解工作。

在编写Msieve时，我有以下几个目标：
要快速
我最初在2003年启动这个项目，是因为对高性能二次筛法实现的进展缓慢感到沮丧。
到2006年，msieve已经是最快可用的二次筛法，领先幅度很大。
像YAFU这样的库随后在二次筛法的性能提升上更加努力，而msieve的重点已经转向数域筛法。
要完整和全面
我尝试让库的尽可能多的部分达到行业领先水平。
NFS代码的一部分已经发展成为独立的研究平台。
要易于使用
唯一的输入是要分解的整数。
其他所有操作都会自动完成，尽管如果你知道如何操作，也可以进行一定程度的用户控制。
要免费（像啤酒一样免费）。
整个代码库都已发布到公有领域。
这对我来说是一个业余爱好，使用的人越多越好。
我已经尽一切努力避免使用那些在GPL许可证下的外部代码，而是选择使用更宽松的许可证。

如果你选择使用Msieve，请告诉我你的使用体验。
我欢迎错误报告、建议、优化、移植到新平台、抱怨、吹嘘，无论什么都可以。

获取Msieve我的网页（www.boo.net/~jasonp）曾经是Msieve源代码和二进制文件的主要分发场所。
随着代码库的增长和更多人自愿帮助，以该网页为基础变得越来越不方便，因此Msieve的开发和二进制版本现在都在Sourceforge（www.msieve.sourceforge.net）上提供。
源代码分发包中包含一个unixmakefile，如果你想要从源代码构建msieve，可以使用它。
如果你有MicrosoftVisualStudio2010，BrianGladman友好地提供了一组构建文件，可以生成Windows二进制文件。
使用Msieve为了避免混淆，我要说明，我交替地将两件事称为“Msieve”。
源代码分发包构建了一个名为“libmsieve.a”的独立静态库，用于实际执行分解工作，还构建了一个名为“msieve”的演示应用程序，使用该库。
库的接口在msieve.h中定义，非常轻量级，可以用于其他应用程序。
虽然演示应用程序是（稍微）多线程的，但库的大部分是单线程的，其所有状态都是传入的。
用于二次筛法和数域筛法的线性代数代码是多线程感知的，整个库应该是多线程安全的。
演示应用程序只有一个任务：作为传递要分解的整数的载体。
数字可以来自文本文件、重定向输入、命令行直接输入，或者可以手动逐个输入。
还支持批量输入，因此你可以将应用程序指向一个包含多个数字的文本文件，每个数字占一行。
默认情况下，所有输出都进入日志文件，摘要信息会显示在屏幕上。
完整的选项列表，可以尝试“msieve-h”。
从v1.08版本开始，msieve的输入可以是使用以下运算符的整数算术表达式：加、减（优先级最低）%整数取余/乘、整数除法^幂()分组（优先级最高）因此，例如：复制(10^53-1)/9给出的值是：复制11111111111111111111111111111111111111111111111111111表达式中使用的整数可以是任意长度，但所有中间结果和最终结果都限制在不超过275位十进制数字。
在分解整数时，库可以产生大量中间信息。
这些信息存储在一个或多个辅助保存文件中，保存文件可以用来重新启动中断的分解。
需要注意的是，分解一个整数后再分解另一个整数会覆盖第一个整数的保存文件。
所需的内存将取决于要分解的数字的大小和使用的算法。
如果运行二次筛法或数域筛法，内存需求在分解的后期会增加，因为那时所有中间结果都需要同时使用。
对于100位数字的二次筛法分解，大多数时间Msieve需要55-65MB内存，分解的最后阶段需要100-130MB。
数域筛法的最后部分可能使用难以置信的大量内存；例如，完成像RSA密钥这样的512位数字的分解需要大约2GB内存。

常见问题解答

Q.我想分解更大的数字。
难道Msieve不能解决比你说的更大的问题吗？Q.我正试图用Msieve破解我前女友的RSA密钥，但没有成功。
问题出在哪里？A.二次筛法确实不适合分解超过约110位数字的数字。
在现代快速CPU上，分解一个110位数字的二次筛法需要近120小时，而超过这个长度的时间会急剧增加。
如果你有非常大的分解需求，有几个软件包可以用来弥补Msieve的NFS代码中的低性能部分：复制-CADO-NFS（cado-nfs.gforge.inria.fr）是一个完整的NFS套件，包括几乎所有阶段的数域筛法的先进（或近乎先进）实现。
CADO-NFS的筛选工具生成的输出与GGNFS和Msieve兼容，因此你可以根据需要选择在NFS的某个阶段使用哪个软件包。
此外，CADO-NFS正在不断积极开发中，在我看来，它代表着高性能NFS社区的未来。
-GGNFS（www.sf.net/projects/ggnfs）有用于NFS筛选和NFS多项式选择的先进工具。
使用后者是可选的，因为Msieve实际上有非常好的NFS多项式选择代码，但前者是绝对必须的，如果你正在分解大于约95位数字的数字。
-Factor-by-GNFS（www.sf.net/projects/factor-by-gnfs）是一个较老的、不兼容的独立软件包。
请参阅后面的网络资源列表，了解Msieve曾经完成的最大的实际分解工作。

Q.你能使Msieve具备网络感知能力吗？能把它做成客户端-服务器模式吗？我能用互联网来分解数字吗？A.Msieve库的演示应用程序只是一个演示。
我不了解网络编程，也没有资格构建在互联网威胁面前安全的客户端-服务器应用程序。
如果你有这方面的知识，你可以在自己的代码中使用Msieve，我会尽我所能提供帮助。
该演示对于在小型私人局域网上有几台机器的人已经足够好，而这目前占了用户群的约100%。

Q.关于我的库实际工作原理的文档都在哪里？A.真的没有。
Msieve是一个业余时间项目，而我业余时间太少，如果我试图制作关于库内部的正式文档，那么我就没有时间实际去处理那些内部了。

代码中相对稳定的部分有广泛的内联文档，但我目前正在处理的部分几乎没有任何注释。
如果你有关于代码特定部分如何工作的具体问题，尽管问...Q.我如何修改Msieve使其在集群上工作？A.分布式筛选如此简单，以至于你不需要高性能并行编程技术或消息传递库来实现它。
如果你有幸拥有一个集群，那么集群自带的批处理调度系统足以实现集群感知筛选。
当然，如果你能获得如此强大的计算能力，你理应使用某种NFS软件包。

Q.你能修改Msieve使其在多核处理器上运行吗？A.如上所述，QS和NFS算法中真正密集的部分是筛选，而为这部分添加多线程是徒劳的。
与同时运行两个Msieve副本相比，你不会节省任何时间。
最后阶段确实可以从多线程中受益，而该部分的密集部分已经是多线程感知的。
这可以改进，但为库的更多部分添加多线程对我来说优先级较低。

Q.为什么将Msieve放入公有领域而不是使其成为GPL许可证下的软件？难道GPL许可证下的代码不会保护你的工作并鼓励贡献吗？A.Msieve是一个学习练习，而不是一个协作项目。
我没有期望其他开发者帮助，尽管许多人这样做了，我对此表示感谢。
至于保护，从这个代码中获得收入的唯一方法是用它来赢得分解竞赛。
虽然数域筛法可以赢得分解竞赛，但你个人没有资源去做这件事。
所以没有理由对这个代码设置许可限制。

Q.你的高精度库很糟糕。你为什么不使用GMP？
A.我知道它很糟糕。
使用GMP会让MSVC用户陷入困境，而且即使构建GMP也需要一个完整且最新的类Unix环境。
基于筛选的分解的妙处在于，对于大型分解，实际的高精度数学运算大约只占总运行时间的1%，所以实际上使用哪种低级高精度库并不重要。
实际上，代码中使用我自己的库的部分相当陈旧，而新开发需要GMP。
在修改NFS代码开始需要对非常大的数字进行算术运算之后，这变得必要。
我的一个最终目标是逐步淘汰（大部分）我自己的大数库，转而使用GMP。

致谢

随着代码变得更有用，有几个人对它进行了非常努力的推动。
汤姆•沃马克、格雷格•查尔德斯、布鲁斯•多德森、哈尔斯坦•汉森、保罗•莱兰德和理查德•瓦克巴思不断向Msieve的NFS后处理代码投掷巨大的尺寸问题，并且在我疯狂地试图跟上他们的步伐时非常有耐心。
如果你尝试使用NFS并且它能正常工作，即使其他程序失败，你主要要感谢这些人。
杰森•金投入了大量时间，极大地改进了NFS多项式选择。
杰夫•吉尔克里斯特做了大量测试、对64位Windows的反馈以及一般文档编写工作。
布莱恩•格拉德曼贡献了一个表达式评估器、VisualStudio构建系统、对NFS多项式选择器中数值积分的大量帮助以及各种可移植性修复。
汤姆•凯奇（愿他安息）发现了许多错误，并用早期版本的Msieve完成了数百次分解。
杰伊•伯格在早期版本的Msieve中对非常大的分解进行了大量实验。
www.mersenneforum.org的因式分解论坛的常客（尤其是杰斯、路易吉、山姆、丹尼斯、桑德、马克•R.、彼得•S.、杰夫•G.）也做了大量的因式分解工作。
亚历克斯•克鲁帕和鲍勃•西尔弗曼都贡献了有用的理论成果。
鲍勃的NFS筛选器代码对我理解事情的工作原理非常有帮助。
我感谢克利斯•卡德在我不得不在之前弄清楚NFS过滤的工作原理。
鲍勃•西尔弗曼、达里奥•阿尔珀恩尤其是比尔•哈特帮助完成了NFS平方根的工作。
'forzles'帮助改进了线性代数中的多线程。
福尔克•休夫纳和弗朗索瓦•格莱纽尔发现了早期版本中的几个严重错误。
J6M完成了AIX移植。
拉里•索尔在将GMP纳入代码方面做了大量工作，遗憾的是我不期望使用它。

网络因式分解资源

互联网上有许多地方深入探讨了因式分解算法的细节，但如果你有大型问题要解决，有几个地方非常方便。
开始因式分解的最佳去处是www.mersenneforum.org的因式分解子论坛；那里有一个繁荣的社区，人们致力于因式分解，包括不少专业人士。
一份很好的因式分解软件列表：http://mersenneforum.org/showthread.php?t=3255一份很好的互联网协调项目的列表，这些项目因式分解各种类型的数字，主要是数学上感兴趣的数字：http://mersenneforum.org/showthread.php?t=9611杰夫的因式分解程序指南是必读材料，如果你想用Msieve处理大尺寸问题：http://gilchrist.ca/jeff/factori ... _guide.htmlNFS@Home是由格雷格•查尔德斯运行的一个分布式计算项目，正在处理最大的公开因式分解项目。

RSALS是另一个处理稍小数字的分布式项目：http://escatter11.fullerton.edu/ ... c.unsads.com/rsals/二次筛法参考文献《质数：计算视角》，作者理查德•克兰德尔和卡尔•波默兰斯，是对二次筛法和计算数论中许多其他主题的极好介绍。
斯科特•康蒂尼的论文《用自初始化二次筛法分解大整数》是实现者的梦想；它填补了克兰德尔和波默兰斯在筛选过程细节上的空白。
万巴赫和韦蒂格1995年的论文《块筛选算法》介绍了使筛选缓存友好的方法。
Msieve使用的算法非常不同（更高效），但你应该先尝试理解这些算法。
伦斯特拉和马纳塞1994年的论文《用两个大质数进行因式分解》详细描述了是Msieve组合阶段核心的循环查找算法。
关于生成树和循环查找的更多背景信息可以在曼努埃尔•胡贝尔2003年的论文《图的稀疏循环基的算法实现》中找到。
这篇论文对我来说是将点连接起来（双关）的关键。
关于SQUFOF有三种广泛可用的描述。
一种入门级的介绍是汉斯•里斯尔在《质数和计算机分解方法》一书中题为“Shanks'FactoringMethodSQUFOF”的部分。
更高级的是杰森•高尔（JasonGower）的博士论文《平方形式分解》（这是我实现该算法时使用的参考）。
亨利•科恩的书（下面提到）也对SQUFOF有深入的讨论。
丹尼尔•尚克斯（DanielShanks）在我还是马里兰大学生的时候是那里的教授，他的工作让我对数论和计算机编程产生了兴趣。
我非常希望在他1996年去世之前能见到他。
布兰特•库罗夫斯基1998年的论文《多多项式二次筛法：一个平台无关的分布式应用》是我能找到的唯一描述Knuth-Schroeppel乘数算法的参考。
戴维斯和霍尔德里奇1983年的论文《用二次筛法算法进行因式分解》对QS的工作原理给出了令人惊讶的理论处理。
阅读它感觉像是发现某种被遗忘的进化分支，与常规的QS实现方式截然不同。
彼得•蒙哥马利的论文《用于在GF(2)上查找依赖关系的块Lanczos算法》彻底改变了因式分解行业。
仅凭这篇论文还不足以实现他的算法；你真的需要其他人的实现来填补几个关键的空白。
迈克尔•彼得森最近的论文《用于求解大型二进制系统的并行块Lanczos算法》对块Lanczos算法进行了有趣的重新表述，并提供了许多提高性能的技巧。
卡尔托芬的论文《有限域中受阻迭代稀疏线性系统求解器》是对蒙哥马利原始块Lanczos论文的一个很好的总结。
古普塔的IBM技术报告《直接求解非对称稀疏线性方程组的最新进展》在NFS上下文中没有相关内容，但其中可能有一些对因式分解人员有用的材料。
数域筛法参考文献马修•布里格斯的《数域筛法引论》是一篇非常好的入门文章；它在某些地方比克兰德尔和波默兰斯的书更深入，而在其他地方则更浅显。
迈克尔•凯斯的《数域筛法初学者指南》在各方面都有更多细节，并开始涉及高级内容。
佩尔•莱斯利•詹森的论文《整数分解》包含了许多其他参考资料所缺乏的NFS初级细节。
彼得•史蒂文哈根的《数域筛法》是对该算法的快速介绍。
史蒂文•拜恩斯的《数域筛法》也是一个很好的简化介绍。
伦斯特拉、伦斯特拉、马纳塞和波拉德的论文《数域筛法》对于历史兴趣来说很不错。
《1024位RSA模数的因式分解估计》应该是任何认为分解商业RSA密钥是一个有趣且容易的项目的必读材料。
《关于1024位RSA和160位椭圆曲线密码学的安全性》是2010年代对前一篇论文的更新。
布莱恩•墨菲的论文《数域筛法算法的多项式选择》非常棒。
它对一个几乎没有文献的课题进行了详尽的讨论。
托尔斯滕•克莱因容的论文《关于数域筛法多项式选择的一些改进》详细解释了自墨菲论文以来在NFS多项式选择方面的许多改进。
克莱因容关于NFS多项式选择的最新算法思想记录在2008年CADO分解研讨会：http://cado.gforge.inria.fr/workshop/abstracts.html我的演讲《高性能优化的GNFS多项式》详细介绍了我在NFS多项式选择方面的研究：http://event.cwi.nl/wcnt2011/program.html杰森•高尔的论文《数域筛法多项式的旋转和平移》描述了一些非常有前景的多项式生成过程改进。

据我所知，还没有人实际实现了这些改进。
D.J.伯恩斯坦有两篇即将发表的论文和几张幻灯片，涉及多项式选择过程的一些改进，我迫不及待地想实现它们。
青木和上田的论文《使用桶排序的筛选》描述了现代筛选器必须具备的内存优化，才能快速运行。
多德森和伦斯特拉的论文《NFS用四个大质数：一次爆炸性的实验》是第一次意识到也许人们应该在NFS中每边使用两个大质数。
弗兰克和克莱因容的论文《连分数和格筛选》是关于高性能格筛选技术的唯一现代参考资料。
鲍勃•西尔弗曼的论文《SNFS的最优参数化》包含了许多关于构建线性筛选器的参数选择和实现细节。
埃克尔坎普的论文《因式分解方法中的筛选量》详细讨论了NFS后处理的模拟。
卡瓦拉尔的论文《数域筛法中的过滤策略》是关于NFS后处理的唯一文档。
我的演讲《数域筛法的自调谐过滤实现》描述了Msieve过滤代码的研究。
丹尼和穆勒的扩展摘要《数域筛法中复合关系的约简》是早期的NFS过滤尝试，现在几乎被遗忘了，但他们的技术可以建立在普通的NFS过滤之上。
蒙哥马利的论文《代数数平方根的算法》描述了NFS平方根阶段的标准算法。
阮的论文《数域筛法的蒙哥马利式平方根》也是该主题的标准内容；我没有仔细阅读这篇论文和前一篇，因为传统的NFS平方根算法对我来说仍然是一个完全的谜。
大卫•尹的论文《使用p-adic构造的代数算法》为msieve使用的单纯形暴力NFS平方根算法背后的数学提供了许多有用的理论见解。
迪西奥•路易兹•加佐尼•菲略补充：论文集《数域筛法的发展》（Springer讲座笔记数学1554）应该绝对是必读材料——不幸的是，它非常难以获得。
它在亚马逊上总是被标记为“特殊订单”，我曾认为我不应该尝试订购，因为他们会在几周后回复我说这本书没有货。
有一天我非常幸运地发现有一本有货，于是我立即订购了。
我再次强烈推荐这本书；我读过很多关于NFS的文献，但第一次真正理解它是在阅读了这里的论文之后。
现代的NFS讲解只展示了当前实现的算法，有时某些事情远非显而易见。
而这本书作为NFS的历史记录，展示了从约翰•波拉德最初的SNFS工作开始的进步，那些看起来不合适的事情开始变得合理。
特别是理解SNFS的初始公式，而不使用字符列。
[注：这本书已经重印，并且至少可以在bn.com上买到。
-JP]像往常一样，亨利•科恩的书《计算代数数论课程》中可以找到非常代数化和深入的讲解。
当然，这本书绝非适合胆小的人。
它也相当过时，例如SNFS部分是基于“旧”的（没有字符列的）SNFS，但它深入探讨了单纯形暴力NFS平方根算法背后的代数。
为了理解NFS，需要大量关于代数和代数数论的背景知识。
我发现了一本很好的代数数论入门书，哈里•波拉德和哈罗德•戴蒙德的《代数数论》。
这是一本老书，没有被现代书籍中过多的抽象所污染。
它帮助我很多去掌握代数概念。
科恩的书对新手来说很难，但随着你深入这个主题，它会变得出奇地有用，而算法方面的内容当然也有帮助。
至于论文：道格拉斯•维德曼的《有限域上稀疏线性方程的求解》提出了矩阵步骤的一种替代方法。

块Lanczos可能更好，但也许维德曼的方法有一些用途，例如开发一个令人尴尬地并行的线性代数算法（在我看来，这是当前NFS研究的圣杯）。

数论爱好者

上面部分链接已经失效。
软件在下面这个网页下载：
https://sourceforge.net/projects/msieve/
我下载了，但不能运行，可能其它数据库没有安装。

nyy

这软件我用过