خوارزمية الكنغر لبولارد

في نظرية الأعداد الحاسوبية والجبر الحاسوبي ، تُعد خوارزمية الكنغر لبولارد (وتُعرف أيضًا بخوارزمية لامدا لبولارد ، انظر قسم التسمية أدناه) خوارزمية لحل مسألة اللوغاريتم المتقطع . وقد طُرحت هذه الخوارزمية عام ١٩٧٨ من قِبل عالم نظرية الأعداد جون إم. بولارد ، في نفس الورقة البحثية التي نشر فيها خوارزمية رو لبولارد الأكثر شهرة لحل المسألة نفسها. ^{[ ١ ] [ ٢ ]} وعلى الرغم من أن بولارد وصف تطبيق خوارزميته على مسألة اللوغاريتم المتقطع في المجموعة الضربية للوحدات بتردد عدد أولي p ، إلا أنها في الواقع خوارزمية عامة للوغاريتم المتقطع، إذ تعمل في أي مجموعة دورية منتهية .

يفترض${\displaystyle G}$هي مجموعة دورية منتهية من الرتبة${\displaystyle n}$والذي يتم إنشاؤه بواسطة العنصر${\displaystyle \alpha }$ونسعى لإيجاد اللوغاريتم المنفصل${\displaystyle x}$من العنصر${\displaystyle \beta }$إلى القاعدة${\displaystyle \alpha }$بمعنى آخر، يسعى المرء${\displaystyle x\in Z_{n}}$بحيث${\displaystyle \alpha ^{x}=\beta }$تتيح خوارزمية لامدا البحث عن${\displaystyle x}$في فترة زمنية معينة${\displaystyle [a,\ldots ,b]\subset Z_{n}}$يمكن البحث في النطاق الكامل للوغاريتمات الممكنة عن طريق ضبط${\displaystyle a=0}$و${\displaystyle b=n-1}$.

1. اختر مجموعة${\displaystyle S}$من الأعداد الصحيحة الموجبة ذات متوسط ​​تقريبي${\displaystyle {\sqrt {ba}}}$وتعريف خريطة شبه عشوائية${\displaystyle f:G\rightarrow S}$.

2. اختر عددًا صحيحًا${\displaystyle N}$واحسب سلسلة من عناصر المجموعة${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$وفق:

• ${\displaystyle x_{0}=\alpha ^{b}\,}$
• ${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ لـ }}i=0,1,\ldots ,N-1}$

3. احسب

${\displaystyle d=\sum _{i=0}^{N-1}f(x_{i}).}$

لاحظ ما يلي:

${\displaystyle x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.}$

4. ابدأ بحساب سلسلة ثانية من عناصر المجموعة${\displaystyle \{y_{0},y_{1},\ldots \}}$وفق:

• ${\displaystyle y_{0}=\beta \,}$
• ${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ لـ }}i=0,1,\ldots ,N-1}$

وتسلسل مطابق من الأعداد الصحيحة${\displaystyle \{d_{0},d_{1},\ldots \}}$وفق:

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$.

لاحظ ما يلي:

${\displaystyle y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}i=0,1,\ldots ,N-1}$

5. توقف عن حساب حدود${\displaystyle \{y_{i}\}}$و${\displaystyle \{d_{i}\}}$عند استيفاء أي من الشرطين التاليين:

أ)${\displaystyle y_{j}=x_{N}}$بالنسبة للبعض${\displaystyle j}$إذا كانت المتتاليات${\displaystyle \{x_{i}\}}$و${\displaystyle \{y_{j}\}}$إذا "تصادمت" بهذه الطريقة، فسنحصل على:

${\displaystyle x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}}$

وهكذا نكون قد انتهينا.

ب)${\displaystyle d_{i}>b-a+d}$إذا حدث هذا، فهذا يعني أن الخوارزمية قد فشلت في العثور على${\displaystyle x}$ويمكن إجراء محاولات لاحقة عن طريق تغيير اختيار${\displaystyle S}$و/أو${\displaystyle f}$.

يُحدد بولارد التعقيد الزمني للخوارزمية على النحو التالي:${\displaystyle O({\sqrt {ba}})}$، باستخدام حجة احتمالية تستند إلى افتراض أن${\displaystyle f}$يتصرف بشكل شبه عشوائي. منذ${\displaystyle a,b}$يمكن تمثيلها باستخدام${\displaystyle O(\log b)}$هذا الأمر يتضاعف بشكل كبير مع حجم المشكلة (على الرغم من أنه لا يزال تحسنًا كبيرًا مقارنة بخوارزمية القوة الغاشمة البسيطة التي تستغرق وقتًا).${\displaystyle O(b-a)}$). للحصول على مثال لخوارزمية لوغاريتمية منفصلة ذات وقت شبه أسي ، انظر خوارزمية حساب المؤشر .

تُعرف هذه الخوارزمية باسمين.

الأولى هي "خوارزمية بولارد للكنغر". يشير هذا الاسم إلى تشبيه استُخدم في الورقة البحثية التي عرضت الخوارزمية، حيث شُرحت الخوارزمية باستخدام كنغر أليف لاصطياد كنغر بري . وقد أوضح بولارد ^{[ 3 ]} أن هذا التشبيه استُلهم من مقال "رائع" نُشر في العدد نفسه من مجلة ساينتفك أمريكان، والذي تناول نظام التشفير بالمفتاح العام RSA . وصف المقال ^{[ 4 ]} تجربةً حُددت فيها "التكلفة الطاقية لحركة الكنغر، مقاسةً باستهلاك الأكسجين عند سرعات مختلفة، وذلك بوضع الكنغر على جهاز المشي ".

أما الثانية فهي "خوارزمية لامدا لبولارد". ومثل اسم خوارزمية أخرى من خوارزميات اللوغاريتم المنفصل لبولارد، وهي خوارزمية رو لبولارد ، يشير هذا الاسم إلى التشابه بين تمثيل الخوارزمية والحرف اليوناني لامدا (${\displaystyle \lambda }$). يتوافق الخط الأقصر لحرف لامدا مع التسلسل${\displaystyle \{x_{i}\}}$لأنها تبدأ من الموضع b إلى يمين x. وبناءً على ذلك، فإن الخط الأطول يتوافق مع التسلسل${\displaystyle \{y_{i}\}}$، والتي "تصطدم" بالتسلسل الأول (تمامًا مثل تقاطع ضربات لامدا) ثم تتبعه لاحقًا.

وقد أعرب بولارد عن تفضيله لاسم "خوارزمية الكنغر"، ^{[ 5 ]} لأن هذا يتجنب الخلط مع بعض الإصدارات المتوازية من خوارزمية رو الخاصة به، والتي أطلق عليها أيضًا اسم "خوارزميات لامدا".

• خدعة دينكين بالورق
• عدد كروسكال ^{[ 6 ]}
• طاولة قوس قزح

• مونتينيغرو، رافي [في ويكي بيانات] ؛ تيتالي، براساد ف. (2010-11-07) [2009-05-31]. كم من الوقت يستغرق اصطياد كنغر بري؟ (ملف PDF) . وقائع الندوة السنوية الحادية والأربعين لجمعية ACM حول نظرية الحوسبة (STOC 2009). الصفحات 553-560 . arXiv : 0812.0789 . doi : 10.1145/1536414.1536490 . S2CID 12797847. مؤرشف (ملف PDF) من الأصل في 2023-08-20 . تم الاسترجاع في 2023-08-20 .