Luhnアルゴリズムは誤りを検知できない場合がある

Pocket

どうも。

昨日、基本情報技術者試験の午後の問8のアルゴリズムがLuhn mod Nアルゴリズムであることを知りました。

調べてみると、「N種類の文字に0からN-1までの数を割り当てたとき、0番とN-1番(最初と最後)の文字が入れ替わった場合どこで入れ替わっても誤りを検知できない」らしい。

それを知って、理系の血が騒いでどうしても証明したくなったのでします。

奇数番目同士・偶数番目同士で文字が入れ替わった場合どの文字同士でも検出できないのはこの前の記事に書いたとおりです。

なので奇数番目と偶数番目で入れ替わった場合でも検知できないことを証明したいと思います。

誤りを検知できないということは、入れ替わる前と後でどちらを計算しても同じ検査文字が生成されるということなので、
N種類の文字に0からN-1までの数を割り当て、[a]をa番に割り当てられた文字とした時、
[0][N-1][N-1][0]の検査文字が一致するということなので、生成手順に当てはめると次の式が立てられる。
(%は余剰演算を表す)

0 + (2(N-1) - 2(N-1)%N)/N + 2(N-1)%N = N-1 + (2*0 - 2*0%N)/N + 2*0%N

式を変形すると

(2(N-1) - 2(N-1)%N)/N + 2(N-1)%N = N-1
(2(N-1) - (N + N-2)%N)/N + (N + N-2)%N = N-1
(2N-2 - N%N - (N-2)%N)/N + N%N + (N-2)%N = N-1
(2N-2 - (N-2))/N + (N-2) = N-1
(2N-2 - N -2)/N + N - 2 = N-1
N/N + N - 2 = N-1
1 + N - 2 = N-1
N-1 = N-1

なので検査文字はどちらもN-1に割り当てられた文字になる

よってLuhn mod Nアルゴリズムでは、0番とN-1番(最初と最後)の文字が入れ替わった場合、誤りを検知できない。

 

以上。

解けた時はすごくスッキリしました。

ではでは。

The following two tabs change content below.
みどりごけ

みどりごけ

スペシャルエグゼクティブアドバイザーほしい物リスト
どこぞのシェル芸大好き鯖管(自称ではない) / 基本情報技術者 / Linux (LPIC2保有) / C# / PHP / JavaScript / 食べ鉄 / Minecraft / ETS2 / GTAV / Ingress
みどりごけ

最新記事 by みどりごけ (全て見る)

コメントを残す