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

Question

Closed. This question is seeking recommendations for software libraries, tutorials, tools, books, or other off-site resources. It does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

我们不允许提出寻求软件库、教程、工具、书籍或其他场外资源推荐的问题。 您可以编辑问题，以便用事实和引文来回答。

2 年前已关闭。

社区审查了是否在 2 年前重新开放此问题，并将其关闭：

原始关闭原因未解决

Answer 1

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

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

本文档对应于 Msieve 库的 1.46 版本。
不要指望仅仅通过阅读它就能成为保理专家。 我有
包括一个相对完整的参考列表，您可以和
如果您不想将代码视为黑匣子，则应该查找
解决您的保理问题。

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);

因式分解过程经理，因为有一个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 行概率因式分解软件命题基于 Miller–Rabin 素性测试，后跟或不跟随 >Pollard 的 rho 算法。 和你一样，我最初的目标是分解一点long long int。 根据我的测试，它的运行速度对我来说足够快，甚至对于一些更大的人来说也是如此。 谢谢。

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

Answer 3

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

如果 Inria 官方项目页面的链接不可用，您可以检查 网络存档上的最新版本。