コーディングと暗号化の数学的基礎

コンピュータおよび通信ネットワークにおける加入者の情報相互作用は、さまざまな種類のエラーおよび妨害の発生につながる妨害の影響を受けやすい。送信されたメッセージのエラーに加えて、違反者のメッセージのコンテンツへの不正アクセスが可能です。これらの望ましくない現象との戦いは何千年も続いていますが、成功はさまざまです。インターネットの作成者は、現在のようにそれをまったく考えていませんでした。当時、彼らはハッカーについてさえ考えていませんでした。



情報対立の主な理論的問題であるそれらを解決するタスクは、コドロジー、クリプトロジー、ステガノロジーの理論に割り当てられており、コドアナリシス、クリプトアナリシス、ステガナリシスの方向性が世界中で集中的に発展しています。実用的な側面も脇にありませんが、ロシア連邦では活動がそれほど高くなく、若者の慣性が影響を及ぼしていることに注意します（私自身はすでに90年を交換しましたが、Habr政権は1950年に年齢制限を制限しました）。もちろん、私の意見は、子孫（曾孫まで）の観察とインターネットでのコミュニケーション、そして私がパートタイムで働いている会社の研修生や従業員とのコミュニケーションに限定されています。メディアも否定性を追加しています。若者の中には少し賢くなった人もいます。丘を越えてください。あなたは他人の行動を自分で見ることができます。

出版物のガイド付きツアー

テクニカルデバイスの開発（合成）には、開発者からの特定の知識、それらを使用する能力、およびこの種の他のスキルが必要です。そのような知識の本質的な要素は数学です。これらは、原則として、代数、離散数学、幾何学、物理学、数学的論理などです。この記事では、古典的な表現ではなく、十分なレベルの厳密さと正確さを備えた代数構造について考察します。私の主な仕事は、テキストや研究で使用するもののプレゼンテーションのアクセス可能性と明確さを確保することです。



たとえば、ここではGF拡張フィールドが使用されます（2 ⁸）そして、それなしでやったら、価値のあることは何も言えません。私の評価基準は単純です。各学期2、または異なる研究グループでの3つの試験とテスト。そこで私は、私が説明し、実践に移し、試験券の回答で何が返されるかを聞いて見ます。試験の回答の分析は非常に役立ちます。何かが違った、より良い言い方をされるべきだったと思います。



そして、ここでのプロパティZ _N複合N = pqを法とする有限数値残差リングの解を使用して、新しい元のアプローチのフレームワーク内で多数を因数分解する問題の解決策を見つけます。以降の各出版物では、標準の数学ツールの一部を転送することは不合理であることが明らかであるため、すべてを1つの場所に収集し、必要に応じて、ここで読者に対応することにしました。



ここでは、平面上の楕円曲線の点のグループが考慮され、使用されます。グループ内の合計操作は非常に特殊なものであり、HECのメンバーからでも、曲線のポイントをどのように追加するかなど、複雑な質問が発生します。

グループ

まず、必要な定義をいくつか紹介します。



定義。有限セットAセット、任意のn個のオブジェクトのコレクション$$${a_1,a_2,..., a_n}$、任意の順序でリストされていますが、重複はありません。セットは、その要素に対して1つ（または複数）の操作と関係が指定されている場合は構造化でき、操作が指定されていない場合は非構造化できます。



以下に、リマインダーとして、有限の離散セットを使用したアクション（操作）の表を示します。わかりやすくするために、図には連続セットAとBも示しています。



セットを使用した操作の表





定義。操作は、マッピングA×A→A、またはたとえばa・b = cです。 a、b、c∊A。算術以外の代数構造での操作が考慮されます：単項（たとえば、反転b ^-1）、二項、三項、...、n項（オペランドの場所の数に応じて）、または乗算順列、モジュラー（（mod R）で結果を取得）など。要素aおよびbは、ab = baの場合、順列または転流すると言われます。



定義。グループは、単一の操作が指定される（任意の性質の）G要素のセットですが、加算（+）にすることができ、グループは加法と呼ばれ、その中立要素（0）または乗算（◦）は乗法と呼ばれます。、その中立的な要素（1）ですが、原則として、これらの操作は通常の算術ではなく、特別な操作です。グループはしばしば記号（G、◦）で示されます。すべてのグループの中で、対称グループには重要な場所が与えられます。$$$S_n$次数n個の順列。グループのプロパティを保持するグループの要素の一部は、サブグループと呼ばれます。本質的に、これらは同じグループであり、元のグループよりも小さいだけです。これはグループの非公式な定義であり、正式な定義は少し後で与えられます。



