2

私はpythonを持っています：

e*d == 1%etf

私たちは (e) と (etf) を知っており、拡張ユークリッド アルゴリズムと剰余算術の乗法逆数の概念を使用して (d) を発見する必要があります。

d = (1/e)%etf

d = (e**-1)%etf

グローバルな間違った番号を生成します。上記のルールを使用して (d) を見つけるのを手伝ってください。

ソリューション （以下に示すPythonのモジュラー乗法逆関数）は、間違った計算結果をもたらします

e*d == 1 (mod etf)
d = (e**(etf-2)) % etf 
d = pow(e,etf-2,etf)

私はどこかで間違いを犯していますか？この計算は大丈夫ですか？

4

2 に答える 2

3

あなたがリストしたトリックd = (e**(etf-2)) % etfは、ETFが素数の場合にのみ機能します。そうでない場合は、EEA 自体を使用してモジュラー乗法逆数を見つける必要があります。

于 2012-09-20T19:30:14.207 に答える
2

これが拡張ユークリッドアルゴリズムの実装です。私はこの回答からコードを取り出し、2 62以外のモジュラスで動作するように一般化し、JavaからPythonに変換しました。

def multiplicativeInverse(x, modulus):
    if modulus <= 0:
       raise ValueError("modulus must be positive")

    a = abs(x)
    b = modulus
    sign = -1 if x < 0 else 1

    c1 = 1
    d1 = 0
    c2 = 0
    d2 = 1

    # Loop invariants:
    # c1 * abs(x) + d1 * modulus = a
    # c2 * abs(x) + d2 * modulus = b 

    while b > 0:
        q = a / b
        r = a % b
        # r = a - qb.

        c3 = c1 - q*c2
        d3 = d1 - q*d2

        # Now c3 * abs(x) + d3 * modulus = r, with 0 <= r < b.

        c1 = c2
        d1 = d2
        c2 = c3
        d2 = d3
        a = b
        b = r

    if a != 1:
        raise ValueError("gcd of %d and %d is %d, so %d has no "
                         "multiplicative inverse modulo %d"
                         % (x, modulus, a, x, modulus))

    return c1 * sign;
于 2012-09-21T22:02:37.930 に答える