CS6.006 Problem Set 5を解く

問題はこちら 意訳が間違っていたらご指摘ください。

フォーマットの説明

問題文

思考方法→答え

の順で書いています。

Problem 5-1

base = 256、つまり256進数で表された整数の計算をするプログラムについて。 base = 256なので、我々が普段使う10種類の0-9の文字だけでなく、"#"とか"$"とか含む256種類の文字を使って数を表すことに注意。 我々の世界の足し算は10進数なので、例えば425+43 = ?みたいな足し算が普通だが、 256進数の場合は5#*&2 + 6S1$); = ?みたいなものが定義できる。いかにも宇宙人の足し算のようなイメージ(だと自分は思う)だが、彼らが256進数を使っているだけと思えばこれは大したことはない。

まずはA+Bについて。 問題文中のアルゴリズムに各行の計算量をつけたものを下に載せる。

ADD(A, B, N)
  C = ZERO(N+1)...O(1)
  carry = 0...O(1)
  for i=1 to N...O(N)
    digit = WORD(A[i]) + WORD(B[i]) + WORD(carry)...O(1)
    C[i] = digit % 256...O(1)
    carry = digit / 256...O(1)
  C[N+1] = carry...O(1)
  return C...O(1)

(a) ADD の time-complexityは?

\Theta(N)→正解。

(b) ADDのoutputのsizeは?

\Theta(N)→正解。

(c) ADD’s output size suggests an easy lower bound for the subroutine. Does the running time of ADD match this lower bound?

(b)より、outputのsizeはO(N)で、少なくともNのsubroutineがあるといえる。(for文のループ1回をsubroutineと考えたらいえる)よって、1. Yes→正解。

次はA・Bの掛け算のプログラムについて。

MULTIPLY(A, B, N)
  C=ZERO(2N) ...O(1)
  for i= 1 to N ...O(N)
  carry=0 ...O(1)
    for j= 1 to N...O(N)
      digit=A[i]·B[j] +WORD(C[i+j−1]) +WORD(carry)...O(A[i]・B[j])
      C[i+j−1] =LSB(digit)...O(1)
      carry=MSB(digit)...O(1)
    C[i+N] =carry...O(1)
  return C

(d) MULTIPLYのtime-complexityは?

\Theta(N^{2})→正解。

(e) MULTIPLYのoutputのサイズは?

\Theta(N)→正解。

(f) MULTIPLY’s output size suggests an easy lower bound for the subroutine.Does the running time of MULTIPLYmatch this lower bound?

(c)とちがって、サイズとtime-complexityが一致していないので、2.No→正解。

次はA / BとA%Bを同時に行うプログラムについて。

DIVMOD(A, B, N)
  Q = ZERO(N) ...O(1)
  R = COPY(A, N) ...O(N)
  S0 = COPY(B, N) ...O(N)
  i = 0 ...O(N)
  repeat ...O(N)
    i = i + 1 ... O(1)
    Si = ADD(Si-1, Si-1, N) ...O(1)
  until Si[N+1] > 0 or CMP(Si, A, N) == GREATER ...O(N)
  for j = i - 1 downto 0 ...O(N)
    Q = ADD(Q, Q, N) ...O(1)
    if CMP(R, Sj, N) != SMALLER ...O(N)
      R = SUBTRACT(R, Sj, N) ...O(1)
      Q[0] = Q[0] || 1 ...O(1)
  return (Q, R)

ざっと何をやっているかについて考える。 まず、前提知識としてビットシフトが必要。説明すると以下のようになります。

ビットシフトとは、数を左または右にずらす操作。

左ビットシフトは、101010という数を、1010100にする操作。

右ビットシフトは、101010という数を、0101010にする操作。

左ビットシフトは数を2倍することに相当し、右ビットシフトは数を2で割ることに相当する。(17とかを2進数に直してビットシフトして10進数に直して確認すればわかります)

さて、DIVMODについて。

