كيفية حساب مصفوفة المفتاح معكوس في خوارزمية التشفير التل؟

Question

أنا أجد صعوبة في فهم الطريقة التي يتم بها حساب عكس المصفوفة في خوارزمية التشفير التل. أحصل على فكرة كل ذلك القيام به في حسابي Modulo، لكن أشياء بطريقة أو بأخرى لا تضيف. أود حقا أن أقدر تفسير بسيط!

النظر في المصفوفة مفتاح التشفير التل التالي:

 5 8 
17 3

يرجى استخدام المصفوفة أعلاه للتوضيح.

Answer 1

يجب عليك دراسة نظرية الخطية النظرية و ال خوارزمية GCD ممتدة, ، الذي ينتمي إلى نظرية الأعداد, ، من أجل فهم الرياضيات وراء حساب modulo.

عكس Matrix K على سبيل المثال هو (1 / det (k)) * undoint (k)، حيث det (k) <> 0.

أفترض أنك لا تفهم كيفية حساب 1 / اعتماد (ك) في حساب Modulo وهنا هو المكان الذي تعود فيه الانتخابات الخطية ومجتمع المعلومات العالمي.

K لديه Det (k) = -121. دعنا نقول أن modulo م هو 26. نريد عاشر* (- 121) = 1 (وزارة الدفاع 26).
a = b (mod m) يعني أن ab = n * m

يمكننا بسهولة العثور على ذلك ل X = 3. والتنافؤ أعلاه صحيح لأن 26 تقسيم (3 * (- 121) -1) بالضبط. بالطبع، الطريقة الصحيحة هي استخدام GCD في الاتجاه المعاكس لحساب X، لكن ليس لدي وقت لشرح كيف تفعل ذلك. تحقق من خوارزمية GCD :)

الآن، Inv (k) = 3 * ([3 -8]، [-17 5]) (وزارة الدفاع 26) = ([9 -24]، [-51 15]) (وزارة الدفاع 26) = ([9 2], [1 15]).

تحديث: الدفع أساسيات نظرية الأرقام الحسابية لمعرفة كيفية حساب interses المعياري مع خوارزمية الإقليدية الممتدة. لاحظ أن -121 mod 26 = 9, ، وذلك ل gcd(9, 26) = 1 نحن نحصل (-1, 3).

Answer 2

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

فقط ابحث عن "Gauss Jordan Matrix Inverse" - ولكن لتلخيص، يمكنك ببساطة مجاورة نسخة من مصفوفة الهوية إلى يمين المصفوفة المراد تقليمها، ثم استخدم عمليات الصف لتقليل مصفوفةك المراد حلها حتى تتمثل به هوية مصفوفة. في هذه المرحلة، أصبحت مصفوفة الهوية المجاورة عكس المصفوفة الأصلية. هاهو!