💻 computer science

A Survey on Complexity Measures of Pseudo-Random Sequences

تستعرض هذه الدراسة المسحية أربعة عقود من الأبحاث حول مقاييس التعقيد المختلفة لتقييم عشوائية المتتاليات شبه العشوائية، بما في ذلك التعقيدات الخطية والتربيعية والقصوى، وتستكشف علاقاتها مع مقاييس أخرى مثل مقاييس ليمبل-زيف، والتمدد، و2-آديك، والارتباط.

المؤلفون الأصليون: Chunlei Li

نُشر 2026-04-15

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Chunlei Li

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول بناء خزنة آمنة لأسرارك الأكثر قيمة. للقيء بذلك، تحتاج إلى مفتاح رئيسي يبدو عشوائياً تماماً—عشوائياً لدرجة أنه لا يمكن لأحد تخمين الرقم التالي في التسلسل. هذا هو عالم علم التشفير، و"العشوائية" في هذه المفاتيح هي كل شيء.

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

إليك تفصيل الورقة باستخدام تشبيهات بسيطة:

1. المشكلة: العشوائية المزيفة

في العالم الرقمي، الحواسيب ليست عشوائية بطبيعتها. إنها مثل روبوتات سريعة جداً ويمكن التنبؤ بها جداً. إذا أخبرت روبوتاً أن "يختار رقماً"، فسيختار دائماً نفس الرقم إذا بدأت بنفس الطريقة.

لجعلها تتصرف بشكل عشوائي، نستخدم مولدات البتات شبه العشوائية (PRBGs). فكر في هذه كـ "آلات عشوائية".

الهدف: يجب أن تنتج الآلة تدفقاً من البتات (0 و1) يبدو تماماً مثل رمي العملة المعدنية.
الخطر: إذا كانت الآلة متوقعة للغاية، يمكن للمخترق اكتشاف النمط، وتخمين البت التالي، وكسر تشفيرك.

2. الحل: قياس "التعقيد"

كيف نعرف ما إذا كان التسلسل عشوائياً حقاً أم مجرد خدعة ذكية؟ نحتاج إلى مقياس تعقيد. تستعرض الورقة أنواعاً مختلفة من المقاييس المستخدمة لاختبار هذه التسلسلات.

فكر في تسلسل الأرقام كأنه وصفة طعام.

تعقيد منخفض: الوصفة بسيطة. "أضف 1، ثم أضف 1، ثم أضف 1". (مثلاً: 1، 2، 3، 4...). يمكن لأي شخص تخمين الرقم التالي. هذا سيئ للأمان.
تعقيد عالٍ: الوصفة عبارة عن رواية من 50 صفحة بدون أي نمط. يجب عليك قراءة الرواية بأكملها لفهمها، ولا يمكنك تخمين الكلمة التالية دون معرفة الكلمات السابقة. هذا جيد للأمان.

تركز الورقة على ثلاثة أنواع رئيسية من "مقاييس التعقيد":

أ. التعقيد الخطي (الاختبار الأبسط)

تخيل أنك تحاول التنبؤ بالشخص التالي في صف من الناس.

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

ب. التعقيد التربيعي (اختبار "الأكثر تعقيداً قليلاً")

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

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

ج. التعقيد من الدرجة القصوى (الاختبار "الأقصى")

هذا هو الاختبار الأصعب. يسأل: "ما هي أصغر آلة ممكنة، من أي نوع (بغض النظر عن غرابة الرياضيات المستخدمة)، يمكنها إنتاج هذا التسلسل؟"

الاختبار: تخيل محققاً يحاول العث_ور على أقصر مجموعة من التعليمات لإعادة تمثيل مسرح الجريمة.
التحول: تشير الورقة إلى مفارقة مضحكة: يمكن أن يكون التسلسل معقداً رياضياً (صعب التوليد) ولكنه سيئ إحصائياً (ليس عشوائياً على الإطلاق).
- تشبيه: تخيل تسلسلاً هو 0، 0، 0، 0، 0، 1. إنه صعب التوليد لأن الآلة يجب أن تتذكر إخراج خمسة أصفار ثم واحد. لكنه ليس عشوائياً بوضوح لأنه مجرد أصفار!
- الدرس: التعقيد العالي لا يعني دائماً عشوائية جيدة. أنت بحاجة إلى مزيج من التعقيد العالي والسلوك الإحصائي الجيد (مثل وجود عدد متساوٍ من الـ 0 والـ 1).