すべてのa、bに対して可換法則ba = abを満たすグループGは、数学者Abel（1802 -1829）Abelianにちなんで呼び出されます。



加法グループの例は、ハミングコードの単語のセットです（ここを参照））。このグループの操作は16次です-（mod2）による単語の合計。このグループでは、コードのサブグループによる128ワードのグループの連続したクラスへの分解操作が実行され、Keliテーブルも作成され、グループの要素がエンコーダー（次元4のスペースに基づく）およびデコーダーで使用されます。一言で言えば、この例は、非常に重要な実際的な問題（コミュニケーション）を解決するために、小さなグループでもどのように使用できるかを明確に示しています。



対称順列（順列）グループは、グループ理論では非常に重要です。この重要性は、任意のサブジェクト領域で発生するグループには、順列上で同形の対称グループ（サブグループ）が存在するという定理によって決定されます。それからそれを研究する仕事は新しいオープングループの研究者のために単純化されます。同形順列グループのほとんどすべてのプロパティは、新しいグループにも保持されます。



簡単な例から始めましょう。 N個の要素が与えられ（1、2、3、...、nの数字で表します）、それらから順列を形成します。その数はnです。 = 1 2 3 ... n。値n = 3、次に3に制限しましょう！ = 6。



定義。グループの順序-グループ内の要素の数は、その順序と呼ばれます。この例では、番号6がグループの順序です。



グループでは、各要素にはグループの順序の除数である順序もあります。

定義。グループの要素の次数は、乗法グループ内の要素の最小指数（加法b + b + b + b + ... b = nb = 0、次数= n）で、たとえば（$$$_4$）³= 1、注文順序（$$$_4$）= 3。



対称グループ内$$$S_n$演算は、順列の乗算です。次数nの各順列は、各行と列に1つの単位が含まれる二乗順列n×n行列に関連付けられているため、この乗算は行列乗算に似ています。これは、対称グループについて以下に示されています$$$S_3$。







グループとその要素を操作するのに便利なように、数学者のKeliは、グループ操作の表（限られたサイズ）を提案しました。行と列の交点のセルに、それらを示す要素を使用した操作の結果が表示されます。テーブル内の結果（および行/列の指定）は、スペースを節約する10進要素番号で表されます。



グループの要素（順列）の乗算テーブル $$$S_3$





Keliテーブルのプロパティを使用すると、乗算テーブルの36個のセルへの入力が簡単になります。

-すべての行と列には、グループ全体の要素が含まれています。

-極端な列は字句的に順序付けられ、反対方向に配置されます（最初の上部/下部-最後の列はその逆です）

-テーブルの主対角線には要素の正方形があり、1がある場合、対応する要素はインボリューションです。の革命$$$S_3$されています$$$_1,_2,_3,_6$

要素の位置の対称性は、マトリックスの対角線に関して満たされます。

テーブルのプロパティを使用すると、テーブルに入力するときに、計算を13ペアの要素のみに制限できます（これらは上に表示されています）。

対称グループ $$$S_4$

グループ $$$S_3$次数は小さく（6）、プロパティを説明するのにあまり便利ではありません。以下に、対称グループの例を示します。$$$S_4$24受注が。次数nのすべての偶数の順列は、記号A_nで示される、対称グループ内の交互のサブグループを形成します。







表2を使用して、要素の任意のペアの製品を見つけることができます$$$S_4$またはそれらのチェーン全体。ただし、結果に次の要素を順次乗算することによって検出されます。作品の要素を並べ替えることはできません。行列の乗算と同様に、順列を乗算する操作は可換ではありません。 1つの要素は、1になるまで何度も乗算すると、すべての中間結果の循環グループを形成します。このような循環サブグループの順序はジェネレーターの順序であり、元の大きなグループの順序を分割する必要があります。



乗算表によると、大きなグループ内にサブグループがあります。小さいサブグループの順序は、大きいサブグループの順序を分割する必要があることに注意してください。

