Rollard'srho算法C语言

Rollard'srho算法是一种用来寻找大素数的随机算法，下面是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long gcd(long a, long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long rollards_rho(long n) {
    long x = rand() % (n - 2) + 2;
    long y = x;
    long c = rand() % (n - 1) + 1;
    long d = 1;
    while (d == 1) {
        x = (x * x + c) % n;
        y = (y * y + c) % n;
        y = (y * y + c) % n;
        d = gcd(abs(x - y), n);
    }
    if (d == n) return rollards_rho(n);
    return d;
}

int is_prime(long n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    long d = n - 1;
    while (d % 2 == 0) d /= 2;
    int k;
    for (k = 0; k < 5; k++) {
        long a = rand() % (n - 3) + 2;
        long x = pow(a, d) % n;
        if (x == 1 || x == n - 1) continue;
        int i;
        for (i = 0; i < (int)log2(n) - 1; i++) {
            x = (x * x) % n;
            if (x == 1) return 0;
            if (x == n - 1) break;
        }
        if (i == (int)log2(n) - 1) return 0;
    }
    return 1;
}

long find_prime(long n) {
    long d = 1;
    while (d == 1) {
        d = rollards_rho(n);
    }
    if (is_prime(d)) return d;
    return find_prime(n / d);
}

int main() {
    long n;
    printf("Enter a number: ");
    scanf("%ld", &n);
    long p = find_prime(n);
    printf("The largest prime factor of %ld is %ld.\n", n, p);
    return 0;
}

该程序通过 `find_prime` 函数来找到大素数，并将其作为输出。该函数通过调用 `rollards_rho` 函数来找到 $n$ 的一个非平凡因子 $d$，然后检查 $d$ 是否为质数。如果是，则返回 $d$，否则递归地调用 `find_prime` 函数，直到找到一个质数为止。

`rollards_rho` 函数使用了随机算法来寻找 $n$ 的一个非平凡因子。该函数先随机选择一个 $x$，然后计算 $x^2 + c \pmod n$，其中 $c$ 是一个随机整数。接着，它分别计算 $x$ 和 $y = (x^2 + c) \pmod n$ 的值，直到它们相遇或者找到了一个非平凡因子 $d$。如果相遇了，则计算 $\gcd(|x - y|, n)$，如果 $\gcd$ 不等于 $1$ 且不等于 $n$，则返回 $\gcd$。如果找到了一个非平凡因子，则返回该因子。如果找到的因子是 $n$，则递归地重新调用 `rollards_rho` 函数。

`is_prime` 函数用来检查一个数是否为质数。该函数使用的是 Miller-Rabin 算法，它是一种快速判断质数的方法。

该程序的输出为 $n$ 的最大素因子。