DIVMOD(A, B, N)...Aは割られる数、Bは割る数
  Q = ZERO(N) ...商を入れる変数
  R = COPY(A, N) ...余りを入れる変数
  S0 = COPY(B, N) ...S_iはB*(2^i)つまりBをi回左にビットシフトした数
  i = 0 
  repeat ...O(N)
    i = i + 1 
    Si = ADD(Si-1, Si-1, N) ...S_iを2倍している。つまりS_iを1回左にビットシフトしている
  until Si[N+1] > 0 or CMP(Si, A, N) == GREATER ...S_iがAより大きくなった時点でrepeat以下を止める
  // ここで例えばi=3でrepeatから抜け出したとすると、Aは、(Bを2回ビットシフトした数)で割れるが、(Bを3回ビットシフトした数)では割れない、ということになる
  for j = i - 1 downto 0 ...商を計算する。
    Q = ADD(Q, Q, N) ...Qを2倍している。つまりQを左にビットシフトする。
    if CMP(R, Sj, N) != SMALLER 
      R = SUBTRACT(R, Sj, N) ... R が S_jより大きいなら、RからS_jを引く。
      Q[0] = Q[0] || 1 ...RからS-jを引いた時にQの最下位ビット(下一桁)を1にする。
  return (Q, R)

(g) CMP(A, B, N)はAとBの大きさを比較してGREATER, SAMLLER, EQUALを返す。CMPが最適な場合のtime-complexityは?

ADD(A, -B)の結果を比べると考えれば、ADDの計算量に依るので、

\Theta(N)→正解。

(h) SUBTRACT(A, B, N) はA-Bを計算する。最適な場合のtime-complexitは?

上と同様に、

\Theta(N)→正解。

(i) DIVMODのtime-complexityは?

CMPがN回、iは最大でN回行われるので、

[tex:\Theta(N2)]→正解。

次は、Newton法を使ってより効率よく割り算を計算するDIVについて。 (DIVは前の問で述べたサブルーチンに基づいているらしいが、どのサブルーチンなのかわからない。一問前に出てきたDIVMODを使うとその時点でNewton法ではなくなるし。。。)

(j) DIVはMULTIPLYを何回呼ぶ?

わからない。→Lecture note 12に載っているNewton法をもとに答えれば良い。

(k) MODのtime-complexityは?

わからない。→同上。英語の読解力がなかった。

次は、 BE mod M

を計算するアルゴリズムについて。入力はN桁。

POWMOD(B, E, M, N)
  R=ONE(N)//result
  X=COPY(B, N)//multiplier
  for i= 1 to N ...O(N)
    mask= 1 ...O(1)
    for bit = 1 to 8 ...O(1)
    if E[i] & mask! =0 ...O(1)
      R=MOD(MULTIPLY(R, X, N), M,2N) ...O(N^2)
      X=MOD(MULTIPLY(X, X, N), M,2N) ...O(N^2)
      mask=LSB(mask·2) ...O(1)
      return R

(l) POWMODのtime-complexityは?

\Theta(N^{3})→正解。

ここで、MULTIPLYを、karatsubaアルゴリズムで書き換える。 Karatsubaは、N桁同士の掛け算をO(Nlog_{2}{3})で行える。

(m) karatsubaのtime-complexityは?

\Theta(N^{log_{2}{3}})→正解。

(n) karatsubaを使った場合のMODは? MODは、A-B(A / B)で計算できるので、karatsubaによるmultiplyと同じ計算量でできる。

\Theta(N^{log_{2}{3}})→正解。

(o) karatsubaを使った場合のPOWMODのtime-complexityは?

\Theta(N*N^{log_{2}{3}})

= \Theta(N^{log_{2}{6}})

→正解。

(p) Aのk乗根の整数部分を、二分探索を使って求める擬似コードを書け。time-complexityはN2 + log3である。

今までのPOWMODとか関数を使うのかなと予想し、考えてみる。

