在C中找到大整数的所有素因数的更好方法？ [英] Better way to find all the prime factors of huge integers in C?

问题描述

我用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函数搜索i范围内的所有整数number。如果是这样，它然后计算它的互补因子(即number/i)，并确定它们中是否有任何一个是素数。如果这些整数是质数，则将使用append将它们追加到列表中。

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

推荐答案

我怀疑您可以通过首先检查小的除数来节省时间。使用Eratosthenes筛子来建立一个低于5,000或10,000的素数列表。然后用这张清单找出你人数众多的小因素，如果有的话。每次您找到一个因子(对于同一因子可能有多次)时，将该因子分开以减小目标数字的大小。

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

只有到那时，您才应该调用M-R测试来找出剩余的因素。

这篇关于在C中找到大整数的所有素因数的更好方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！