3. "المقاييس الأخرى"

تذكر الورقة أيضاً طرقاً أخرى لقياس العشوائية، وتقارنها بالمقاييس الثلاثة الرئيسية:

تعقيد ليمبل-زيف (Lempel-Ziv Complexity): هذا يشبه اختبار الضغط. إذا استطعت ضغط ملف وجعله صغيراً جداً، فقد كان الملف يحتوي على الكثير من الأنماط (عشوائية منخفضة). إذا ظل الملف ضخماً بعد الضغط، فهو عشوائي جداً.
تعقيد 2-adic: هذا اختبار متخصص للآلات التي تتعامل مع "الحمل" (مثل عندما تضيف 1 إلى 9 وتحصل على 10). إنه نوع مختلف من الرياضيات ولكنه يفحص الشيء نفسه.
مقاييس الارتباط (Correlation Measures): يتحقق هذا مما إذا كان التسلسل يحتوي على أي "أصداء". إذا رأيت نمطاً يتكرر نفسه مع تأخير طفيف، فإن التسلسل ضعيف.

4. ماذا وجد المؤلف؟

يلخص تشونلي لي أن:

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

الخلاصة الكبرى

بناء مفتاح تشفير آمن يشبه بناء متاهة.

التعقيد الخيدي يتحقق مما إذا كانت المتاهة تحتوي على مسار بسيط ومستقيم.
التعقيد التربيعي/التعقيد من الدرجة القصوى يتحقق مما إذا كانت هناك حلقات مخفية أو أنفاق سرية.

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

باخت-اختصار: هذه الورقة هي خريطة لـ "مشهد العشوائية"، توضح لنا أي الأدوات نملك لقياس الأمان، وأي الأدوات أصبحت قديمة، وأين نحتاج لبناء جسور جديدة لمستقبل علم التشفير.

إليك ملخص تقني مفصل للورقة البحثية الاستقصائية "مسح لمقاييس التعقيد للتسلسلات شبه العشوائية" للباحث تشونلي لي.

1. بيان المشكلة

تتناول الورقة التحدي الجوهري المتمثل في تقييم العشوائية في التسلسلات شبه العشوائية (PRS) التي يتم إنشاؤها بواسطة مولدات البتات شبه العشوائية (PRBGs)، والتي تُعد بالغة الأهمية للتطبيقات التشفيرية (مثل مفاتيح التشفير، والـ nonces).

المشكلة الجوهرية: بينما تتطلب العشوائية المثالية عدم القدرة على التمييز عن المصدر الموحد، فإن المولدات في العالم الحقيقي تعتمد غالبًا على خوارزميات حتمية (مثل سجلات الإزاحة التغذية الراجعة - FSRs). إذا كان للتسلسل "تعقيد" منخفض، فيمكن التنبؤ به أو إعادة بنائه من ملاحظة قصيرة، مما يؤدي إلى إخفاقات أمنية.
الفجوة: على الرغم من أن التعقيد الخطي مفهوم جيد الفهم ومعياري (على سبيل المثال، في اختبارات NIST)، إلا أن مقاييس التعقيد غير الخطية الأخرى (التربيعي، والترتيب الأقصى، و2-adic، إلخ) والعلاقات المتبادلة بينها لا تزال أقل استكشافًا، لا سيالما فيما يتعلق بسلوكها الإحصائي والحدود النظرية للتسلسلات الدورية.

2. المنهجية

يستخدم المؤلف نهج مراجعة شاملة للأدبيات والتحليل النظري، مع التركيز على:

