c++ - C 或 C++：用于分解整数的库？

Question

似乎有几种非常快速的素数分解算法（看起来理想的一种是二次筛选）。但是，为了简单起见，我不想自己制作（可能很差）实现，而是使用现成的库。

我需要能够有效地分解最多 15 位的整数。正因为如此，我不是在寻找必须渐近最佳缩放的算法，因为我们可以假设被分解的数字小于 10 ¹⁵。

我已经查看了Wikipedia 的 Quadratic Sieve 页面上列出的一些实现。然而，一些实现似乎并没有得到很好的维护。有些没有文件；等等！我检查了一些著名的库，例如 Boost，是否有分解方法，但它们似乎没有。

谁能推荐一个符合上述标准的图书馆？

Answer 1

查看Jason Papadopoulos 的MSIEVE库以分解大整数。

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

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

Answer 2

GMP-ECM怎么样？