c - C/GMP中的段错误:使用Pollard Rho计算因子

我是一个经验丰富的程序员，但对C还不太熟悉。我正在尝试学习C语言，以便使用gmp库编写快速的大整数程序；最后，我打算用C函数编写程序的性能部分，这些函数是通过其他语言的外部函数接口调用的。作为学习C和gmp库的工具，我编写了如下所示的pollard rho整数分解程序（是的，我知道这不是pollard rho最好的实现，但它很简单，目前我只想开始）。我的程序编译正确，但当运行时它会死掉，并显示“分段错误”消息。我想这意味着我的指针在某个地方被弄乱了，但我看不到。可能不止一个。有人能看看我的程序并告诉我哪里出错了吗？并指出任何风格问题或其他我可以改进的？多谢，菲尔

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

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

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    if (! (new = malloc(sizeof(List))))
        return NULL;
    new->data = data;
    new->next = next;
    return new;
}

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    } else {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r);
}

void rho_factors(List *fs, mpz_t n)
{
    mpz_t f;
    mpz_init_set_ui(f, 0);

    while (! (mpz_probab_prime_p(n, 25)))
    {
        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    mpz_clear(f);
    insert_in_order(n, fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s\n", argv[1]);
        return 0;
    }

    printf("%s", argv[1]);
    rho_factors(fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }

    return 0;
}

编辑1：多亏了丹尼尔·菲舍尔，我取得了一些进步，不再有分割错误。当用n=1234567调用rho棼u factor时，下面显示的代码正确地打印了因子127，但是rho棼u factors返回一个空列表，因此rho棼u factors仍然有问题。我想问题是我不能像现在这样一直重新初始化同一个变量，但是我不知道正确的方法。不知何故，我需要复制我找到的每个因素，然后在fs中插入该副本。多谢，菲尔

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

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

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    if (! (new = malloc(sizeof(List))))
        return NULL;
    new->data = data;
    new->next = next;
    return new;

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    } else {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r, NULL);
}

void rho_factors(List *fs, mpz_t n)
{
    while (! (mpz_probab_prime_p(n, 25)))
    {
        mpz_t f;
        mpz_init_set_ui(f, 0);

        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    insert_in_order(n, fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s is prime\n", argv[1]);
        return 0;
    }

    rho_factor(f, n, 1);
    printf("%s\n", mpz_get_str(NULL, 10, f));

    printf("%s", argv[1]);
    rho_factors(fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }

    return 0;
}

伊迪丝2：明白了。感谢丹尼尔·费舍尔。最终版本如下所示。

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

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

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    new = malloc(sizeof(List));
    new->data = data;
    new->next = next;
    return new;
}

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    }
    else
    {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r, NULL);
}

void rho_factors(List **fs, mpz_t n)
{
    while (! (mpz_probab_prime_p(n, 25)))
    {
        mpz_t *f = malloc(sizeof(*f));
        mpz_init_set_ui(*f, 0);

        rho_factor(*f, n, 1);
        *fs = insert_in_order(*f, *fs);
        mpz_divexact(n, n, *f);
    }

    *fs = insert_in_order(n, *fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s is prime\n", argv[1]);
        return 0;
    }

    printf("Factors of %s:", argv[1]);
    rho_factors(&fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }
    printf("\n");

    return 0;
}

最佳答案

不能重复使用这样的mpz_t：

void rho_factors(List *fs, mpz_t n)
{
    mpz_t f;
    mpz_init_set_ui(f, 0);

    while (! (mpz_probab_prime_p(n, 25)))
    {
        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    mpz_clear(f);
    insert_in_order(n, fs);
}

GMP重新分配viaf指向的存储时，旧存储是freed。这很可能发生在while循环中，但不一定。如果没有，那么所有列表条目都指向同一个数字。
但是在循环之后，当您mpz_clear(f)时，列表data中的每个fs指针都变成了一个野生指针，然后当您insert_in_order(n, fs)时，您会取消以前的freed指针的引用。（这很可能已经在while循环中的某个insert期间发生了，但这里可以保证。）
另外，在rho_factor中，您应该调用

mpz_clears(t, h, d, r, NULL);

mpz_clears的参数列表必须以NULL结尾。
其他问题：
通过aList *，因此对fs中的rho_factors所做的更改不会影响fs中的main。传递一个List **并在适当的地方取消引用它，还忘记分配最后的insert_in_order返回值。
局部变量f超出块末尾的范围，导致损坏。malloc指向mpz_t的指针以保持它们的生存。
无效rho_因子（列表**fs，mpz_t n）
{
同时（！（mpz_probab_prime_p（n，25）））
{
mpz_t*f=malloc（大小（*f））；
mpz_init_set_ui（*f，0）；

    rho_factor(*f, n, 1);
    *fs = insert_in_order(*f, *fs);
    mpz_divexact(n, n, *f);
}

*fs = insert_in_order(n, *fs);

}
在main

List *fs = NULL;
/* snip */
rho_factors(&fs, n);

应该这么做。最后（？），则在insert_in_order中有故障，while循环中的比较是向后的。

关于c - C/GMP中的段错误:使用Pollard Rho计算因子，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9354211/