الأسس الرياضية للتشفير والتشفير

يخضع تفاعل المعلومات للمشتركين في شبكات الكمبيوتر والاتصالات لاضطرابات تؤدي إلى حدوث أخطاء واضطرابات بمختلف أنواعها. بالإضافة إلى الأخطاء في الرسائل المرسلة ، يمكن الوصول غير المصرح به إلى محتوى رسائل الجاني. كانت المعركة ضد هذه الظواهر غير المرغوب فيها مستمرة منذ آلاف السنين ، ولكن بنجاح متفاوت. لم يتصور مبدعو الإنترنت الأمر على الإطلاق كما هو عليه الآن. لم يفكروا حتى في المتسللين في ذلك الوقت.



يتم تعيين المشكلات النظرية الرئيسية لمواجهة المعلومات ، ومهام حلها إلى نظريات علم الشفرات وعلم التشفير وعلم الإخفاء ، حيث تتطور اتجاهات تحليل الكود ، وتحليل الشفرات ، والتحليل المخفي بشكل مكثف في جميع أنحاء العالم. الجوانب العملية أيضًا لا تقف جانبًا ، لكنني سألاحظ أن النشاط في الاتحاد الروسي ليس مرتفعًا جدًا ، ويؤثر الجمود الشبابي (لقد قمت بالفعل بتبادل العقد التاسع ، لكن إدارة Habr حددت الحد الأدنى للسن في عام 1950). رأيي ، بالطبع ، يقتصر على مراقبة الأبناء (حتى أحفاد الأحفاد) والتواصل على الإنترنت ، وكذلك مع المتدربين وموظفي الشركة التي أعمل فيها بدوام جزئي. كما تضيف وسائل الإعلام السلبية. لقد أصبح بعض الشباب أكثر حكمة ، فاذهبوا فوق التل. يمكنك أن ترى سلوك الآخرين بنفسك.

جولة إرشادية للمنشورات

يتطلب تطوير (توليف) الأجهزة التقنية من المطور معرفة معينة ، والقدرة على استخدامها ومهارات أخرى من هذا النوع. مكون أساسي لهذه المعرفة هو الرياضيات. هذه ، كقاعدة عامة ، الجبر ، والرياضيات المنفصلة ، والهندسة ، والفيزياء ، والمنطق الرياضي ، وما إلى ذلك. هنا في المقالة سننظر في الهياكل الجبرية ليس بالكامل في العرض الكلاسيكي ، ولكن بمستوى كافٍ من الصرامة والدقة. مهمتي الرئيسية هي ضمان إمكانية الوصول ووضوح عرض الأشياء التي أستخدمها في نصوصي وأبحاثي.



على سبيل المثال ، هنا يتم استخدام حقل امتداد GF (2 ⁸) وإذا استغنا عنها ، فلا شيء يستحق العناء. معايير التقييم الخاصة بي بسيطة. كل فصل دراسي 2 أو حتى 3 امتحانات واختبارات في مجموعات دراسية مختلفة. هناك أسمع وأرى ما شرحته ، وجلبته إلى الممارسة ، وما أعيد إلي في الإجابات على تذاكر الامتحان. تحليل إجابات الامتحان مفيد للغاية ، وأرى أنه كان يجب ذكر شيء ما بشكل مختلف وأفضل.



و هنا خصائص Z _Nيتم استخدام نموذج حلقة البقايا العددية المحدودة للمركب N = pq لإيجاد حل لمشكلة تحليل الأعداد الكبيرة في إطار نهج أصلي جديد. من الواضح أنه في كل من المنشورات اللاحقة سيكون من غير المعقول نقل جزء من الأدوات الرياضية القياسية ، لذلك تقرر جمع كل شيء في مكان واحد ، وإذا لزم الأمر ، مخاطبة القراء هنا.



هنا يتم أخذ واستخدام مجموعة من نقاط المنحنى الإهليلجي على مستوى. عملية الجمع في مجموعة من نوع خاص جدًا ، مما يتسبب في أسئلة محيرة ، مثل كيف يمكنك إضافة نقاط المنحنى ، حتى من أعضاء HEC.

