خطوة صغيرة، خطوة عملاقة

في نظرية الزمر ، وهي فرع من فروع الرياضيات، تُعدّ خوارزمية الخطوة الصغيرة والخطوة العملاقة خوارزميةً للالتقاء في المنتصف لحساب اللوغاريتم المنفصل أو رتبة عنصر في زمرة أبيلية منتهية ، وقد وضعها دانيال شانكس . ^{[ 1 ]} وتُعتبر مسألة اللوغاريتم المنفصل ذات أهمية جوهرية في مجال التشفير بالمفتاح العام .

تعتمد العديد من أنظمة التشفير الأكثر شيوعًا على افتراض أن حساب اللوغاريتم المتقطع صعب للغاية؛ فكلما زادت صعوبته، زادت الحماية التي يوفرها لنقل البيانات. ومن طرق زيادة صعوبة حساب اللوغاريتم المتقطع بناء نظام التشفير على مجموعة أكبر.

تعتمد الخوارزمية على المفاضلة بين المساحة والوقت . وهي عبارة عن تعديل بسيط إلى حد ما لعملية الضرب التجريبي، وهي الطريقة الساذجة لإيجاد اللوغاريتمات المنفصلة.

بالنظر إلى مجموعة حلقية${\displaystyle G}$من النظام${\displaystyle n}$مولد كهربائي${\displaystyle \alpha }$من المجموعة وعنصر المجموعة${\displaystyle \beta }$المشكلة هي إيجاد عدد صحيح${\displaystyle x}$بحيث

${\displaystyle \alpha ^{x}=\beta \,.}$

تعتمد خوارزمية الخطوة الصغيرة والخطوة العملاقة على إعادة الكتابة${\displaystyle x}$:

${\displaystyle x=im+j}$

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$

${\displaystyle 0\leq i<m}$

${\displaystyle 0\leq j<m}$

لذلك، لدينا:

${\displaystyle \alpha ^{x}=\beta \,}$

${\displaystyle \alpha ^{im+j}=\beta \,}$

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$

تقوم الخوارزمية بالحساب المسبق${\displaystyle \alpha ^{j}}$لعدة قيم من${\displaystyle j}$ثم يقوم بإصلاح${\displaystyle m}$ويحاول قيم${\displaystyle i}$في الجانب الأيمن من التطابق أعلاه، على غرار عملية الضرب التجريبي. يتم اختبار ما إذا كان التطابق محققًا لأي قيمة من${\displaystyle j}$، باستخدام القيم المحسوبة مسبقًا لـ${\displaystyle \alpha ^{j}}$.

المدخلات : مجموعة دورية G من الرتبة n ، لها مولد α وعنصر β .

الناتج : قيمة x تحقق الشرط التالي${\displaystyle \alpha ^{x}=\beta }$.

1. m ← السقف( √ n )
2. لكل j حيث 0 ≤ j < m :
   1. احسب قيمة α ^j وخزّن الزوج ( j , α ^j ) في جدول. (انظر §  في الممارسة العملية )
