[情報セキュリティ] バイナリ法がわかりません..

質問

[情報セキュリティ] バイナリ法がわかりません...

ー－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
問題.
バイナリ法でa^19を計算するのに必要な乗算は何回必要か示せ

解答.
19=(10011)_2

※以下、aの指数の()内の数字は二進数とする

y ← a = a^(1) mod N
y ←y^2 = a^(10) mod N
y ←y^2 = a^(100) mod N
y ←y^2 = a^(1000) mod N = = a^(1001) mod N
y ←y^2 = = a^(10010) mod N = a^(10011) mod N

よって乗算は６回
ー－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
とありました。
しかし、
a^2 = a*a
a^4 = a^2 * a^2
a^8 = a^4 * a^4
a^16 = a^8*a^8
a^17 = a^16 * a
a^18 = a^17 *a
a^19 = a^18 *a
より、乗算は７回なのではないのですか？
解答がmod Nと、Nでわったあまりにしているのもよくわかりません

よろしくお願いします

回答No.1

上野 尚人（@uenotakato）

最終的に求めたい値は a^19 ではなく a^19 を N で割った余りだと思われます。

y ← a = a^(1) mod N
a を N で割った余りを求めて y に格納する

y ←y^2 = a^(10) mod N
y^2 を N で割った余りを求めて y に格納する
（y^2 を求める際に乗算1回）
この時点で、a^2 を N で割った余りを求めたことになる

y ←y^2 = a^(100) mod N
y^2 を N で割った余りを求めて y に格納する
（y^2 を求める際に乗算1回）
この時点で、a^4 を N で割った余りを求めたことになる

y ←y^2 = a^(1000) mod N = = a^(1001) mod N
y^2 * a を N で割った余りを求めて y に格納する
（y^2 * a を求める際に乗算2回）
この時点で、a^9 を N で割った余りを求めたことになる

y ←y^2 = = a^(10010) mod N = a^(10011) mod N
y^2 * a を N で割った余りを求めて y に格納する
（y^2 * a を求める際に乗算2回）
この時点で、a^19 を N で割った余りを求めたことになる

以上より、乗算の回数は6回とできます。

お礼

ありがとうございました。