レッスン
理論 — スターゲートアドレス数学ダイヤラー
ゲートアドレスとは、重複のない順序付き選択 — すなわち順列です。順序が意味を持ち（同じ記号でも異なる順序でダイヤルすれば別のアドレスになります）、記号の重複もないため、これはまさに P(n, k) = n! / (n − k)! によって数え上げられるケースです。
各記号の意味
n- リング上で利用可能な記号の数：
39。 k- ダイヤルする記号の数：
7。 P(n, k)- 順序付き選択の総数、
39! / 32! = 77,519,922,480。 destinations- より少ない方の総数、
1,987,690,320— 7つのうち1つの役割が決められたときに、実際に目的地へと繋がるアドレスの数。
公式の導き方
- ダイヤル手順を直接数え上げます。記号の重複がないため、1つ目の記号の選び方は39通り、2つ目は38通り、3つ目は37通りとなり、7つ選ぶまで同様に続きます。
- 掛け合わせると
39 × 38 × 37 × 36 × 35 × 34 × 33となります。階乗を使って書くと39! / 32!になります。末尾の32!は使われていない部分そのものであり — これは上に表示されている公式= 77,519,922,480と一致します。 - ここで、最後の記号を出発点として固定すると、残りの38個から自由に選べるのは6個だけになります：
P(38, 6) = 38 × 37 × 36 × 35 × 34 × 33 = 1,987,690,320。これが2つ目の数値であり、ちょうど1つ目の数値を39で割った値になります。
表示の読み方
中央の公式を挟んで2つの計算結果が並んでいます。興味深いのはその比率です。目的地のアドレス数は、総数をちょうど 39 で割った値になっており、これは7つのスロットのうち1つを固定したことの算術的な特徴を示しています。
- 前提
- 記号の重複がなく、順序が重要であることを前提としています。前者の前提を外すと39を7乗することになります。後者の前提を外すと組合せを数えることになり、39個から7個を選ぶ組合せは
7! = 5040の倍率で小さくなります。 - 成り立たない場合
- 大きな数値は探索規模を過大評価させがちです。約20億というアドレス数は果てしない銀河のように思えるかもしれませんが、順列の総数はどれが有効であるかについては何も教えてくれません。7文字の文字列の大半が単語ではないのとまったく同じように、大部分の配列はどこにも繋がりません。可能性を数え上げるのは簡単な前半にすぎません。どれに意味があるのかを知ることが難しい後半であり、どんな階乗もそれを教えてはくれません。
全プロセスの詳細解説
-
17( i + 3)で重み付けされた7グリフのプリセットのチェックサム 8 ステップ
7グリフ（安定） プリセットは 3, 9, 17, 21, 28, 35, 1 をダイヤルします。パネルは 0 から数えてスロット i にあるグリフに 17(i + 3) の重みを掛け、それらを足し合わせて mod 97 で約減します。手計算でチェックサムを求め、さらに、それらのグリフのうち 2 つを逆の順序でダイヤルした場合に、それが検出されないことがあり得るかどうかを判定しなさい。
-
これ以降の計算はすべて重みに関する算術であるため、まず重みを書き出します。7 つのスロットと 7 つの重みがあり、それらは正確に 17 ずつ増加します。この規則性こそが、最後の証明全体の根幹をなすものです。
-
各グリフの番号に対応するスロットの重みを掛けて足し合わせます。この段階ではまだ余りの計算を行っていません。これは通常の和であり、必要ならすべての項から 17 を共通因数としてくくり出すこともできます。
-
次に 97 で割って余りを求めます。12,597 の中には 97 がちょうど 129 個含まれ、84 が残ります。これが チェックサム (mod 97) タイルに表示されている値であり、この導出においてツールから取得する最後の数値です。これ以降の計算はすべて自身で行います。
-
ここで、このタイルでは答えることのできない問いが生じます。スロット i と j のグリフを入れ替えたとします。和に含まれる他のすべての項は変化しないため、合計の変化量は 1 つだけです。つまり、2 つのグリフが互いの重みを交換したことになります。これを展開すると、重みは公差 17 の等差数列であるため、重みの差は 17(i − j) にまとまります。
-
この公式をそのまま信用するのではなく、検証してみましょう。スロット 0 と 1 にはそれぞれ 3 と 9 が入っているため、Δ = 17(0 − 1)(9 − 3) = −102 となり、−102 を mod 97 で考えると 92 になります。したがって 84 + 92 = 176、すなわち 79 になると予測されます。最初の 2 つを入れ替えた同じ 7 つのグリフ
?address=9,3,17,21,28,35,1をツールに入力すると、タイルには 79 と表示されます。 -
入れ替えが見過ごされるためには、Δ は単に小さいだけでなく、mod 97 で 0 にならなければなりません。つまり、チェックサムが再び 84 に一致する必要があります。したがって、97 は 17(i − j)(vj − vi) を割り切れなければなりません。97 は素数であり 17 を割り切らないため、積が素数の倍数となるのは因数の少なくとも 1 つがすでにその素数の倍数である場合だけです。ゆえに、97 はスロットの差またはグリフの差を 単独で 割り切れなければなりません。
-
どちらの差もそれを満たすことはできません。シェブロンは最大でも 9 個であるため、異なる 2 つのスロットの差は最大で 8 です。また、1 から 39 の間から選ばれた異なる 2 つのグリフの差は最大で 38 です。両方の差は 0 ではなく、ともに 97 より小さいため、Δ が mod 97 で 0 になることは決してありません。このチェックサムにおいて、2 つのグリフの入れ替え（転置）が見過ごされることはありません。これはこのアドレスに限ったことではなく、ダイヤル可能なあらゆるアドレスにおいて同様です。スロットの差が 97 未満に保たれるのは、シェブロンが 9 個だからです。URL を通じてより長いアドレスをツールに渡すと、この保証は真っ先に失われます。
-
すべての転置を検出できることは、アドレスの正しさを保証することと同義ではありません。そして、これこそがタイルが控えめながらも主張しすぎている点です。同じ 7 つのグリフの 他の 5,039 通りの並び順のうち、62 通りもが 84 という結果になります（97 等分に均等に分類された場合は約 52 通りとなるはずです）。誤った順序のおよそ 100 に 1 つが正しいものとして読み取られてしまいます。この仕組みは、最もよくある誤ダイヤルを排除するだけであり、それ以上のことは何もできません。
解答
84 — 2 つのグリフを入れ替えても、結果が 84 のままになることは決してありません。 ただし、この保証は境界条件によるものであり、チェックサム自体の固有の性質ではありません。97 が最長のスロット差と最大のグリフ差の両方よりも大きい場合にのみ成り立ちます。リングを 98 個のグリフに拡張すると、この保証は直ちに破綻します。1, 98, 17, 21, 28, 35, 3 と 98, 1, 17, 21, 28, 35, 3 はどちらもチェックサムが 35 となります。なぜなら、それらの差である 97 が法（モジュラス）によって打ち消されるからです（ここでは計算上拡張していますが、ツールのリングは 39 で停止します）。これこそが、IBAN のチェックディジットが mod 10 ではなく mod 97 で計算されるまさにその理由です。フィールドが変化し得るどの値よりも大きい素数を選べば、すべての転置が必ず検出されるようになります。ツールはチェックサムを計算するだけで、何が検出できるかについては何も示しません。そして 5,039 通り中の 62 通りという数値は、ツールが計算しない 2 つ目の事柄であり、このタイルを無条件に信用するのを思いとどまらせる理由でもあります。
-
参考文献 (1)
- Ordered selections without repetition, which is what P(n, k) counts: I. Niven, "Permutations and Combinations," in Mathematics of Choice: How to Count Without Counting, 7–26. Mathematical Association of America.