3. احسب α ^{− m} .
4. γ ← β . (ضع γ = β )
5. لكل i حيث 0 ≤ i < m :
   1. تحقق لمعرفة ما إذا كان γ هو المكون الثاني ( αj ⁾ لأي زوج في الجدول.
   2. إذا كان الأمر كذلك، فأرجع im + j .
   3. إذا لم يكن الأمر كذلك، γ ← γ • α ^{− m} .

أفضل طريقة لتسريع خوارزمية الخطوة الصغيرة والخطوة العملاقة هي استخدام مخطط بحث فعال في جدول. يُعد جدول التجزئة الخيار الأمثل في هذه الحالة . تتم عملية التجزئة على المكون الثاني، ولإجراء الفحص في الخطوة 1 من الحلقة الرئيسية، يتم تجزئة γ والتحقق من عنوان الذاكرة الناتج. بما أن جداول التجزئة قادرة على استرجاع وإضافة العناصر في${\displaystyle O(1)}$الوقت (الوقت الثابت)، وهذا لا يبطئ خوارزمية الخطوة الصغيرة والخطوة العملاقة بشكل عام.

التعقيد المكاني للخوارزمية هو${\displaystyle O({\sqrt {n}})}$، بينما يبلغ التعقيد الزمني للخوارزمية${\displaystyle O({\sqrt {n}})}$مدة التشغيل هذه أفضل من${\displaystyle O(n)}$زمن تشغيل عملية الحساب البدائية البسيطة.

يمكن للمتطفل استخدام خوارزمية الخطوة الصغيرة والخطوة العملاقة لاستنتاج المفتاح الخاص المُولّد في تبادل مفاتيح ديفي-هيلمان ، عندما يكون المعامل عددًا أوليًا ليس كبيرًا جدًا. أما إذا لم يكن المعامل عددًا أوليًا، فإن خوارزمية بوهليغ-هيلمان تتميز بتعقيد حسابي أقل، ويمكنها حل المشكلة نفسها. ^{[ 2 ]}

• خوارزمية الخطوة الصغيرة والخطوة العملاقة هي خوارزمية عامة. وهي تعمل مع كل مجموعة دورية منتهية.
• ليس من الضروري معرفة الترتيب الدقيق للمجموعة G مسبقًا. تظل الخوارزمية فعّالة حتى لو كان n مجرد حد أعلى لترتيب المجموعة.
• عادةً ما تُستخدم خوارزمية الخطوة الصغيرة والخطوة العملاقة للمجموعات التي رتبتها أعداد أولية. أما إذا كانت رتبة المجموعة مركبة، فإن خوارزمية بوهليغ-هيلمان تكون أكثر كفاءة.
• تتطلب الخوارزمية${\displaystyle O(m)}$الذاكرة. من الممكن استخدام ذاكرة أقل باختيار قيمة أصغر لـ m في الخطوة الأولى من الخوارزمية. يؤدي ذلك إلى زيادة وقت التشغيل، والذي يصبح بالتالي${\displaystyle O(n/m)}$. بدلاً من ذلك، يمكن للمرء استخدام خوارزمية رو لبولارد للوغاريتمات ، والتي لها نفس وقت التشغيل تقريبًا مثل خوارزمية الخطوة الصغيرة والخطوة العملاقة، ولكنها تتطلب ذاكرة صغيرة فقط.
• بينما يُنسب الفضل في هذه الخوارزمية إلى دانيال شانكس، الذي نشر الورقة البحثية لعام 1971 التي ظهرت فيها لأول مرة، فإن ورقة بحثية أخرى نُشرت عام 1994 من قبل نيتشاييف ^{[ 3 ]} تنص على أنها كانت معروفة لجيلفوند في عام 1962.
• توجد نسخ محسّنة من الخوارزمية الأصلية، مثل استخدام جداول البحث المقتطعة الخالية من التصادم ^{[ 4 ]} أو خرائط النفي والانعكاس المعياري المتزامن لمونتغمري. ^{[ 5 ]}

• H. Cohen ، دورة في نظرية الأعداد الجبرية الحاسوبية، سبرينغر، 1996.
• د. شانكس ، عدد الفئات، نظرية التحليل إلى عوامل والأجناس. في وقائع ندوة الرياضيات البحتة 20، الصفحات 415-440. الجمعية الأمريكية للرياضيات، بروفيدنس، رود آيلاند، 1971.
• أ. شتاين وإ. تيسكي، طرق الخطوة الصغيرة والخطوة العملاقة المُحسَّنة، مجلة جمعية رامانوجان الرياضية 20 (2005)، العدد 1، 1-32.
• AV Sutherland ، حسابات الترتيب في المجموعات العامة ، أطروحة دكتوراه، معهد ماساتشوستس للتكنولوجيا، 2007.
• دي سي تير، تعديل لخوارزمية شانكس ذات الخطوة الصغيرة والخطوة العملاقة، رياضيات الحوسبة 69 (2000)، 767-773. doi : 10.1090/S0025-5718-99-01141-2

• خطوة صغيرة - خطوة عملاقة - مثال على كود مصدر C