مجموعات

نقدم أولا عددا من التعريفات الضرورية.



التعريف . مجموعة محدودة مجموعة أ ، مجموعة من أي كائنات ن$$${a_1,a_2,..., a_n}$مدرج بأي ترتيب ولكن لا يوجد تكرارات. يمكن هيكلة المجموعات ، بحيث يتم تحديد عملية واحدة (أو أكثر) وعلاقات على عناصرها ، وغير منظمة ، عندما لا يتم تحديد أي عمليات.



أدناه ، كتذكير ، يتم إعطاء جدول الإجراءات (العمليات) مع مجموعات منفصلة محدودة ، وللتوضيح ، تُظهر المخططات أيضًا المجموعات المستمرة A و B.



جدول العمليات مع المجموعات





التعريف . العملية هي تعيين A × A → A أو ، على سبيل المثال ، a · b = c ؛ أ ، ب ، ج ∊ أ. تعتبر العمليات في الهياكل الجبرية بخلاف العمليات الحسابية: أحادي (على سبيل المثال ، انعكاس ب ^-1 ) ، ثنائي ، ثلاثي ، ... ، n-ary (وفقًا لعدد أماكن المعاملات) ، أو الضرب التباديل ، المعياري (أخذ النتيجة بواسطة (mod R)) ، إلخ. يُقال إن العناصر a و b تتناوب أو تنتقل إذا كانت ab = ba.



التعريف . المجموعة هي مجموعة من عناصر G (من أي طبيعة) يتم تحديد عملية واحدة عليها ، ولكن يمكن أن تكون إضافة (+) وتسمى المجموعة مضافة ، ويسمى عنصرها المحايد (0) أو الضرب (◦) الضرب، عنصرها المحايد (1) ، لكن كقاعدة عامة ، هذه العمليات ليست حسابية عادية ، ولكنها عمليات خاصة. غالبًا ما يتم الإشارة إلى المجموعة بالرمز (G ، ◦) ؛ من بين جميع المجموعات ، يتم إعطاء مكان مهم للمجموعات المتماثلة$$$S_n$تباديل درجة n. تسمى أجزاء عناصر المجموعة التي تحافظ على خصائص المجموعة المجموعات الفرعية. في جوهرها ، هذه هي نفس المجموعات ، أصغر فقط من المجموعة الأصلية. هذا تعريف غير رسمي للمجموعة ، وسيتم تقديم التعريف الرسمي بعد ذلك بقليل.



المجموعة G ، التي تفي بالقانون التبادلي ba = ab للجميع a ، b ε G تسمى بعد عالم الرياضيات Abel (1802-1829) Abelian .



مثال على مجموعة مضافة هو مجموعة كلمات كود هامينج ( انظر هنا). العملية في هذه المجموعة هي الترتيب السادس عشر - تجميع الكلمات بواسطة (mod2). مع هذه المجموعة ، تم إجراء عملية التحلل إلى فئات متجاورة لمجموعة مكونة من 128 كلمة بواسطة مجموعة فرعية من الكود ، كما تم إنشاء جدول Keli ، وتُستخدم عناصر المجموعة في المشفر (أساس مساحة البعد 4) وفك التشفير. باختصار ، يوضح هذا المثال بوضوح كيف يمكن استخدام مجموعة صغيرة لحل مشكلة عملية مهمة جدًا (الاتصال).



مجموعات التقليب المتماثل (التقليب) مهمة جدًا في نظرية المجموعة. يتم تحديد هذه الأهمية من خلال النظرية ، التي تنص على أنه بالنسبة لأي مجموعة تنشأ في مجال موضوع تعسفي ، هناك مجموعة متماثلة (مجموعة فرعية) متشابهة لها على التباديل. ثم يتم تبسيط مهمة دراستها للباحث في مجموعة مفتوحة جديدة. تقريبًا جميع خصائص مجموعة التقليب المتشابه تحمل في المجموعة الجديدة أيضًا.



