C或C++:用于分解整数的库？

Question

似乎有几种真正快速的素数因子分解算法(一种看似理想的是二次筛分).但是,为了简单起见,我想使用现成的库,而不是自己(可能很差)实现.

我需要能够有效地计算多达15位的整数.正因为如此,我不找那一定尺度渐近最好的,因为我们可以假设被分解的数字是不到10算法¹⁵.

我已经看过维基百科的Quadratic Sieve页面上列出的一些实现.但是,有些实现似乎没有得到很好的维护; 有些人没有文件; 等等!我检查了一些着名的库,比如Boost,是否有分解方法,但似乎没有.

任何人都可以推荐符合上述标准的图书馆吗？

Answer 1

查看Jason Papadopoulos 编写的用于分解大整数的MSIEVE库。

Msieve 是我努力理解和优化如何使用最强大的现代算法分解整数的结果。

本文档对应于 Msieve 库的 1.46 版本。不要指望仅仅通过阅读它就能成为保理专家。我提供了一个相对完整的参考列表，如果您希望将代码视为不仅仅是一个黑匣子来解决因式分解问题，您可以并且应该查找这些参考资料。