楕円曲線上スカラー倍算のwidth-w NAF性質の証明について！

質問

この間以下の論文を読みましたけど、なかなか納得できなくて、困っています。だれが教えていただけませんか。よろしくお願いします。
　Minimality and Other Properties of the Width-w Nonadjacent Form (2004)http://citeseer.ist.psu.edu/648299.html
2.1. Uniqueness.
　Proposition 2.1. Every integer has at most one w-NAF.
　Proof. We suppose the result is false and show that this leads to a contradiction.Suppose there are two di erent w-NAFs, say (a_{l-1}... a_2a_1a_0)_2 and (b{l'-1}...b_2b_1b_0)_2,
such that(a_{l-1}... a_2a_1a_0)_2 and (b{l'-1}...b_2b_1b_0)_2,
where l and l' are the respective lengths of these representations. We can assume that l is as small as possible. These representations stand for the same integer, callit n.
(###---###の部分がわかりません、この以後は理解できると思います。)
###
　If a0 = b0, then
(a_{l-1}... a_2a_1)_2 and (b{l'-1}...b_2b_1)_2
and so we have two different, and shorter, w-NAFs which stand for the same integer,contrary to the minimality of l. So, it must be that a_0≠b_0.
###

　If n is even then a0 = b0 = 0.
However, a_0≠b_0, so it must be that n is odd;hence, both a_0 and b_0 are nonzero. Because the representations are both w-NAFs,
we have (a_{l-1}... {a_w}00...0a_0)_2 and (b{l'-1}...{b_w}00...0b_0)_2
==> a_0=b_0 (mod 2^w).
However, -(2^{w-1}-1)<=a_0, b_0<=2^{w-1}-1,
and thus -2(2^{w-1}-1)<=a_0,b_0<=2(2^{w-1}-1):
The only multiple of 2^w in this range is 0, and since 2^w|(a_0-b_0) it must be that a_0-b_0 = 0.
However, this contradicts the fact that a_0≠b_0. Thus, the representations cannot exist and the result follows.

回答No.1

Tacosan

n は「w-NAF 表現をしたときに 2通りの表現を持つ」わけですが, 実はもう 1つこっそり仮定されています. その仮定が
We can assume that l is as small as possible.
で, 「(短い方の) w-NAF 表現の長さ l が最短である」というものです.
ところが, この状況でしかも a_0 = b_0 を仮定すると「2通りの w-NAF 表現を持ち, しかももっと (w-NAF 表現が) 短い整数が存在する」ので, a_0 = b_0 はありえない, といっています.

お礼

to Tacosanさん：
ご回答をいただき、ありがとうございます。
(1)
nは2通りのw-NAF表現をもつ、それぞれのビット数はlとl'します。ただしビット数lは2通りのw-NAF表現の最短ビット数であると仮定します(l<l',)そうすると、もっと (w-NAF 表現が) 短い整数が存在するかもしれない。
たとえば、11=(a_i...a_1 a_0)_{NAF_w}=(b_j...b_1 b_0)_{NAF_w}(i<j)とすると,a_0=b_0==>(a_i...a_1)_{NAF_w}=(b_j...b_1)_{NAF_w}が成り立つ。そういう考え間違ってると思います。
(2)
ｗを固定して、すべての整数に対し、ｌは2通りのw-NAF表現の最短ビット数であると仮定しますと、以下の矛盾が出てくると思います。そういう考えは正しいですか。
{
a_0 = b_0 を仮定すると「2通りの w-NAF 表現を持ち, しかももっと (w-NAF 表現が) 短い整数が存在する」
}
2つの考え方はどうでしょうか。以上、よろしくお願いします。