在 C 中找到大整数的所有素因子的更好方法？

Question

我用 C 编写了一个代码，它基本上列出了一个巨大数字的所有质因数，使用 gmp 库存储。在这里：

int is_div(mpz_t number, mpz_t i) {
    return mpz_divisible_p(number,i)!=0;
}

mpz_t * prime_divs(mpz_t number){
    mpz_t * prime_dividers = NULL;
    mpz_t i, i_squared,TWO, comp;
    mpz_inits(i, i_squared, TWO, comp, NULL);
    mpz_set_ui(i,2);
    mpz_mul(i_squared, i ,TWO);
    while(mpz_cmp(i_squared,number)<=0){
        if(is_div(number,i)){
            mpz_fdiv_q(comp, number, i);
            if(is_prime(i)) append(&prime_dividers,i);
            if(is_prime(comp)) append(&prime_dividers,comp);
        }
        mpz_add_ui(i,i,1);
        mpz_mul(i_squared, i ,i);
    }
    mpz_clears(i, i_squared, TWO, comp, NULL);
    return prime_dividers;
}

注意这里没有定义函数int is_prime(mpz_t n)，因为它很长。只知道它是 Miller-Rabin 素数测试的确定性变体（最多 3,317,044,064,679,887,385,961,981）的实现。函数 void append(mpz_t** arr, mpz_t i) 也是如此，它只是一个将其附加到列表的函数。

所以我的 prime_divs 函数搜索范围 [2,sqrt(number)] 中除 number 的所有整数 i。如果是这样，它会计算它的互补除数（即 number/i）并确定它们中是否有素数。如果这些整数是素数，那么它们将被添加到使用 append.

的列表中

有什么方法可以使prime_divs更快？

Answer 1

我想您可以通过首先检查小除数来节省时间。使用埃拉托色尼筛法列出 5,000 或 10,000 以下的素数。然后使用该列表找出你的大数中的小因素（如果有的话）。每次你找到一个因子（对于同一个因子可能多次）除掉那个因子以减少目标数字的大小。

当您用尽小素数列表后，可能值得运行在尝试因式分解之前对大留数进行快速素性检查。这避免了浪费大量时间寻找大质数的因子。您需要测试这个想法，看看它是否真的为您节省了时间。

然后你才应该调用 M-R 检验来找到剩余的因素。

在 C 中找到大整数的所有素因子的更好方法？

Better way to find all the prime factors of huge integers in C?

c

primes

prime-factoring

factoring