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

Question

似乎有几个非常快的质因数分解算法（一个看起来很理想的是二次筛法）。然而，我不想自己编写（可能很差）的实现，而是希望使用现成的库来简化操作。

我需要能够高效地分解多达15位数字的整数。因此，我不是在寻找渐进最优的算法，因为我们可以假设要分解的数字小于10的15次方。

我已经查看了维基百科的二次筛法页面上列出的一些实现。但是，其中一些实现似乎没有得到很好的维护；一些实现没有文档等等！我检查了一些知名的库，例如Boost，但它们似乎没有质因数分解方法。

有人可以推荐符合上述标准的库吗？

- PythonPower

---

要求我们推荐或寻找书籍、工具、软件库、教程或其他外部资源的问题不适合在 Stack Overflow 上讨论，因为它们往往会吸引主观性答案和垃圾信息。相反，请描述问题以及已经采取的解决措施。 - genpfault

这样的问题应该在[softwarerecs.se]上。 - phuclv

这个非常有趣的数学问题是否有重新开放的机会？我想不仅仅建议使用库，还要编写自己的代码，并附上完整的研究和解释。 - Arty

Answer 1

请查看由Jason Papadopoulos开发的MSIEVE库，用于分解大整数。

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

本文档对应Msieve库的1.46版本。阅读本文档并不会让您成为分解专家。如果您想将代码视为不仅仅是解决分解问题的黑盒子，则应该查阅我包含的相对完整的参考列表。

- Nick Dandoulakis

---

再次强调，我找不到任何真正的文档。我不确定它如何与我的程序集成，因此也不确定它是否能够正常工作！ - PythonPower

好的，我说过你可能会... :) 我也对因数分解很感兴趣。因数分解是一个困难的问题，可能很难找到一个记录和快速的库。 - Nick Dandoulakis

我同意，特别是在项目文档和速度几乎是互相排斥的情况下。 ;) - PythonPower

链接的论坛：http://mersenneforum.org/forumdisplay.php?f=19 看起来相当活跃 - 我建议在那里寻求帮助，并可能指回这个主题。 - John Carter

好的，我已经询问了...显然需要一位管理员检查我的第一篇帖子，所以当它被批准后，我会发布链接。 - PythonPower

@PythonPower 还可以吗？ :P - Jacob Akkerboom

Answer 2

将以下文本翻译成中文：

在C语言中，要对整数进行因式分解，可以尝试使用一种概率方法：

我的建议标题：

#include <stdlib.h>
#include <sys/time.h>

typedef unsigned long long int positive_number; // __uint128_t
static inline positive_number multiplication_modulo(positive_number lhs, positive_number rhs, positive_number mod);
static int is_prime(positive_number n, int k); // prime checker
positive_number factor_worker(positive_number n);
positive_number factor(positive_number n, int timeout);

因为有超时，分解过程被管理器管理：

double microtime() {
    struct timeval time; gettimeofday(&time, 0);
    return (double) time.tv_sec + (double) time.tv_usec / 1e6;
}

// This is the master function you can call, expecting a number and a timeout(s)
positive_number factor(positive_number n, int timeout) {
    if (n < 4) return n;
    if (n != (n | 1)) return 2;
    double begin = microtime();
    int steps = 8; // primality check iterations
    positive_number a, b;
    for (a = n >> 1, b = (a + n / a) >> 1; b < a; a = b, b = (a + n / a) >> 1, ++steps);
    if (b * b == n) return b ; // we just computed b = sqrt(n)
    if (is_prime(n, steps)) return n;
    do { positive_number res = factor_worker(n);
        if (res != n) return res;
        if (++steps % 96 == 0 && is_prime(n, 32)) return n ; // adjust it
    } while (microtime() - begin < timeout);
    return n;
}

"乘法器" 助手因为计算是模 N 进行的:

static inline positive_number multiplication_modulo(positive_number lhs, positive_number rhs, positive_number mod) {
    positive_number res = 0; // we avoid overflow in modular multiplication
    for (lhs %= mod, rhs%= mod; rhs; (rhs & 1) ? (res = (res + lhs) % mod) : 0, lhs = (lhs << 1) % mod, rhs >>= 1);
    return res; // <= (lhs * rhs) % mod
}

这是英语文本，已经是中文了。它的意思是：“当然，这是“质数检查器”助手：”。

