MOF: Mutual Opposite Form(相互交代形式)

English page German page

MOFは符号付きバイナリ列の新しい標準的な表現で、右から左へだけでなく 左から右へも計算することもできる。

内容:
動機:

アーベル群のランダムな元に対する指数演算における最も共通な方法は 移動窓方式であり、これはいくつかの前計算を犠牲にしてバイナリ法の効率性を高めるものである。逆元計算が易しい（例えば、楕円曲線）群において、指数の符号付き表現は、必要となる前計算の量を減らすことができるので 意味がある。漸近的に最もよい符号付きの方法はw NAF(幅w の非隣接形式)である、なぜなら非零濃度がほぼ最適であるように前計算の試みが最小になっているからある。不運にも、幅w の非隣接形式は最下位ビットからしか計算することができない、すなわち右から左へしか計算することができない。しかしながら、メモリが抑制された機器との関連から左から右への記録方式は非常に貴重である。

整数d の表現はd=sum(di 2i) として表現し、ここで、di はT の元である。通常の2進表現としてT={0,1} を表し、この表現は一意的である。 もし、集合T が大きければ、すなわち負の数を許せば、一つの数に対して、いくつかの表現で表すことができる。
10進数2進数 T=
181=10110101{0,1}
=1-110-11-11-1{-1,0,1}
=10-10-10101{-1,0,1}

ゴール

  1. #T を最小にする。
    楕円曲線暗号への応用として、T の各桁は時間のかかる前計算を必要とし、メモリも必要となる。
  2. 非零濃度を最小にする。
    乗法や指数演算のアルゴリズムでは、非零 の桁には余分な演算が必要となる。したがって、0 の桁がたくさんある ときの計算は速い。
相互交代形式:

定義(相互交代形式)
相互交代形式(Mutual Opposite Form(MOF))とは、以下の条件を満たす符号付きバイナリ列である:

  1. 隣接する非零ビットの符号が相互である(0 ビットの部分は考えない)。
  2. 非零である最上位ビットと非零である最下位ビットはそれぞれ1 と-1 である。

例
互いに符号が交代している非零ビットの間にいくつかの0 ビットが挿入される。 MOFの例として、0 1 0 0 -1 0 1 0 0 0 -1 0 0 1 -1 0がある。 次に各バイナリ列は相互交代形式によって一意に表現することができることを証明する。

バイナリ列から相互交代形式への変換
n ビットのバイナリ列から(n+1) ビットの相互交代形式への単純かつ自由な変換を示す。

極めて重大なポイントは以下の点である。n ビットのバイナリ列d はmd = 2d - d を計算することによって変換できる、 ここで、- はビットの引き算とみなす。実はd を以下のように変形できる:

2d =dn-1dn-2...di-1...d1d0
-d =dn-1...di...d2d1d0
md =dn-1dn-2-dn-1...di-1-di...d1-d2d0-d1-d0

アルゴリズム : バイナリ法から相互交代形式への左から右への変換
入力:非零n ビットのバイナリ列d=dn-1|dn-2|...|d1|d0
出力:相互交代形式 mdn|...|md1|md0 of d
  • mdn <- dn-1
  • for i = n - 1 down to 1 do
    • mdi <- di-1 - di
  • md0 <- -d0
  • return (mdn, mdn-1, ..., md1, md0)

アルゴリズム: バイナリ法から相互交代形式への右から左への変換
入力:非零n ビットのバイナリ列d=dn-1|dn-2|...|d1|d0
出力:相互交代形式 mdn|...|md1|md0 of d
  • md0 <- -d0
  • for i = 1 to n - 1 do
    • mdi <- di-1 - di
  • mdn <- dn-1
  • return (mdn, mdn-1, ..., md1, md0)

定理
すべての非負整数d は幅w の相互交代形式としての表現を持ち、それは先頭の0 の個数を除いて一意的である。

幅wの非隣接形式

定義(幅w の非隣接形式)
符号付き桁の列は以下の3 つの条件を満たすとき、また、そのときに限り幅w の非隣接形式と呼ばれる:

  1. 0 でない最上位ビットは正である。
  2. どの連続したw 個の桁についても、その中の多くとも1 つは非零である。
  3. 各非零桁は奇数であり、その絶対値は2w-1 より小さい。

アルゴリズム: 幅w の非隣接形式の生成
入力:幅w,n ビットの整数d
出力:幅w の非隣接形式 sdn|sdn-1|...|sd0 of d
  • i <- 0
  • while d >= 1 do
    • if d is even then
      • sdi <- 0
    • else
      • sdi <- d mods 2w; d <- d - sdi
    • d <- d/2; i <- i + 1
  • return (sdn, sdn-1, ..., sd0)

アルゴリズムは最下位ビットから幅w の非隣接形式を生成する、これは右から左への計算で生成される。 非零ビットの濃度の平均はn -> inftyのとき漸近的には、1/(w+1) であり、桁集合T={+ -1, + -3, ..., + - (2w-1-1)} は最小と思われる。