\sqrt[K]{A}\leqx<\sqrt[K]{A}+1

を満たすxが求まれば、xの整数部分が答えである。

これらをK乗すると、

A\leqx^{K}<(\sqrt[K]{A} + 1)^{K}

が得られる。 だから、これを満たした時点で終了するようなwhileループを書いて二分探索を行えばよい? 実際には、上限の(\sqrt[K]{A} + 1)^{K}はAのK乗根を知らないと計算できないので、A+1を上限として抑えればよい。 通常の二分探索のコードをアレンジしたものが以下。

left = 0
right = A + 1
middle = left + (right - left) / 2
while ( abs(POW(middle, K) - A) < 1 ){
  if ( POW(middle, K) < A ){
    left = middle
  }
  else {
    right = middle
  }
  middle = left +(right - left) / 2
}

time-complexityは、 whileループがlog(N)回実行され、その中でPOW(middle, K)は、先ほどのPOWDIVを使うとして

\Theta(N^{log_{2}{6}})

の時間がかかるので、

\Theta(log{N}*N^{log_{2}{6}})

が答え??だがこれは問題設定に合わない。諦める。→

答えの概要:[tex:2i]のK乗がAを超えるような最小のiを計算し、j=i-1から0までiterateし、[tex:R + 2j]のK乗がAを超えない場合のみ[tex:R=R+2j]へとRを更新する。 こうしていくと、RはAのK乗根の直前のintegerに近づいていく。 2のi乗を足していく操作をすることで、ビットシフトとbitwise-ORだけで足し算が実現できるのでこちらの方が早い。そのうち詳しく記事にしたい。

Problem 5-2

次は、RSA暗号の問題。文中から読み取れるRSA暗号の仕組みをまとめると以下のようになる。数字eとして、65537を選ぶのがよくあるらしい。(そこそこ大きくて素数だから?)

f:id:hisyatokaku:20191103145949p:plain
自分の鍵を公開する様子

f:id:hisyatokaku:20191103150034p:plain
サーバがユーザからもらった鍵を利用して安全に数字を伝える様子

(a) 復号の部分の計算、つまりed mod mのtime-complexityは?

先ほどのPOWMODをそのまま使えば良い。ので、

\Theta(N^{log_{2}{6}})→正解。

次に、RSAの応用例の話。問題設定は、自分がKeg standをしている写真を暗号化して送りたい状況。

Keg standの例。狂っている。 www.google.com

効率の悪い方法の紹介から始まる。これは、画像をN-1バイトずつに切り分けて、(端っこはN-1バイトにならなかったら、N-1バイトになるまで0をつける) それぞれのブロックをRSA暗号で暗号化する。画像を青で表すと以下のようなイメージ。

f:id:hisyatokaku:20191103151005p:plain
問題で紹介されている、非効率な暗号化の方法

(b) R×Cの画像をブロックにわけて暗号化する。RSA暗号化の関数をE(n)とすると、これは何回呼ばれるか?

問題文から、画像のバイト数は全部で、3 × R × Cバイト(3はRGBそれぞれでの数字を保管する分)。 3×Cの画像領域をN-1バイトのブロックに切り分ける操作をR回行うので、できるブロックの数は、

RC/(N-1)

Big-O記法では定数は無視するので、

RC/Nが答え。→正解。

(c) (b)のように暗号化した画像を復号するtime-complexityは?

復号には、POWMODを呼ぶ必要がある。これは、(a)より計算量がわかっている。このPOWMODはブロックの数だけ呼ばれるので、

\Theta(\frac{RC}{N}N^{log_{2}{6}})

つまり、

\Theta(RCN^{log_{2}{3}})→正解。

(d) RSA暗号で暗号化されない数をfixed pointと呼ぶ。つまり、E(n) = n mod mとなる数nのことである。以下の数はfixed pointか?:0, 1, 2, 3, m-1, m-2

