Problem 182 「RSA暗号」

RSA 暗号は以下のアルゴリズムに基づいている:

さてある em について me mod n = m となることがある. 以下, me mod n=m となる m公然の平文と呼ぶことにする.

公開鍵の一部 e を選ぶときには, 公然の平文が多くならないという点が重要である. 例えば, p = 19, q = 37 とする. このとき, n = 19 * 37 = 703 でありφ = 18 * 36 = 648 である. もし e = 181 とすると, gcd(181, 648) = 1 であるが, 全ての平文 m (0≤mn-1) が公然の平文となってしまう. e についてどのような選び方をしても, 必ずいくつかは公然の平文が存在する. 従って, 公然の平文の数を最小化するように e を選ぶのは重要である.

さて, p = 1009, q = 3643 とする. このとき, 公然の平文の個数が最小となる全ての e の総和を求めよ (ただし 1<e<φ(1009,3643) かつ gcd(e,φ)=1).


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-11-02 (火) 22:24:31