我々は、環状基構成要素P₁₄生成します。我々はpの交差点で見つけライン14で表2を入力します₁₄列要素P ₂₄。ライン24において、我々は、要素p見つける_11をカラム14との交点のセル内に、そして最後にカラム14との交点における列11のセルでは、要素p見つける₁、すなわち ニュートラル要素1。したがって、p ₁₄・p ₁₄・p ₁₄・p ₁₄ = p ₁、これらは4次サブグループの要素であり、その値は次数24を完全に分割します：4 =6。そのために、Keliテーブルを作成できます。見られるもの以外の要素が表示されません。このサブグループでは、要素p ₁₄及びp _11は、 4次を有し、そしてP ₂₄秒が退縮あります。

グループの形態

グループ（G、*）のグループ（G '、◦）へのマッピングfは、任意のa、b∊G、f（a * b）= f（a）◦f（b）の場合、ホモモルフィック（またはホモモルフィズム）と呼ばれます。通常、これらの等式はf（e）= e '、

f（a ^-1）=（f（a））^-1として継続します。等式の右側の表記は画像を示し、画像と呼ばれます。左側の表記は、マッピングfのプレイメージです。一般に、イメージとプレイメージの操作は一致しません。ホモモルフィズムfの下でのアイデンティティ（G '、◦）のプリイメージは、このホモモルフィズムのカーネルと呼ばれ、kerfで表されます。学年でよく知られている例は、このようなマッピング

ログ（a◦b）=ログ（a）+ログ（b）です。



画像の要素に操作（+）があり、プリイメージでは要素は乗算の操作（◦）によって接続されています。グループの同形画像はグループ（サブグループ）です。つまり、GのG 'へのf-同形性であり、Gがグループである場合、G'もグループです。同形性はグループ同形性の一般化です。fがGからG 'への1対1の同形性マッピングである場合、それは同形性であり、G≈G'として表されます。

画像の（マッピングfがグループ操作を保持する）ようなマッピングf：G→G 'が存在する場合、操作（・）および（*）を持つ2つのグループGおよびG'は同形と呼ばれます。



定理。 HをグループGの通常のサブグループとし、G = G / Hとします。次いで、上のグループGの写像f G式f（A）によって与え= A同形です。この同形性の核心はHです。この同形性はしばしば自然（標準）と呼ばれます。

グループの同形性は、基本的に標準的な同形性によって使い果たされます。



サブグループH = {1,8、17,24}に関する次数24のグループGをコセットに分解し、この分解のためにサブグループHに関する商グループを構築しましょう。この目的のために、サブグループHの要素の左右の積を列に書き込みます。







次数24のグループGのサブグループHに関するコセットへの分解の表では、列l1、l2、l3、l4、l5が左側の名前で示され、n1、n2、n3、n4、n5-右側のコセット、列ごとに1つのクラスの主要な代表が次の行。



真ん中の列Hは4次グループ（同形性の核）です。列には、クラスの主要な代表者とグループHの要素の積が入力されます。列に入力された後、クラスが比較されます。左右のクラスの構成が一致する場合、それらは単にコセットクラスについて話し、H = K0、K1、K2、K3、K4、K5を示します。さらに、サブグループHは通常と呼ばれます。表に記入するとき、次のクラスの代表者は、すでに構築されているクラスに含まれていない要素から最小の要素Gを選択します。



得られたコセットは、サブグループHによってグループGの商グループと呼ばれる新しいグループの要素と見なされます（商グループG = G / Hが示されます）。この新しいグループでの操作は、クラスの乗算です。たとえば、K3×K5 = K2のように、クラスのペアごとに、4×4のテーブルが作成されます。このテーブルでは、行が最初の要素の要素でマークされ、列が2番目の要素でマークされます。さらに、乗算はグループGと同様に実行されます。このような乗算の結果、16個の要素が得られますが、これらはすべて同じクラス（この場合はクラスK2）に属しています。



同形性マッピングに加えて、同形性はエンドモルフィズムとオートモルフィズムです。グループGのそれ自体への同形性はエンドモルフィズムと呼ばれ、グループGのそれ自体への同形性はオートモルフィズムです。これらの概念は、注入、サージェクション、およびバイジェクションによる非構造化セットのマップの概念に匹敵します。



表2-ケリ対称グループ$\$インライン\$\; S\_4（乗算P\_k\; =\; P\_i\; P\_j）$$インライン$

通勤者

