1

再帰ではなく反復を使用したユークリッドのアルゴリズムの実装には2つのタイプがあります。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 に答える