دالة وحيدة الاتجاه
على سبيل التعريف، في علم التعمية الحديثة، الدالة وحيدة الاتجاه هي دالة رياضية من السهل حساب قيمتها لأي مدخل في وقت متعدد الحدود (Polynomial Time)، لكن من الصعب جدًا (عمليًا) معرفة المدخل إذا عُرف الناتج فقط. يعتمد الأمان في كثير من خوارزميات التعمية على وجود مثل هذه الدوال. وجود هذه المسائل وحيدة الاتجاه يرتبط بمسألة شهيرة في علم الحاسوب، وهي: هل جميع المسائل التي يمكن التحقق من حلها بسرعة يمكن كذلك حلها بسرعة؟ إذا كانت الإجابة نعم (أي إذا كان NP = P)، فلن توجد دوال وحيدة الاتجاه. أما إذا ثبت وجود دالة وحيدة الاتجاه، فهذا يعني بالضرورة أن NP لا تساوي P. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
التعريف
ومن ناحية أخرى، أي أنه، لكل خوارزمية عشوائية ، ولكل عدد صحيح موجب ولكل كبير بما فيه الكفاية حيث ،
وفي هذا الصدد، ليس من الكافي أن تكون الدالة "فاقدة للمعلومات" (أي ليست واحد لواحد) حتى تُعتبر دالة وحيدة الاتجاه. مثلًا، الدالة التي تعطي سلسلة من الأصفار بطول لأي مُدخل بطول ليست دالة وحيدة الاتجاه، لأن من السهل إيجاد مُدخل يعيد نفس المخرج. بشكل أدق: لمثل هذه الدالة التي تخرج فقط سلسلة من الأصفار، يمكن لخوارزمية أن تعيد أي سلسلة بطول عند إدخال ، وسوف تجد بالفعل سابقة صحيحة لهذا الناتج، حتى وإن لم يكن هو نفسه المدخل الأصلي الذي أنتج سلسلة الأصفار.
من جهة ثانية، الدالة تُسمى دالة وحيدة الاتجاه إذا كان من الممكن حساب بواسطة خوارزمية زمنها كثير الحدود، ولكن أي خوارزمية عشوائية بزمن كثير الحدود تحاول حساب شبه معكوس لـ تحقق نجاحًا باحتمال ضئيل. (الرمز هنا يعني أي عدد من التكرارات، انظر نجمة كلين).
في هذا الإطار، لاحظ أن التعريف يشترط أن تكون الدالة "صعبة العكس" في متوسط الحالات وليس في أسوأ الحالات، وهذا يختلف عن أغلب نظرية التعقيد (مثل صعوبة NP) حيث يقصد بالصعوبة في أسوأ الحالات. لهذا السبب، حتى لو كانت بعض المرشحات للدوال وحيدة الاتجاه معروفة بأنها NP كاملة، فهذا لا يعني بالضرورة أنها بالفعل دوال وحيدة الاتجاه، إذ يعتمد ذلك فقط على غياب خوارزميات معروفة لحل المسألة.
كذلك، حيث أن الاحتمال يؤخذ على اختيار من التوزيع المنتظم على وعلى عشوائية .
مقدمة
علاوةً على ذلك، كريبتومانيا (Cryptomania): توجد دوال وحيدة الاتجاه وأنظمة تشفير بمفتاح عام، مما يتيح الاتصال الآمن.
وفي هذا السياق، بيسيلاند (Pessiland): توجد مسائل NP الكاملة الصعبة حتى في الحالة المتوسطة، لكن لا وجود لدوال وحيدة الاتجاه.
وفي هذا الصدد، تشير أغلب الأدلة النظرية الحالية إلى أن العالم الخامس (Cryptomania) هو الأقرب للواقع، إلا أن إثبات وجود الدوال وحيدة الاتجاه أو عدمه ما يزال من أعقد مسائل علم الحاسوب، ولا توجد أدلة قاطعة ترجح أيًا من هذه العوالم بشكل نهائي.
وفي هذا الصدد، عالم الحدس (Heuristica): مسائل NP الكاملة صعبة فقط في أسوأ الحالات، بينما يسهل حل أغلب الحالات العملية.
علاوةً على ذلك، الدوال وحيدة الاتجاه هي دوال رياضية تُعتبر من اللبنات الأساسية في علم التعمية الحديثة، إذ تعتمد عليها الكثير من خوارزميات التشفير لضمان الأمان في بيئات مثل الإنترنت، حيث يصعب تحقيق الحماية المطلقة. يشير الباحث راسل إمباغلياتسو في ورقة بحثية نُشرت عام 1995 إلى خمسة "عوالم" نظرية تصف مستقبل الدوال وحيدة الاتجاه ومسائل التعقيد الحسابي، وهي:
من جهة ثانية، عالم الخوارزميات (Algorithmica): حيث NP = P، وتصبح جميع المسائل التي يمكن التحقق منها قابلة للحل بسهولة.
وفي هذا الصدد، مينيكربت (Minicrypt): توجد دوال وحيدة الاتجاه، لكن أنظمة التشفير بالمفتاح العام غير ممكنة.
الضرب والتفكيك
من جهة ثانية، الدالة f تحصل على عددين أوليين p,q بالعد الثنائي والمُخرج حاصل الضرب أي: بينما يمكن ان نحسب هذه الدالة بوقت في حين أن n هو طول المُدخلات، الدالة العكسية والتي هي ايجاد عوامل عدد N هي مسألة لم تُحل بعد حيث أن أفضل الخوارزميات لحلها عدد الخطوات فيها: , وهو شبه حدودي متعلق ب-
دالة رابين
في هذا الإطار، دالة رابين ببساطة هي دالة التربيع النمطية، أي كالتالي: حيث أنَّ وكلا من p و- q عددين اوليين. يمكن البرهنة بأن ايجاد الجذر التربيعي النمطي مكافئ لتفكيك العدد N الذي كما اسلفنا مسألة تفكيك الاعداد هي مسألة صعبة.
دوال مرشحة لتكون وحيدة الاتجاه
علاوةً على ذلك، فيما يلي قائمة بدوال لا يُعرف اهي وحيدة الاتجاه، وبشكل عام فانه قد حصلت بحوث كثيرة ولا يوجد تقدم نحو حل لاي منها:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