1

我有两种使用迭代而不是递归的欧几里得算法的实现。一种是常见的：

void myXEuclid(int a, int b)
{
    int prevx = 1, x = 0;
    int prevy = 0, y = 1;
    int q, r;

    while (b)
    {
        q = a / b;
        r = a % b;

        int tmp = x;
        x = prevx - q * x;
        prevx = tmp;

        tmp = y;
        y = prevy - q * y;
        prevy = tmp;

        a = b;
        b = r;
    }
    printf("prevx = %d, prevy = %d\n", prevx, prevy);
}

我真的不明白初始化来自哪里：

int prevx = 1, x = 0;
int prevy = 0, y = 1;

无论如何，我仍然可以从上面的片段中得到正确的答案。但是在 RSA 算法中，当我做 A*B mod n = 1 时，我必须确保 B 是最小的非负数。所以这是欧几里得算法的下一个令人困惑的实现，也使用迭代：

int Euc(int A, int B)
{
    int a = A, b = B;
    int quotient, remainder, lastY;
    int x = 0, y = 1;

    int X = 1, Y = 1;

    while (a)
    {
        quotient = b / a;
        remainder = b % a;
        b = a;
        a = remainder;
        lastY = y;
        y *= quotient;

        if (X == Y)
        {
            if (x >= y)
            {
                y = x - y;
            } 
            else
            {
                y = y - x;
                Y = 0;
            }
        }
        else
        {
            y = x + y;
            X = 1 - X;
            Y = 1 - Y;
        }

        x = lastY;
    }

    if (X == 0)
    {
        x = B - x;
    }

    return x;
}

我不知道大写变量 X 和 Y 的含义以及它们的初始化来自何处。但是上面的函数可以返回满足方程 A * x mod B = 1 的 x，它是最小的非负数。

我可以理解递归的。但不是迭代的。老实说，我已经好几天没睡好觉了。

我不是来自说英语的国家。因此，如果您能帮助我，请简单详细地解释一下。谢谢。谢谢。

4

1 回答 1

1

这里稍微详细解释一下 GCD 算法和 C/C++ 中的不同实现

http://512algorithms.blogspot.co.il/

于 2012-10-20T12:24:17.633 回答