static int is_prime(positive_number n, int k) {
    positive_number a = 0, b, c, d, e, f, g; int h, i;
    if ((n == 1) == (n & 1)) return n == 2;
    if (n < 51529) // fast constexpr check for small primes (removable)
        return (n & 1) & ((n < 6) * 42 + 0x208A2882) >> n % 30 && (n < 49 || (n % 7 && n % 11 && n % 13 && n % 17 && n % 19 && n % 23 && n % 29 && n % 31 && n % 37 && (n < 1369 || (n % 41 && n % 43 && n % 47 && n % 53 && n % 59 && n % 61 && n % 67 && n % 71 && n % 73 && ( n < 6241 || (n % 79 && n % 83 && n % 89 && n % 97 && n % 101 && n % 103 && n % 107 && n % 109 && n % 113 && ( n < 16129 || (n % 127 && n % 131 && n % 137 && n % 139 && n % 149 && n % 151 && n % 157 && n % 163 && n % 167 && ( n < 29929 || (n % 173 && n % 179 && n % 181 && n % 191 && n % 193 && n % 197 && n % 199 && n % 211 && n % 223))))))))));
    for (b = c = n - 1, h = 0; !(b & 1); b >>= 1, ++h);
    for (; k--;) {
        for (g = 0; g < sizeof(positive_number); ((char*)&a)[g++] = rand()); // random number
        do for (d = e = 1 + a % c, f = n; (d %= f) && (f %= d););
        while (d > 1 && f > 1);
        for (d = f = 1; f <= b; f <<= 1);
        for (; f >>= 1; d = multiplication_modulo(d, d, n), f & b && (d = multiplication_modulo(e, d, n)));
        if (d == 1) continue;
        for (i = h; i-- && d != c; d = multiplication_modulo(d, d, n));
        if (d != c) return 0;
    }
    return 1;
}

因式分解“worker”，一次调用不能保证成功，它是一个概率性的尝试。

positive_number factor_worker(positive_number n) {
    size_t a; positive_number b = 0, c, d, e, f;
    for (a = 0; a < sizeof(positive_number); ((char*)&b)[a++] = rand()); // pick random polynomial
    c = b %= n;
    do {
        b = multiplication_modulo(b, b, n); if(++b == n) b = 0;
        c = multiplication_modulo(c, c, n); if(++c == n) c = 0;
        c = multiplication_modulo(c, c, n); if(++c == n) c = 0;
        for (d = n, e = b > c ? b - c : c - b; e; f = e, e = multiplication_modulo(d / f, f, n), e = (d - e) % n, d = f);
        // handle your precise timeout in the for loop body
    } while (d == 1);
    return d;
}

使用示例：

#include <stdio.h>

positive_number exec(positive_number n) {
    positive_number res = factor(n, 2); // 2 seconds
    if (res == n) return res + printf("%llu * ", n) * fflush(stdout) ;
    return exec(res) * exec(n / res);
}

int main() {
    positive_number n = 0, mask = -1, res;
    for (int i = 0; i < 1000;) {
        int bits = 4 + rand() % 60; // adjust the modulo for tests
        for (size_t k = 0; k < sizeof(positive_number); ((char*)&n)[k++] = rand());
        // slice a random number with the "bits" variable
        n &= mask >> (8 * sizeof (positive_number) - bits); n += 4;
        printf("%5d. (%2d bits) %llu = ", ++i, bits, n);
        res = exec(n);
        if (res != n) return 1;
        printf("1\n");
    }
}

你可以把它放进一个名为primes.c的文件中，然后编译并执行：

gcc -O3 -std=c99 -Wall -pedantic primes.c ; ./a.out ;

此外，128位整数GCC扩展 扩展可能可用。

示例输出：

  358205873110913227 =    380003149 * 942639223    took 0.01s
  195482582293315223 =    242470939 * 806210357    took 0.0021s
  107179818338278057 =    139812461 * 766597037    took 0.0023s
   44636597321924407 =    182540669 * 244529603    took 0s
  747503348409771887 =    865588487 * 863578201    took 0.016s

// 128-bit extension available output :
170141183460469231731687303715506697937 =
13602473 * 230287853 * 54315095311400476747373 took 0.646652s

信息：这个C99 100行概率分解软件建议基于米勒-拉宾素性测试，然后是波拉德的rho算法。和你一样，我最初的目标只是分解一些小的long long int。根据我的测试，它对我来说运行得足够快，即使是一些更大的数。谢谢。

该软件“按原样”提供，不提供任何形式的保证。

- user13366325

---

你可以通过在每次调用 rand() 时使用更多的位来改进它。假设 RAND_MAX 是2的幂减1，则以下是一种简单的方法：for (k = 1; k; k *= RAND_MAX + 1U) res |= rand() * k; - chqrlie

rand_prime() 中的 res 未初始化。你可能是想这样做，但它会生成一个警告，并且在读取 xor 操作时，res 可能是一个陷阱值，导致未定义的行为。 - chqrlie

Answer 3

关于GMP-ECM（整数分解的椭圆曲线方法）怎么样？

如果Inria官方项目页面的链接不可用，您可以在Web Archive上检查最近版本。

- John Carter

---

我找不到关于这个的文档（它的“文档”部分是空的）。它的名称似乎也暗示它使用GMP来存储整数。考虑到我在一台64位计算机上运行，我更倾向于使用64位整数。 - PythonPower

你有检查源代码分发中的readme.lib文件吗？它并不是最详细的文档，但它解释了它的工作原理。（然而，它使用gmp而不是64位整数）。 - Soroosh

2021年链接已经失效。这是反对将链接作为答案的理由的典型例子。 - Peter Leopold

@PeterLeopold：尽管指针失效，但总比没有信息好。网络档案经常有许多有用网站的备份。 - chqrlie