表に基づくアルゴリズム

ウィキペディア小見出し辞書

表に基づくアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/12 06:49 UTC 版)

「ヴァーヘフアルゴリズム」の記事における「表に基づくアルゴリズム」の解説

ヴァーヘフアルゴリズムは3つの表を使って実装できる: 積表d・逆元表inv・そして置換表pである。 d(j,k)k0123456789j00 1 2 3 4 5 6 7 8 9 11 2 3 4 0 6 7 8 9 5 22 3 4 0 1 7 8 9 5 6 33 4 0 1 2 8 9 5 6 7 44 0 1 2 3 9 5 6 7 8 55 9 8 7 6 0 4 3 2 1 66 5 9 8 7 1 0 4 3 2 77 6 5 9 8 2 1 0 4 3 88 7 6 5 9 3 2 1 0 4 99 8 7 6 5 4 3 2 1 0 inv(j)j00 14 23 32 41 55 66 77 88 99 p(pos,num)num0123456789 pos (mod 8)00 1 2 3 4 5 6 7 8 9 11 5 7 6 2 8 3 0 9 4 25 8 0 3 7 9 6 1 4 2 38 9 1 6 0 4 3 5 2 7 49 4 5 3 1 2 6 8 7 0 54 2 8 6 5 7 3 9 0 1 62 7 9 3 8 0 6 4 1 5 77 0 4 6 9 1 3 2 5 8 最初の表dは、二面体群D5の積に基づくものであり、単にその群のケイリー表（英語版）である。この群は可換ではない、つまりある値jとkに対して、d(j,k) ≠ d(k, j)であることに注意せよ。 逆元表invは数字に対して積における逆元、つまりd(j, inv(j)) = 0を満す数を表す。 置換表pは各数字に対して、数値の中における位置を元に、置換を適用する。これは実際には単一置換(1 5 8 9 4 2 7 0)(3 6)を繰り返し適用したものである。つまり、p(i+j,n) = p(i, p(j,n))である(参考: [要説明] ヴァーヘフチェックサムの計算は次のように実行される: 数値の各桁から配列nを作成する。桁は右から左へ取る(最も右の桁がn0,となる)。 チェックサムcを0に初期化する。 配列nの各添字i(0から始まる)に対して、cをd(c, p(i mod 8, ni))で置き換える。 元の数値はc = 0となるとき、かつそのときのみ妥当である。 チェックデジットを生成するには、0を末尾に追加して上記の計算をする。すると正しいチェックデジットはinv(c)となる。