2007-02-21 [長年日記]
■ISBN(旧)のチェックデジットと剰余の関係
旧ISBNのチェックデジット計算方法は以下の通り。
ISBNの頭9桁が 479732973 だとする。
各桁の数字に、左からそれぞれ10,9,8,7,6,5,4,3,2を掛けて和を取る。
つまり、
4×10＝40 7×9＝63 9×8＝72 7×7＝49 3×6＝18 2×5＝10 9×4＝36 7×3＝21 3×2＝6
となり、
40+63+72+49+18+10+36+21+6=315
となる。
和を11で割ったあまり(以下"剰余"と表現する)を算出して0〜10の値を得る。その値に応じて、
0の場合、チェックデジットは"0"。
1の場合、チェックデジットは"X"。
それ以外の場合、"11-剰余"をチェックデジットとする。
315 ÷ 11 = 28 あまり 7
であり、チェックデジットは"4"となる。
これは余談になるけど、新ISBN(要はJANコード)から旧ISBNのチェックデジットを計算するプログラムソースは、
で書いた。
ここまでは単なる「知識」だ。
では、「なぜこの様な計算方法になっているのだろう?」ということを考えてみよう。
先頭9桁は0〜9の数字だけが入るし、その各桁に掛けるのは2〜10である。
これを表にすると、1の段の代わりに10の段があって、1の行の上に0の行もある、九九の表もどきになるわけだ。実際は一番左の桁に10を掛けることになるので、本来の九九の表と「段」の並びを入れ替えて書いてみよう。
\(\begin{array}{r|rrrrrrrr}&10&9&8&7&6&5&4&3&2\\~~~~~~~~~~0&0&0&0&0&0&0&0&0&0\\~~~~~~~~~1&10&9&8&7&6&5&4&3&2\\~~~~~~~~~2&20&18&16&14&12&10&8&6&4\\~~~~~~~~~3&30&27&24&21&18&15&12&9&6\\~~~~~~~~~4&40&36&32&28&24&20&16&12&8\\~~~~~~~~~5&50&45&40&35&30&25&20&15&10\\~~~~~~~~~6&60&54&48&42&36&30&24&18&12\\~~~~~~~~~7&70&63&56&49&42&35&28&21&14\\~~~~~~~~~8&80&72&64&56&48&40&32&24&16\\~~~~~~~~~9&90&81&72&63&54&45&36&27&18\\~\end{array}\)
先のISBNの計算に出てきた部分がハッキリと判る様にしてみる。
\(\begin{array}{r|rrrrrrrr}&10&9&8&7&6&5&4&3&2\\~~~~~~~~~~0&0&0&0&0&0&0&0&0&0\\~~~~~~~~~1&10&9&8&7&6&5&4&3&2\\~~~~~~~~~2&20&18&16&14&12&\fbox{10}&8&6&4\\~~~~~~~~~3&30&27&24&21&\fbox{18}&15&12&9&\fbox{6}\\~~~~~~~~~4&\fbox{40}&36&32&28&24&20&16&12&8\\~~~~~~~~~5&50&45&40&35&30&25&20&15&10\\~~~~~~~~~6&60&54&48&42&36&30&24&18&12\\~~~~~~~~~7&70&\fbox{63}&56&\fbox{49}&42&35&28&\fbox{21}&14\\~~~~~~~~~8&80&72&64&56&48&40&32&24&16\\~~~~~~~~~9&90&81&\fbox{72}&63&54&45&\fbox{36}&27&18\\~\end{array}\)
箱で括られた部分を足して、11の剰余を取ったことになる。
さてこの「九九の表もどき」は、実は冗長だ。「全部足して11での剰余」を取っても、「11の剰余を足して、またさらに11の剰余」を取ってもいいからだ。
確認しておこう。
4×10＝40 40÷11=3 あまり 7 7×9＝63 63÷11=5 あまり 8 9×8＝72 72÷11=6 あまり 6 7×7＝49 49÷11=4 あまり 5 3×6＝18 18÷11=1 あまり 7 2×5＝10 10÷11=0 あまり 10 9×4＝36 36÷11=3 あまり 3 7×3＝21 21÷11=1 あまり 10 3×2＝6 6÷11=0 あまり 6 7+8+6+5+7+10+3+10+6=62 62÷11=5 あまり 7
となって結果は同じ。
したがって「九九の表もどき」も先に剰余の形で書いておけばよい。
\(\begin{array}{r|rrrrrrrr}&10&9&8&7&6&5&4&3&2\\~~~~~~~~~0&0&0&0&0&0&0&0&0&0\\~~~~~~~~~1&10&9&8&7&6&5&4&3&2\\~~~~~~~~~2&9&7&5&3&1&10&8&6&4\\~~~~~~~~~3&8&5&2&10&7&4&1&9&6\\~~~~~~~~~4&7&3&10&6&2&9&5&1&8\\~~~~~~~~~5&6&1&7&2&8&3&9&4&10\\~~~~~~~~~6&5&10&4&9&3&8&2&7&1\\~~~~~~~~~7&4&8&1&5&9&2&6&10&3\\~~~~~~~~~8&3&6&9&1&4&7&10&2&5\\~~~~~~~~~9&2&4&6&8&10&1&3&5&7\\~\end{array}\)
この表の各列を観察してみると、「なぜ11の剰余を取るのか?」が判る。
……
各列に同じ数字は一つもでてこない。
つまり、(例えば数字を手で入力するなどで)どこか1ヶ所を間違えたとしても、必ず別のチェックデジットが出てくるという仕組みになっているのだ。
11で剰余を取ることが効いている。
11が10より大きな素数であること――2〜10までの数との共通の因子(素因数)を持たないということがポイントだ。
チェックデジットに使えるキャラクタに制限が無ければ、剰余を13で取っても17で取ってもよい。でも、12や14や15では駄目なのだ。
そしてもう一つ。
これは自明ではないけど――表から全ての組み合わせを観察するか、あるいは証明を与える必要があるのだけど――どこかの数字とどこかの数字を入れ換えても別のチェックデジットが出てくる様にもなっている*1。
と、まぁこれは10年ぐらい前にチェックデジット計算方法を眺めていて気がついたことである。
チェックデジットが何のためにあるのか? と言われれば誤入力した際にそれをエラーとして弾くためだろう。
ならばチェックデジットの計算方法は、その様にデザインされているハズだ、と考えたのだった。
果たしてその計算方法は、1ヶ所の入力誤りや1ヶ所(1組)の数字の交換をエラーとして検出できるようになっていたわけだ。
ISBNのチェックデジットに限らず、世の中にあるチェックデジットは前述の性質のうち、少なくともどちらか一方を持っているはずである。
そうなっていなかったらデザインが悪いということ。……だと思う。
ずっと後になって、
- 作者: 結城 浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売: 2005-03-24
- ASIN: 4797329734
- メディア: 大型本
の「剰余」の章を読んでいたときに思い出していた。
始めに出したISBNの例は、実はこの本のそれである。
追記(2007/3/7)
- 作者: セアラ フラナリー,デイヴィッド フラナリー
- 出版社/メーカー: 日本放送出版協会
- 発売: 2001-08
- ASIN: 4140806311
- メディア: 単行本
を読書中。上に書いたことに近い内容のことが載っていた。
現代の暗号方式(のうちの多数)が整数論、とりわけ剰余や素因数と深い関係があることを考えると、この本にISBNの話題が出てくるのは不思議でない。正直「やはりISBNの話は良い例になるのだな」と改めて思った。
実はこれを書いた理由というのはどこかのblogで、「プログラマの数学(結城 浩)を読んでみて、プログラマと関係がない」と思ったというエントリを読んだからなのだった。
剰余の裾野には暗号方式という大きな沃野があり、そしてその一角にチェックデジットやチェックサムといった小さな(けれども軽んずべからざる)領域があるのだと、そう思いこれを書いた。
■素数ゼミの謎
上の話がピンとこない人には、
- 作者: 吉村 仁
- 出版社/メーカー: 文藝春秋
- 発売: 2005-07-12
- ASIN: 4163672303
- メディア: 単行本
がいいかもしれない。
正直私はあまり面白くなかった。短時間で読めてしまったし。
セミが13や17といった、素数を周期とする特性を自然のうちに獲得したというのは、確かに驚く他は無い。
だけどそこから観測・推測できる数学的な性質は、改めて説明される必要を感じなかったから「私の」評価は低い。
とはいえ、Amazonのレビューの点数が高いことには納得できる本である。
*1 同じ数字を入れ替えたら同じチェックデジットが出てくるけど、それは「入力間違いではない」のでOK。また、各桁に2〜10という別々の数を掛けているのも重要。これにより、"0"と"他の数"を入れ替えた時に別のチェックデジットがでてくるようになっているわけだ。