E(n) = ne mod m = n mod mとなる数がfixed pointである。0, 1はe乗されても結果が変わらないのでmodも変わらない。2, 3, m-1, m-2は変わる。→

m-1 \equiv -1 mod mで、[tex:(-1)e = -1](eは奇数)であるので、0, 1, m-1が正解。

(e) RSA暗号の弱点を表すものとして正しい式を以下から選べ。

  • mは素数の積であればよいので m = 3 * 5 = 15として
  • eは(3-1)*(5-1) = 8と互いに素であればよいのでe=3として
  • nはなんでもよいのでn=2として

一個一個代入して確かめれば良い。反例があれば正しくないといえる。

  1. E(-n)\equiv -E(n)  mod  m → 左辺:(-2)3 mod 15 = -8 mod 15 = 7, 右辺:-(23) mod 15 = 7 なので一致。

証明:f:id:hisyatokaku:20191103162144j:plain →正解。

  1. E(n_1)+E(n_2) \equiv E(n_1 + n_2) mod m → n_1, n_2を1, 2として、左辺:(E(1) + E(2)) mod 15 = 9 mod 15 = 9, 右辺:E(1 + 2) mod 15 = 27 mod 15 = 12なので不一致。 →正解。

  2. E(n_1)-E(n_2) \equiv E(n_1 - n_2) mod m → n_1, n_2を2, 1として、左辺:(E(2) - E(1)) mod 15 = 7 mod 15 = 7, 右辺:E(2-1) mod 15 = 1 mod 15 = 1なので不一致。 →正解。

  3. E(n_1)×E(n_2) \equiv E(n_1×n_2) mod m → n_1, n_2を1, 2として、左辺:(E(1) × E(2)) mod 15 = 8 mod 15 = 8, 右辺:E(1×2) mod 15 = 8 mod 15 = 8なので一致。

証明:f:id:hisyatokaku:20191103162202j:plain →正解。

  1. E(n_1)^{n_2} \equiv E(n_1^{n_2}) mod m → n_1, n_2を2,3として、左辺:E(2)3 mod 15 = 23e mod 15= 512 mod 15 = 2, 右辺:E(23) mod 15 = 8e mod 15 = 2なので一致。

証明:f:id:hisyatokaku:20191103162217j:plain →正解。

次に、RSAの応用例について。会社Aは、新製品ができる日より前は、NOというメッセージを暗号化し、会社Bに毎日伝えつづけ、新製品ができたら、YESというメッセージを暗号化し、会社Bに伝える。しかしこれには欠点があり、他者が暗号を解読できなくても、NOというメッセージからYESというメッセージに変わったことだけはわかるので、新製品ができた事実がバレる可能性があるというもの。(なお、暗号化は会社Bのe, mを使って行われるものとする。)

(f) この解決策として有効なものを以下から選べ。

  1. 一定の長いメッセージを送りたいメッセージの最後尾に追加し、メッセージをとても長くする。→ 毎日同じメッセージを送ることに変わりないので、有効でない。

  2. 固定長のrandomな数字をメッセージに貼り付ける。→毎回暗号化された値が変わるので良い。また、固定長の数字であれば、受信した側は復号した後に出てきたrandom数字を除去すればよいので、有効である。

  3. 会社Aは、自分のe, mを毎回生成し、毎回異なるe, mでメッセージを送る。復号に必要な鍵dは、会社Bのe, mを用いて送る。→ これも毎回暗号化された値が変わる。また、解読に必要な鍵自体も暗号化されているので、漏洩しても会社Bの復号用の鍵dがバレていなければ、解読される心配がない。よって有効である。

  4. 一般的でない文字エンコーディングで文字を変換する。→暗号化された値は毎回変わらないので、有効でない。

  5. 会社Aと会社Bが秘密の復号用の鍵をシェアする。→暗号化された値は毎回変わらないので、有効でない。

→正解。

Problem 5-3

プログラミング課題。省略。