نماذج FSR: تحليل التسلسلات الناتجة عن سجلات FSR الخطية (LFSRs)، وFSR التربيعية، وFSR غير الخطية العامة.
الأدوات الجبرية والخوارزمية: استخدام أدوات مثل خوارزمية Berlekamp-Massey، والكسور المستمرة، وتحويلات فوريه المتقطعة (DFT)، وتحويل فوريه المتقطع المعمم (GDFT)، ونظرية الرسوم البيانية للكلمات المباشرة غير الحلقية (DAWG).
التحليل الإحصائي: فحص القيم المتوقعة، والتباينات، وملفات التوزيع لمقاييس التعقيد للتسلسلات العشوائية.
التحليل المقارن: وضع متباينات وعلاقات رياضية بين مقاييس التعقيد المختلفة (مثل الخطي مقابل التربيعي مقابل الترتيب الأقصى).

3. المساهمات الرئيسية والنتائج التقنية

أ. التعقيد الخطي (LC)

التعريف: طول أقصر سجل LFSR يولد التسلسل.
السلوك الإحصائي: بالنسبة للتسلسلات الثنائية العشوائية بطول $n$ ، فإن التعقيد الخطي المتوقع هو $\approx n/2$ . تراجع الورقة أعمال Rueppel وNiederreiter التي توضح أنه بالنسبة للتسلسلات العشوائية، فإن $L_n(s) = n/2 + O(\log n)$ .
التسلسلات الدورية: يتم تحديد التعقيد الخطي للتسلسلات ذات الدورية $n$ عبر مبرهنة Günther-Blahut باستخدام تحويل فوريه المتقطع المعمم (GDFT). تفصل الورقة التعقيد الخطي المتوقع للتسلسلات الدورية، مشيرة إلى أنه عمومًا يكون أعلى من $n/2$ (غالبًا ما يقترب من $n$ ) اعتمادًا على مجموعات كوزيت الدورات (cyclotomic cosets) للفترة.
التسلسلات المثالية: تناقش التسلسلات $d$ -perfect حيث يظل ملف التعقيد الخطي قريبًا من $n/2$ لجميع الإزاحات، وهي خاصية حاسمة لمفاتيح التشفير (keystreams).

ب. التعقيد التربيعي (QC)

التعريف: طول أقصر FSR ذو دالة تغذية راجعة تربيعية.
الحساب: تفصل الورقة خوارزميات (Rizomiliotis et al.) التي تحل نظامًا من المعادلات الخطية $M(n,m)F(m) = E(n,m)$ لتحديد التعقيد التربيعي. وتبرز خوارزمية تكرارية مشابهة لخوارزمية Berlekamp-Massey ولكنها تعتمد على حسابات رتبة المصفوفة (matrix rank).
السلوك الإحصائي: على عكس التعقيد الخطي، لا توجد نتائج نظرية صارمة للسلوك الإحصائي للتعقيد التربيعي. تقدم الورقة التخمين 2 (Youssef & Gong) الذي يشير إلى أن التعقيد التربيعي المتوقع للتسلسلات العشوائية هو $\approx \sqrt{2n}$ .
الآثار الأمنية: إذا كان للتسلسل تعقيد تربيعي منخفض، فيمكن تحديد دالة التغذية الراجعة بشكل فريد بعد ملاحظة $O(m^2)$ من البتات، مما يجعله غير آمن.

ج. تعقيد الترتيب الأقصى (MOC) / التعقيد غير الخطي

التعريف: طول أقصر FSR (مع أي تغذية راجعة غير خطية) يولد التسلسل.
الحساب: تراجع الورقة نهجين رئيسيين:
1. طريقة DAWG: تربط MOC بعمق الرسم البيوي للكلمات المباشرة غير الحلقي (Direct Acyclic Word Graph).
2. الطريقة الجبرية/التكرارية: تستخدم الكلمات الذاتية (eigenwords) والتحديثات التكرارية لدوال التغذية الراجعة (مشابهة لـ Berlekamp-Massey). متوسط التعقيد هو $O(n^2 \log n)$ .
السلوك الإحصائي: بالنسبة للتسلسلات العشوائية، $E[M_n(s)] \approx 2 \log_q(n)$ .
التسلسلات ذات التعقيد العالي: تصنف الورقة التسلسلات ذات التعقيد الأقصى الممكن ( $n-1$ ). ومن المثير للدهشة أن هذه التسلسلات (مثل $00\dots01$ ) تمتلك هياكل تكرارية قوية وخصائص إحصائية ضعيفة (نقص في التوازن)، مما يجعلها غير مناسبة للتشفير رغم تعقيدها العالي.
التسلسلات الدورية: توفر المبرهنة 10 شروطًا ضرورية وكافية لتسلسل دوري بطول $n$ ليكون له MOC يساوي $n-1$ ، مما يكشف عن هيكل تكراري مستمد من خوارزمية إقليدس.

