قابلية الاختزال الذاتي العشوائي

الموسوعة الحرة

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

تعريف

إذا أمكن اختزال دالة f، التي تُقيّم أي حالة x، في زمن متعدد الحدود إلى تقييم f على حالة عشوائية واحدة أو أكثر yᵢ ، فإنها تُسمى دالة ذاتية الاختزال (ويُعرف هذا أيضًا بالاختزال الذاتي المنتظم غير التكيفي ). في الاختزال الذاتي العشوائي، تُحوّل أي حالة x في أسوأ الحالات ضمن نطاق f إلى مجموعة عشوائية من الحالات y₁ , ..., yᵏ . يتم ذلك بحيث يُمكن حساب f ( x ) في زمن متعدد الحدود، بمعلومية تسلسل رمي العملة الناتج عن التحويل، و x ، و f ( y₁ ), ..., f ( yᵏ ) . بالتالي، بأخذ المتوسط ​​بالنسبة للتوزيع المُستحث على yᵢ ، يكون تعقيد الحالة المتوسطة لـ f هو نفسه (ضمن عوامل متعددة الحدود ) تعقيد الحالة العشوائية الأسوأ لـ f . 

إحدى الحالات الخاصة الجديرة بالملاحظة هي عندما يتم توزيع كل عنصر عشوائي yᵢ توزيعًا منتظمًا على كامل مجموعة العناصر في مجال الدالة f التي يبلغ طولها | x |. في هذه الحالة، تكون f صعبة في المتوسط ​​كما هي في أسوأ الحالات. يتضمن هذا النهج قيدين أساسيين. أولًا ، يتم توليد y₁ ، ...، yₖ بطريقة غير تكيفية. هذا يعني أنه يتم اختيار y₂ قبل معرفة f ( y₁ ) . ثانيًا، ليس من الضروري أن تكون النقاط y₁ ، ... ، yₖ موزعة توزيعًا منتظمًا.

التطبيق في بروتوكولات التشفير

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

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

أمثلة

تُعد كل من مشكلة اللوغاريتم المنفصل، ومشكلة البقايا التربيعية ، ومشكلة عكس RSA ، ومشكلة حساب الثابت للمصفوفة، مشاكل عشوائية ذاتية الاختزال.

اللوغاريتم المتقطع

النظرية : إذا كانت لدينا مجموعة دورية G بحجم | G |، وإذا كانت خوارزمية حتمية متعددة الحدود A تحسب اللوغاريتم المنفصل لجزء 1/poly( n ) من جميع المدخلات (حيث n = log | G | هو حجم المدخلات)، فإنه توجد خوارزمية عشوائية متعددة الحدود لحساب اللوغاريتم المنفصل لجميع المدخلات.

بفرض وجود مولد g لمجموعة دورية G = { g i | 0 ≤ i < | G | }، و x ∈ G ، فإن اللوغاريتم المتقطع لـ x بالنسبة للأساس g هو العدد الصحيح k (0 ≤ k < | G |) حيث x = g k . بافتراض أن B موزعة توزيعًا منتظمًا على {0,...,| G | − 1}، فإن xg B = g k + B موزعة أيضًا توزيعًا منتظمًا على G. لذا، فإن xg B مستقل عن x ، ويمكن حساب لوغاريتمه باحتمالية 1/poly( n ) في زمن متعدد الحدود. وبالتالي، فإن log g x ≡ log g xg B - B (mod | G |)، واللوغاريتم المتقطع قابل للاختزال الذاتي.     

عنصر دائم في المصفوفة

بالنظر إلى تعريف الثابت للمصفوفة ، يتضح أن PERM ( M ) لأي مصفوفة M من الرتبة n × n هي متعددة حدود متعددة المتغيرات من الدرجة n على عناصر M. يُعد حساب الثابت للمصفوفة مهمة حسابية معقدة ، وقد ثبت أن PERM مسألة كاملة من فئة #P ( برهان ). علاوة على ذلك، فإن القدرة على حساب PERM ( M ) لمعظم المصفوفات تستلزم وجود برنامج عشوائي يحسب PERM ( M ) لجميع المصفوفات. وهذا يُثبت أن PERM مسألة عشوائية قابلة للاختزال الذاتي. تتناول المناقشة التالية الحالة التي تُسحب فيها عناصر المصفوفة من حقل منتهٍ F <sub> p </sub> لعدد أولي p ، حيث تُجرى جميع العمليات الحسابية في هذا الحقل.

لتكن X مصفوفة عشوائية من الرتبة n × n عناصرها من Fp . بما أن جميع عناصر أي مصفوفة M + kX هي دوال خطية لـ k ، فإن تركيب هذه الدوال الخطية مع متعددة الحدود متعددة المتغيرات من الدرجة n التي تحسب PERM ( M ) يُعطينا متعددة حدود أخرى من الدرجة n لـ k ، والتي سنسميها p ( k ). من الواضح أن p (0) تساوي قيمة PERM للمصفوفة M.

لنفترض أننا نعرف برنامجًا يحسب القيمة الصحيحة لـ PERM ( A ) لمعظم المصفوفات من الرتبة n× n ذات العناصر من Fp ، وتحديدًا 1 − 1/( 3n ) منها. عندئذٍ، باحتمالية تقارب الثلثين، يمكننا حساب PERM ( M + kX ) لـ k = 1, 2, ..., n + 1. بمجرد حصولنا على هذه القيم n + 1، يمكننا إيجاد معاملات p ( k ) باستخدام الاستيفاء (مع الأخذ في الاعتبار أن p ( k ) من الدرجة n ). بمجرد معرفة p ( k ) بدقة، نقوم بحساب p (0)، والتي تساوي PERM ( M ).  

إذا فعلنا ذلك، فإننا نخاطر بأن نكون مخطئين بنسبة 1/3 من الوقت، ولكن من خلال اختيار عدة قيم عشوائية X وتكرار الإجراء المذكور أعلاه عدة مرات، وتقديم الفائز بالأغلبية فقط كإجابة، يمكننا خفض معدل الخطأ إلى مستوى منخفض للغاية.

عواقب

مراجع