0

私は来週これについてテストを受け、素数を使ったいくつかの基本的な例を実行していました。本の例はこの問題に悩まされていないようです

ステップ 1- 2 つの素数を選択します (私は p=3、q=7 を選びました)

ステップ 2 - n=pq = 21 を計算する

ステップ 3 - totient(n) = tot(p)*tot(q) = 2*6 = 12 の計算

ステップ 4- gcd(e,tot(n))=1 (互いに素) となる 1 < e < tot(n) となる e を選択します。私は e=5 を選びました。

ステップ 5- d*e % tot(n) = 1 となるように d を選択します。

私が理解したことから、d は整数でなければなりませんでした。それは間違った結論ですか？または、この場合、5 は有効な e ではありませんか?

4

2 に答える 2

1

はい、整数でなければなりません。ステップ 5 で探しているのは、剰余乗法逆数です。基本的に、ある整数、または別の言い方をdすれば、 の倍数よりも 1 大きいような整数です。とが互いに素である限り、逆になります — あなたの例の場合、たまたま 5:です。d*e = m*tot(n) + 1md*etot(n)etot(n)edd*e = 5*5 = 25 = 2*tot(n) + 1

于 2013-10-18T16:45:39.567 に答える
1

はい、dは整数であり、eの剰余逆数として計算されます。以下は、係数mに関して数値xの逆数を計算する関数です。

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q := b // m
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

もっと見たい場合は、私のブログに RSA 計算の例があります。

于 2013-10-18T17:00:31.640 に答える