0

我用 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)这里没有定义该函数，因为它很长。只要知道它是米勒拉宾素性检验的确定性变体（最多 3,317,044,064,679,887,385,961,981）的实现。function 也是如此void append(mpz_t** arr, mpz_t i)，它只是一个将其附加到列表的函数。

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

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

4

1 回答 1

2

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

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

只有这样你才应该调用 MR 测试来找到剩余的因素。

于 2020-04-20T11:31:51.050 回答