幅w の非隣接形式を左から右に計算することは不可能だと思われる。そこが、他の方法を探す動機である。

相互交代形式の窓法:

このセクションでは、窓法を適用して相互交代形式の非零濃度をどのように減少させるかということを示す。 初めに右から左へ移り変わるように行われる幅w の非隣接形式の移動窓法を考える。以前から知られている生成方法とは対照的に、この新しい方法は桁上がりがない、すなわち各ステップですでに知られている多くともw+1 個の連続した入力されたビットについては十分である。

左から右へ行われる相互交代形式の幅w の移動窓法の類似の結果として、双対な新しいクラスである幅w の相互交代形式を定義する。 この変換は一般的な幅w に対する初めての左から右への記録方式である。

これらの関係は以下の図で示されている:

schema

右から左で行なわれる場合: 幅w の非隣接形式
提案した方式を記述するために、幅w に対する変換のテーブルを必要とする。初めに、最初と最後のビットが0 でないような相互交代形式の長さl の幅への変換を定義する:

General Conversion table

その上、すべての符号を変えた変換の類似を得る。幅w に対する完全なテーブルを生成するために、 長さl=2, 3, ..., w に対するすべての変換を考えなければならない。もし、l < wを満たせば、幅は先頭にある0 たちでいっぱいになる。

例: w=3 の場合、右から左で行われる移動窓法に対しては以下のテーブルを用いる:

幅w=3に対する変換表

アルゴリズム: バイナリ法から幅wの非隣接形式への右から左への変換
入力:幅w , n ビットのバイナリ列 d=dn-1|dn-2|...|d1|d0
出力:幅w の非隣接形式 sdn|sdn-1|...|sd0 of d
  • dn+w-2 <- 0; dn+w-3 <- 0; ...; dn <- 0; d-1 <- 0
  • i <- 0
  • while i <= n do
    • if di-1 = di then
      • sdi <- 0; i <- i + 1
    • else {The MOF windows begins with a non-zero digit righthand}
      • (sdi+w-1, ..., sdi) <- TablewSW(di+w-2 - di+w-1, di+w-3 - di+w-2, ..., di-1 - di)
      • i <- i + w
  • return (sdn, sdn-1, ..., sd0)

左から右への計算の場合:幅w の相互交代形式
提案した方式を記述するために、幅w に対する変換表を必要とする。最初と最後のビットが0 でないようなMOFの長さl の幅への変換は右から左への計算の場合と同じ方法で 完全に定義される（前述のテーブルを見て、指定の場所をよく考えよ）。 幅w に対する完全なテーブルを生成するために、以下のように長さl=2, 3, ..., w に対するすべての変換を考えなければならない。 唯一の違いは、もし、l < w を満たせば、先頭の0 たちの代わりに中の0 たちでいっぱいになるところである。 そのような例として、幅4 に対する変換表Table4SWを構成する:

w=4に対する幅wの相互交代形式への変換表

この表は、完全に相互交代形式の条件を満たすべきである。 通常、2つの異なる相互交代形式の列に関する等式、(* 1 -1) = (* 0 1), (* -1 1) = (* 0 -1)は同じパターンに変換される。 類似の方法として、TablewSWは一般の幅w に対して定義される。この場合、桁集合はT = { +-1, +-3, ..., +-2w-1-1 }であり幅w の非隣接形式と同じである。ゆえに、この方式では、2w-2 個の前計算された元しか必要としない。そのアルゴリズムは、左から右で行う幅w の相互交代形式を生成するためにこの表を最大限に利用する。

アルゴリズム:バイナリ法から幅w の相互交代形式への左から右への変換
入力:幅w ,非零n ビットのバイナリ列d=dn-1|dn-2|...|d1|d0
出力:幅w の相互交代形式 sdn|sdn-1|...|sd0 of d
  • d-1 <- 0; dn <- 0
  • i <- 0
  • while i >= w - 1 do
    • if di = di-1 then
      • sdi <- 0; i <- i - 1
    • else {The MOF windows begins with a non-zero digit lefthand}
      • (sdi, sdi-1, ..., sdi-w+1) <- TablewSW(di-1 - di, di-2 - di-1, ..., di-w - di-w+1)
      • i <- i - w
  • if i >= 0 then
    • (sdi, sdi-1, ..., sd0) <- Tablei+1SW(di-1 - di, di-2 - di-1, ..., d0 - d1, -d0)
  • return (sdn, sdn-1, ..., sd0)

Theorem
wMOFの非零濃度の平均は、n -> inftyのとき漸近的には、1/(w+1) である。

ランダムな整数d (0 < d < 1024 )に対するMOF表現の計算:

この変換器はランダムな整数d (0 < d < 1024 )に対するMOF表現の計算を行ない、その答えを出力します。その後、左から右もしくは右から左への移動窓法を適用することができます。

(0 < d < 1024)