Pollard rho 整数分解

Question

我正在尝试在 C/C++ 中实现 Pollard Rho 整数分解。Google 为我提供了问题的 Java 实现 此处。

我不太了解 Java，所以我想出了这个。我在 C++ 中的实现适用于大多数人但很少有像我在那里使用的“9999”这样的情况。

我知道 C++ 没有 Biginteger 类，所以我无法拥有 JAVA 中提供的完整功能，但我想分解 15 位数字，这足以满足 unsigned long long

请指出什么我的实施错误。

Answer 1

问题就在这里：

#define abs(x) (x>0)?(x):(-x)

您的 abs 宏中缺少一些括号。尝试：

#define abs(x) ((x)>0 ? (x) : -(x))

相反。 （考虑在 x-xx <= 0 的情况下扩展 abs(x-xx) 时会发生什么。）

另外，为什么你的 gcd 函数返回一个 int 而不是比 BigInteger？

您还应该注意（假设 unsigned long long 是 64 位整数类型）此代码对于大于 2**32 的 N 无法正常工作：如果x（或xx）大于或等于2**32，则x*x将换行模2**64，为您提供了错误的 x*x % N 值。

Answer 2

我发现了一个区别：Java 代码将 c 和 x 分配为 new BigInteger(N.bitLength(), random)，而C++代码使用rand() % N，这是一个较小的随机范围。对于值 9999，二进制为 10011100001111，因此 Java 代码将为 c 和 x 提供最大值 16383。

Answer 3

您可以尝试 Pollard Rho 的约 100 行 C 实现：

有一些助手：

#include <stdlib.h>
#include <stdint.h>

typedef uint_fast64_t num ;

static inline num mul_mod(num a, num b, const num mod) {
    // Return (a * b) % mod, avoiding overflow errors while doing modular multiplication.
    num res = 0, tmp;
    for (b %= mod; a; a & 1 ? b >= mod - res ? res -= mod : 0, res += b : 0, a >>= 1, (tmp = b) >= mod - b ? tmp -= mod : 0, b += tmp);
    return res % mod;
}

static inline num square_root(num n) {
    // Return the number that was multiplied by itself to reach N.
    num a = 0, b, c;
    for (b = 1ULL << 62; b; c = a + b, n -= c &= -(n >= c), a = (a >> 1) | (c & b), b >>= 2);
    // Variable n contains the remainder.
    return a;
}

有一个必需的质数检查器：

static  int is_prime(const num n, size_t iterations) {
    // Perform a Miller-Rabin (strong probable prime) test.
    num a = 0, b, c, d, e, f; int h, i;
    if ((n == 1) == (n & 1)) return n == 2;
    for (b = c = n - 1, h = 0; !(b & 1); b >>= 1, ++h);
    for (; iterations--;) {
        for (size_t g = 0; g < sizeof(a); ((char*)&a)[g++] = rand()); // random input.
        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 = mul_mod(d, d, n), f & b && (d = mul_mod(e, d, n)));
        if (d == 1) continue;
        for (i = h; i-- && d != c; d = mul_mod(d, d, n));
        if (d != c) return 0;
    }
    return 1;
}

有两个因式分解函数：

static inline num factor_worker_2(const num n, size_t limit) {
    // Perform a Pollard's Rho probabilistic test.
    size_t a = -1, b = 2;
    num c, d = 1 + rand(), e = 1, f = 1;
    for (c = d %= n; f == 1 && --limit; d = c, b <<= 1, a = -1) {
        for (; f |= e, f == 1 && ++a != b;) {
            c = mul_mod(c, c, n);
            for (++c, c *= c != n, e = n, f = c > d ? c - d : d - c; (f %= e) && (e %= f););
        }
    }
    return f;
}

static inline num factor_worker_1(const num n) {
    // Perform a trial divisions test on N.
    static const num list[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 1};
    size_t i;
    for (i = -1; n % list[++i];);
    return list[i];
}

有一个因式分解< strong>ma​​nager：

num factor(const num n) {
// Basic factorization manager, detect primes, perfect squares, execute workers.
    num res;
    switch (n) {
        case 0: case 1: case 2: case 3:
            res = 1; break;
        default:
            res = factor_worker_1(n);
            if (res == 1 && !is_prime(n, 20)) {
                res = square_root(n);
                if (res * res != n)
                    for(;res = factor_worker_2(n, -1), res == 1 || res == n;);
            }
    }
    return res;
}

有一个ma​​in：

#include <assert.h>
#include <stdio.h>

int main(void) {
    num N;
    N = 951818131364430049;
    printf("factor is %zu\n", factor(N));
}

尝试一下：

// You can put it into a main.c file then compile + execute :
// gcc -O3 -std=c99 -Wall -pedantic main.c ; ./a.out ;

这里是来源 了解更多信息，谢谢。