要素の各対に、GεB、我々は要素を関連付け、この一対の整流子と呼ばれる

[A、B] = ^-1 B ^-1 ABを。すべてのコミュテーターによって生成されたグループGのサブグループKは、グループGのコミュテーターサブグループまたは派生サブグループと呼ばれます。







グループGは、チェーンG⊇G'⊇G''⊇…⊇G ^（i） ⊇... ^（各サブグループG ^（i）は前のサブグループのコミュテーターサブグループ^）が、ユニットサブグループの有限数のステップの後に終了する場合（たとえば、G ^（F） = 1

のテーブル4、交互のサブグループG「= A_の4オーダー12がGから、正常です=$$このサブグループの左右のコセットが一致するため、24次のS 4（クラスは完全なグループを補完するものと同じです）$S_4$$$）。次に、表4は、整流器が1である新しいサブグループの要素G '' = {1,8,17,24}を含む小さな4×4テーブル（整流器）に折りたたまれます。表4は、グループの可解性を示しています。$S_4$$$。$S_4$

結論

この記事では、グループ理論の主な規定のいくつかについて説明します。これらは、技術的（理論的および数学的ではない）性質の出版物でよく使用されます。そのような出版物のテキストの理解は、主に数学的なツールの所持によって決定されます。



グループについては、商グループへの同形マッピングの例と手法が示されています。

数値例は、提示された資料のアクセス可能性を確保し、慎重な分析または手に鉛筆を使った繰り返しで、その理解と同化を大いに助けるように設計されています。これは単に古典的なマニュアルから欠落しています。これは多くの場合、スペースと時間を節約することに起因します。

このスタイルで続けるかどうかが明らかになる読者の反応を待っています。

文献

Avdoshin S.M.、Nabebin A.A.離散数学。モジュラー代数、暗号化、コーディング。 -M。：DMK Press、2017年。-352ページ。

アキモフO.E.離散数学。論理、グループ、グラフ-M 。：ラボベース。 Zn。、2001.-352p。

アンダーソンD.A. Discrete mathematics and combinatorics）、Moscow：Williams、2003、960p。

BerlekampE。代数コーディング理論。 -M 。：ミール、1971年。-478ページ。

ヴァウリンA.E.コンピュータのセキュリティ問題における個別の数学。 H 1- SPb。：VKAim。 A.F. Mozhaisky、2015.219p。

ヴァウリンA.E.コンピュータのセキュリティ問題における個別の数学。 H 2- SPb。：VKAim。 A.F. Mozhaisky、2017年。-151ページ。

D. Gorenstein、有限の単純なグループ。それらの分類の紹介-M。：Mir、1985.- 352p。

Graham R.、Knut D.、Ptashnik O.ConcreteMathematics。FoundationsofInformatics.-M。：Mir、1998.-703p。

エリザロフV.P.エンドリング。 -M。：Helios ARV、2006年。 -304ページ

イワノフB.N.離散数学：アルゴリズムとプログラム-M。：Lab.Baz。知識、2001.280ページ。

エルサリムスキーY.M.離散数学：理論、問題、応用-M。：Vuzovskaya kniga、2000。-280p。

Lidl R.、Niederreiter G.有限フィールド：2巻。Vol.1-M。：Mir、1988。 -430ページ

Lidl R.、Niederreiter G.有限フィールド：2巻。Vol.2-M。：Mir、1988。 -392ページ

Lyapin E.S.、Aizenshtat A.Ya.、Lesokhin M.M.、グループの理論に関する演習-モスクワ：Nauka、1967.-264p。

Mutter V.M.ジャミング防止情報伝達の基本。 -L。 Energoatomizdat、1990、288ページ。

A.A. Nabebin、Discrete Mathematics、Moscow：Lab。知識、2001.280ページ。

F.A.ノビコフ プログラマーのための離散数学。-SPb。：Peter、2000.-304p。

Hall M. Group Theory.-M。：Izd。IL、1962年。-468ページ。

シハノビッチYu.A. グループ、リング、ラティス。--SPb。：Kirtsideli、2006年。-368ページ

シュネパーマンL.B. 問題と演習における代数と数の理論のコース：2時間でパート2。-Mn。：Vysh。shk。、1987.-256p。

シュネパーマンL.B. 代数と数の理論における問題のコレクション-ミンスク：デザインPRO、2000年。-240ページ。