لنبدأ بمثال بسيط. يتم إعطاء عناصر N (نشير إليها بالأرقام 1،2،3 ، ... ، ن) ونشكل تباديل منها ، وعددها ن! = 1 2 3 ... ن. لنقصر أنفسنا على القيمة n = 3 ، ثم 3! = 6.



التعريف . ترتيب المجموعة - يسمى عدد العناصر في المجموعة بترتيبها. في المثال ، الرقم 6 هو ترتيب المجموعة.



في المجموعة ، كل عنصر له أيضًا ترتيب يمثل القاسم على ترتيب المجموعة.

التعريف . ترتيب عنصر المجموعة هو الأس الأصغر للعنصر في مجموعة المضاعفة (التعدد في المادة المضافة b + b + b + b + ... b = nb = 0 ، order = n) حيث يصبح عنصرًا محايدًا ، على سبيل المثال ($$$_4$) ³ = 1 طلب أمر ($$$_4$) = 3.



في المجموعة المتماثلة$$$S_n$العملية هي مضاعفة التباديل. هذا الضرب مشابه لضرب المصفوفة ، حيث أن كل تبديل من الدرجة n يرتبط بمصفوفة تبديل n × n مربع حيث يحتوي كل صف وعمود على وحدة واحدة. هذا موضح أدناه للمجموعة المتماثلة$$$S_3$...







لتسهيل العمل مع مجموعة وعناصرها ، اقترح عالم الرياضيات كيلي جدولًا لعمليات المجموعة (محدودة الحجم). في الخلية عند تقاطع صف وعمود ، يتم وضع نتيجة العملية مع العناصر التي تشير إليهما. يتم تمثيل النتيجة (بالإضافة إلى تعيين الصفوف / الأعمدة) في الجدول بأرقام العناصر العشرية ، مما يوفر مساحة.



جدول الضرب لعناصر (التباديل) لمجموعة $$$S_3$





يتم تبسيط الملء في 36 خلية في جدول الضرب باستخدام خصائص جدول Keli.

- تحتوي جميع الصفوف والأعمدة على عناصر المجموعة بأكملها.

- الأعمدة المتطرفة مرتبة حسب المعجم وموجهة بشكل معاكس (الأول أعلى / أسفل - آخر واحد هو العكس)

- على القطر الرئيسي للجدول توجد مربعات من العناصر ، إذا كان هناك 1 ، فإن العنصر المقابل لها هو الانقلاب ؛ في$$$S_3$هي $$$_1,_2,_3,_6$

- فيما يتعلق بأقطار المصفوفة ، يتم إجراء تناظر مواضع العناصر.

تسمح خصائص الجدول ، عند ملئه ، بتقييد الحسابات على 13 زوجًا فقط من العناصر (موضحة أعلاه).

مجموعة متماثلة $$$S_4$

مجموعة $$$S_3$لديه طلب صغير (6) وليس مناسبًا جدًا لتوضيح الخصائص. أدناه سنقدم أمثلة مع المجموعة المتماثلة$$$S_4$24 طلب. تشكل جميع التباديل الزوجية للدرجة n مجموعة فرعية متناوبة في المجموعة المتماثلة ، يُشار إليها بالرمز A _n .







يمكن استخدام الجدول 2 للعثور على منتجات أي زوج من العناصر$$$S_4$أو لسلسلتها بأكملها ، ولكن يتم العثور عليها من خلال الضرب المتسلسل للنتيجة بالعنصر التالي. لا يمكنك إعادة ترتيب العناصر في العمل. الضرب التبادلي ليس تبادليًا ، مثل ضرب المصفوفة. عنصر واحد ، عندما يضرب في نفسه عدة مرات حتى تحصل على 1 ، يشكل مجموعة دورية من جميع النتائج الوسيطة. ترتيب هذه المجموعة الفرعية الدورية هو ترتيب المولد ؛ يجب أن يقسم ترتيب المجموعة الأصلية الكبيرة.



وفقًا لجدول الضرب ، توجد مجموعات فرعية داخل مجموعة كبيرة. تذكر أن ترتيب المجموعة الفرعية الأصغر يجب أن يقسم ترتيب المجموعة الأكبر.