د. العلاقات بين مقاييس التعقيد

تؤسس الورقة تسلسلًا هرميًا وعلاقات متبادلة:

سلسلة المتباينات: $M_n(s) \le Q_n(s) \le L_n(s) \le n$ .
التعقيد 2-adic: التعقيد MOC لتسلسل ثنائي محكوم بحد أعلى وهو تعقيده الـ 2-adic.
تعقيد Lempel-Ziv (LZ): مرتبط بـ MOC عبر "ملف القيم الذاتية" (عدد السلاسل الفرعية المتميزة).
تعقيد التوسع (Expansion Complexity): مرتبط بدرجة كثيرات الحدود التي تلغي التسلسل.
مقاييس الارتباط: يتم تقديم حدود تربط التعقيد الخطي/MOC بمقاييس الارتباط من الرتبة $k$ . الارتباط العالي يعني تعقيدًا أقل.

4. النتائج الرئيسية والمشكلات المفتوحة

تسلسلات DeBruijn: تناقش الورقة التعقيد الخطي لتسلسلات DeBruijn (المحصورة بين $2^{m-1}+m$ و $2^m-1$ ) وتقترح التخمين 3 بخصوص وجود تسلسلات ذات كثيرات حدود دنيا محددة.
التعقيد التربيعي لـ DeBruijn: تؤكد أن بالنسبة للرتبة $m \ge 3$ ، فإن $Q(s) \le 2^m - \binom{m}{2} - 1$ .
المشكلات المفتوحة المقترحة:
1. توصيف جميع التسلسلات الدورية بطول $n$ التي تمتلك أكبر تعقيد تربيعي ( $n-1$ ).
2. وضع حدود دنيا لـ $k$ -error maximum-order complexity للتسلسلات ذات الـ MOC الأقصى.

5. الأهمية

الأمن التشفيري: توضح الورقة الاستقصائية أن التعقيد العالي لا يعني تلقائيًا عشوائية جيدة. فالتسلسلات ذات الـ MOC الأقصى غالبًا ما تفشل في الاختبارات الإحصائية (التوازن، خصائص التشغيل/run properties) بسبب هيكلها التكراري. وعلى العكس من ذلك، فإن التسلسلات ذات التعقيد المنخفض يسهل كسرها.
التقييس (Standardization): تعزز الورقة أهمية التعقيد الخطي في اختبارات NIST بينما تسلط الضوء على الحاجة إلى فهم أفضل للمقاييس غير الخطية (MOC, QC) لمنع الإخفاقات التشفيرية المستقبلية.
اتجاه البحث: تحدد الورقة أنه بينما نضج التعقيد الخطي بشكل جيد، فإن التعقيد التربيعي وتعقيد الترتيب الأقصى يفتقران إلى نظريات إحصائية صارمة. وهي تدعو إلى أدوات جبرية جديدة وأطر نظرية لتحليل هذه المقاييس غير الخطية، لا سيما للتسلسلات الدورية المستخدمة في تشفيرات التدفق (stream ciphers).

باختสร، تعمل هذه الورقة كجسر حيوي بين النظرية الراسخة للتعقيد الخطي والمجال الأكثر تعقيدًا والأقل فهمًا للتحليل غير الخطي للتسلسلات، مما يوفر خارطة طريق للبحوث المستقبلية في تصميم التسلسلات التشفيرية.