人が犯した偶発的なエラーから識別子文字列を保護するタスクが発生する場合があります。 たとえば、支払いカード番号。 これを行うには、特別な方法で計算されたチェックディジットが行に追加され、ユーザーがこの番号を入力すると、データベースにアクセスせずに初期エラーチェックを実行できます。 最も簡単なオプションは、すべての桁の合計を10で割った余りを追加することです。この場合、任意の1桁（コントロール1桁を含む）の歪みが検出されやすく、そのような線はテストに合格しません。 しかし、チェックサムなどのいくつかの他のエラーは、たとえば、2桁の順列の置換を逃しますが、これもかなり一般的なエラーです。
銀行カード番号を保護するために、少し複雑なアルゴリズムであるムーンアルゴリズムが選択されました。 修正が1つ追加されました。偶数の位置にある数値に2を掛けてから合計します（9を超える場合は9が減算されます）。 これにより、任意の数字を歪めることに加えて、隣接する数字のほとんどの（すべてではありませんが）順列をキャッチできます。
（1桁の歪みに加えて）隣接する桁の順列を検出できるアルゴリズムはありますか？ はい、それらは存在しますが、何らかの理由であまり一般的ではありません。 これは、二面体グループに基づいたVerhuffアルゴリズムと、 Damm準グループに基づいたDammアルゴリズムです。 怖いですが、実際には複雑なことはありません（「グループ」の概念に精通している人にとって）。
オランダの数学者および彫刻家（写真の彼の彫刻の1つ）であるJacobus Verhoeffは、 二面体グループに基づくアルゴリズムを提案しました。 二面角グループは、回転と軸対称の両方を含む、通常のNゴンの対称のグループです。 そのようなグループは可換ではありません：番号が付け直された通常のポリゴンが最初に対称的に表示されてから回転される場合、ほとんどの場合、最初に回転してから表示される場合と同じではありません。 したがって、二面体グループの操作を使用して元の文字列の数字を連続的に「乗算」するとき、つまり 通常のNゴンに回転と対称マッピング操作を連続して適用すると、ほとんどの順列に対する保護が得られます。 大多数からですが、それでも全員からではありません。 Verhuffは、このアルゴリズムを改善することを提案しました。各桁を乗算してから、特別な表に従って、行の桁の位置に応じて別の桁に置き換えます。 テーブルは、1つの順列から前の結果に順番に適用することで取得されます。このようなアプリケーションを8回実行すると元の順序になります。したがって、テーブル8x10を事前に構築してそこから値を取得できます。 これらの順列のいくつかは、ソース文字列の隣接する桁の順序で起こりうるすべてのエラーを決定することを可能にします。つまり、これは、これらの2種類のエラーから保護するチェックディジットを見つける問題の完全かつ正しい解決策です。 どうやら、Verkhuffはランダム選択による順列の成功を発見しました。それらのかなりの数があります。
追加の変更なしで隣接する数字の順列を見つけることができるグループが存在するかどうかという問題は、長い間未解決のままでした。 そして、すでにXXI世紀の2004年に、ドイツの数学者Michael Dammがそのようなグループの存在を証明しました。それらは弱く完全に反対称なクワジグループと呼ばれます。 私はそれらを構築する方法を完全に理解していません;希望する人はそれを公開することによってこれを自分でやろうとすることができます。 クイックルックではそれほど複雑に見えませんが（質問が長い間開かれているのは奇妙なことです）、実際の実装には、より簡単な方法があります。 既製のテーブルを使用します。
次に、次の主要な質問に進みましょう。10進数の文字列ではなく、16進数、base64、base58などの任意の文字列を保護する必要がある場合はどうでしょうか。 つまり、10進数システムの特定のケースではなく、一般的な形式で問題を解決することです。
Moonアルゴリズムはこのケースに問題なく拡張されますが、隣接する数字のすべての順列を検出するわけではないため、それほど興味深いものではありません。 任意のサイズの反対称準グループを構築する方法は完全に明確ではありません。 Verhuffアルゴリズムの場合、サイズNの2面体グループは簡単に作成できますが、置換テーブルが必要です。これは、どこで入手できるかが不明です（また、存在するかどうかも不明です）。 これが最後の質問の研究であり、私は始めました。
グーグルでは、N = 64に対して、個別の試行と「かなり良い」ソリューションの使用（つまり、ほぼすべての順列の検出）しか得られませんでした。
おそらく、目的の順列を見つけるために試行され、テストされたすべての方法を説明するわけではありませんが、結果は得られませんでした。 特定の問題を解決しようとしました。base64とbase58の順列を見つけて、隣接する数字の順序を変更しないようにします。 私は、異なる最適化オプションを使用したランダムまたはシーケンシャル検索によってそのような順列を見つける試みが失敗したとしか言えません。 しかし、最終的に、私は任意の偶数の一般的な解決策を見つけました。
順列は次のとおりです。
0, N-1 .. N/2+1, 1 .. N/2
たとえば、N = 10の場合、これは次のようになります。
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
この順列には、もう1つの注目すべき特性があります。常に12の期間（N> = 8の場合）があるため、12xNテーブルを事前に構築してそこから数字を取得できます。
以下は、base58のVerhuffアルゴリズムの拡張案の実装例です （厳密には、これはVerkhuffアルゴリズムではなく、その一般化です）。 完全なライブラリではなく、単なるユーティリティ、いわば概念実証です。
この順列に望ましい特性があり、期間が12であることの証明は、後で提供します。 余白のスペースが小さすぎて、ここに収まりません。