نقوم ببناء مجموعة دورية بتوليد العنصر ص ₁₄ . ندخل الجدول 2. في السطر 14 نجد عند التقاطع مع p ₁₄عنصر العمود ص ₂₄ ؛ في الصف 24 نجد في خلية التقاطع مع العمود 14 العنصر p ₁₁ وأخيراً في خلية الصف 11 عند التقاطع مع العمود 14 نجد العنصر p ₁ ، أي عنصر محايد 1. لذلك ، p ₁₄ · p ₁₄ · p ₁₄ · p ₁₄ = p ₁ ، هذه عناصر من المجموعة الفرعية من الدرجة الرابعة ، والتي تقسم قيمتها الترتيب تمامًا 24: 4 = 6. بالنسبة لها ، يمكنك إنشاء جدول Keli ولا يحتوي على لن تظهر أي عناصر باستثناء تلك التي تم العثور عليها. في هذه المجموعة الفرعية ، يكون للعنصر p ₁₄ و p ₁₁ الترتيب الرابع ، و p ₂₄ الثاني هو الانقلاب.

أشكال المجموعة

يسمى تعيين f لمجموعة (G ، *) لمجموعة (G '،،) متماثل الشكل (أو تماثل الشكل) إذا كان ، لأي أ ، ب G ، و (أ * ب) = و (أ) ◦ و (ب). عادة ما تستمر هذه المساواة على النحو f (e) = e '،

f (a ^-1 ) = (f (a)) ^-1 . يشير الترميز الموجود على يمين المساواة إلى الصورة ويسمى الصورة ؛ إلى اليسار ، الصورة المسبقة للتعيين f. في الحالة العامة ، لا تتطابق العمليات على الصورة والصورة. يُطلق على الصورة المسبقة للهوية (G '،) في ظل التشابه بين الأشكال f نواة هذا التشابه ويتم الإشارة إليها بواسطة ker f. من الأمثلة المعروفة من سنوات الدراسة

سجل الخرائط (أ◦ب) = السجل (أ) + السجل (ب).



عناصر الصورة مع وجود عملية عليها (+) ، وفي الصورة السابقة ترتبط العناصر بعملية الضرب (◦). الصورة المتجانسة للمجموعة هي مجموعة (مجموعة فرعية) ، أي إذا كان تماثل الشكل f لـ G على G 'و G هو مجموعة ، فإن G' هي أيضًا مجموعة. تماثل الشكل هو تعميم لتماثل المجموعة: إذا كانت f عبارة عن رسم خرائط متماثل من واحد إلى واحد لـ G على G '، فعندئذ يكون متشابهًا ، ويشار إليه بـ G≈G'.

مجموعتان G و G 'مع العمليات (·) و (*) تسمى isomorphic إذا كان هناك تعيين f: G → G' بحيث (يحافظ التعيين f على تشغيل المجموعة) للصورة ؛



نظرية. دع H مجموعة فرعية طبيعية لمجموعة G و G = G / H. ثم تعيين f للمجموعة G على G المعطى بالصيغة f (a) = aهو تشابه الشكل. نواة هذا التشابه هي H. وغالبا ما يسمى هذا التشابه الطبيعي (الكنسي).

يتم استنفاد تماثلات المجموعة بشكل أساسي من خلال التشابهات القانونية.



دعونا نحلل المجموعة G من الترتيب 24 فيما يتعلق بمجموعتها الفرعية H = {1،8 ، 17،24} إلى مجموعات تجميل ونبني لهذا التحلل مجموعة ناتج قسمة فيما يتعلق بالمجموعة الفرعية H. لهذا الغرض ، نكتب في أعمدة النواتج اليمنى واليسرى لعناصر المجموعة الفرعية H.







في جدول تحلل المجموعة G من الترتيب 24 إلى مجموعات تجميل فيما يتعلق بالمجموعة الفرعية H ، يتم تعيين الأعمدة l1 ، l2 ، l3 ، l4 ، l5 أسماء اليسار و n1 ، n2 ، n3 ، n4 ، n5 - cosets الأيمن ، الممثلون الرئيسيون للفئات ، واحد لكل عمود ، مكتوبون في السطر التالي.



العمود الأوسط H هو مجموعة من الدرجة الرابعة (نواة تماثل الشكل). تمتلئ الأعمدة بمنتجات الممثلين الرائدين للفئات وعناصر المجموعة H. بعد ملء الأعمدة ، تتم مقارنة الفئات. إذا تزامنت تراكيب الفئتين اليمنى واليسرى ، فإنهم يتحدثون ببساطة عن فئات coset ويشيرون إلى H = K0 ، K1 ، K2 ، K3 ، K4 ، K5. علاوة على ذلك ، تسمى المجموعة الفرعية H طبيعية . عند ملء الجدول ، يختار الممثل الرئيسي للفئة التالية أصغر عنصر G من العناصر غير المدرجة في الفئات التي تم إنشاؤها بالفعل.



تعتبر مجموعات التمام التي تم الحصول عليها أدناه كعناصر من مجموعة جديدة تسمى مجموعة حاصل المجموعة G من قبل المجموعة الفرعية H (يشار إلى مجموعة الحاصل G = G / H). العملية في هذه المجموعة الجديدة هي مضاعفة الفئات: لكل زوج من الفئات ، على سبيل المثال ، K3 × K5 = K2 ، يتم إنشاء جدول 4 × 4 ، حيث يتم تمييز الصفوف بعناصر العامل الأول ، والأعمدة - الثانية. علاوة على ذلك ، يتم إجراء الضرب كما هو الحال في المجموعة G. نتيجة هذا الضرب يعطي 16 عنصرًا ، لكنهم جميعًا ينتمون إلى نفس الفئة ، في حالتنا هذه الفئة K2.



بالإضافة إلى تعيينات تماثل الشكل ، فإن التشابهات هي تشابهات وتشكيلات تلقائية. يُطلق على التشابه في المجموعة G في حد ذاته اسم التشابه الداخلي ، والتشابه للمجموعة G على نفسها هو تشابه ذاتي. هذه المفاهيم قابلة للمقارنة مع مفاهيم خرائط المجموعات غير المهيكلة عن طريق الحقن ، والتطرف ، والانحراف.



الجدول 2 - مجموعة كيلي المتماثلة$\$\; مضمنة\; \$\; S\_4\; (الضرب\; P\_k\; =\; P\_i\; P\_j)$$ مضمنة $

العاكس

لكل زوج من العناصر a ، b G ، نربط عنصرًا يسمى عاكس هذا الزوج

[أ ، ب] = أ ^-1 ب ^-1 أب. تسمى المجموعة الفرعية K للمجموعة G التي تم إنشاؤها بواسطة جميع مبدلاتها المجموعة الفرعية للمبدل للمجموعة G أو المجموعة الفرعية المشتقة.







تسمى المجموعة G قابلة للحل إذا كانت السلسلة G G '⊇ G' '⊇ ... ⊇ G ⁽ⁱ⁾ ⊇ ... ، حيث تكون كل مجموعة فرعية G ⁽ⁱ⁾ هي العاكس للمجموعة السابقة ، تنتهي بعد عدد محدود من الخطوات على مجموعة الوحدة الفرعية ، على سبيل المثال ، G ^(و) = 1.

في الجدول 4 ، المجموعة الفرعية البديلة G '= A _{4 من} الترتيب 12 طبيعية ، من G =$$$S_4$ من أجل 24 ، حيث أن cosets الأيسر والأيمن لهذه المجموعة الفرعية يتطابقان (الفئات هي نفس المكمل للمجموعة الكاملة $$$S_4$). في هذه الحالة ، يتم طي الجدول 4 في جدول 4 × 4 أصغر (عاكس التيار) يحتوي على العناصر G '= {1،8،17،24} من مجموعة فرعية جديدة ، مبدلها هو 1. يوضح الجدول 4 قابلية حل المجموعة$$$S_4$...

خاتمة

تناقش المقالة بعض الأحكام الرئيسية لنظرية المجموعة ، والتي غالبًا ما تستخدم في المنشورات ذات الطبيعة التقنية (وليس النظرية والرياضية). يتم تحديد فهم نص هذه المنشورات إلى حد كبير من خلال امتلاك الأدوات الرياضية.



بالنسبة للمجموعة ، يتم تقديم مثال وتقنية لرسم خرائط متجانسة الشكل في مجموعة حاصل القسمة.

تهدف الأمثلة العددية إلى ضمان توافر المواد المقدمة والمساعدة إلى حد كبير في فهمها واستيعابها ، مع التحليل الدقيق أو حتى التكرار باستخدام قلم رصاص. وهو ببساطة مفقود في الكتيبات الكلاسيكية. غالبًا ما يُعزى ذلك إلى توفير المساحة والوقت.

أنا في انتظار رد فعل من القراء ، والذي سيوضح ما إذا كنت ستستمر في هذا الأسلوب أم لا.

الأدب

Avdoshin S.M.، Nabebin A.A. الرياضيات المنفصلة. وحدات الجبر والتشفير والترميز. - م: مطبعة DMK ، 2017. -352 ص.

Akimov O.E. الرياضيات المتقطعة ، المنطق ، المجموعات ، الرسوم البيانية - م: مختبر ، قاعدة. Zn. ، 2001. -352 ص.

أندرسون د. الرياضيات المتقطعة والتوافقية) ، موسكو: ويليامز ، 2003 ، 960 ص.

Berlekamp E. نظرية الترميز الجبري. - م: مير ، 1971. - 478 ص.

فاولين أ. الرياضيات المتقطعة في مشاكل أمن الحاسوب. ح 1- SPb .: VKA im. أ. Mozhaisky، 2015.219 ص.

فاولين أ. الرياضيات المتقطعة في مشاكل أمن الحاسوب. ح 2- SPb.: VKA im. أ. Mozhaisky، 2017. -151 ص.

جورنشتاين ، مجموعات بسيطة محدودة. مقدمة لتصنيفهم. - م: مير ، 1985. - 352 ص.

Graham R.، Knut D.، Ptashnik O. Concrete Mathematics. Foundations of Informatics.-M: Mir، 1998.-703 p.

إليزاروف ف. حلقات النهاية. - م: هيليوس ARV ، 2006. - 304 ص.

إيفانوف ب. الرياضيات المتقطعة: الخوارزميات والبرامج - م: مختبر قاعدة. المعرفة ، 2001.280 ص.

يروساليمسكي ي. الرياضيات المنفصلة: النظرية ، المشاكل ، التطبيقات - م: Vuzovskaya kniga ، 2000.280 ص.

Lidl R. ، Niederreiter G. الحقول المحدودة: في مجلدين ، المجلد .1 -M: Mir ، 1988. - 430 ص.

Lidl R. ، Niederreiter G. الحقول المحدودة: في مجلدين ، المجلد. 2 -M: Mir ، 1988. - 392 ص.

Lyapin E.S. ، Aizenshtat A.Ya. ، Lesokhin M.M. ، تمارين حول نظرية المجموعات. - موسكو: Nauka ، 1967. -264 p.

تمتم ف. أساسيات نقل معلومات مكافحة التشويش. -ل. Energoatomizdat ، 1990 ، 288 ص.

نبين ، الرياضيات المتقطعة ، موسكو: مختبر. المعرفة ، 2001.280 ص.

نوفيكوف رياضيات متقطعة للمبرمجين. - SPb .: Peter، 2000. - 304 p.

Hall M. Group Theory.-M: Izd. IL ، 1962. - 468 ص.

شيخانوفيتش يو. المجموعات ، الحلقات ، المشابك. - SPb .: Kirtsideli، 2006. - 368 ص.

شنيبرمان ل. دورة الجبر ونظرية الأعداد في المسائل والتمارين: في ساعتين الجزء 2. -منج: فيش. shk. ، 1987. - 256 ص.

شنيبرمان ل. مجموعة مسائل في الجبر ونظرية الأعداد - مينسك: Design PRO، 2000. -240 p.