خوارزمية تحليل المجموعات الجبرية

غالباً ما يكون من الممكن ضرب عنصر من عناصر المجموعة بعدة أعداد صحيحة صغيرة بسرعة أكبر من ضربها في حاصل ضربها، وذلك عادةً باستخدام طرق تعتمد على الفروق: حيث يتم حساب الفروق بين الأعداد الأولية المتتالية ثم جمعها تباعاً.${\displaystyle d_{i}r}$هذا يعني أن إجراءً من خطوتين يصبح منطقيًا، حيث يتم أولًا حساب Ax بضرب x في جميع الأعداد الأولية التي تقل عن حد B1 _، ثم يتم فحص p Ax لجميع الأعداد الأولية بين B1 _وحد أكبر B2 _. وهذا من شأنه أن يخفف شرط السلاسة لرتبة المجموعة من كونها B1 _- powersmooth إلى كونها حاصل ضرب عدد أولي بين B1 _و B2 _في عدد B1 _- powersmooth.

تُعدّ طريقة الفرق هي الطريقة الأساسية "للمرحلة الثانية". وتوجد تعديلات عليها مثل طريقة مونتغمري لتزاوج الأعداد الأولية (1978) وامتداد برنت-سوياما. ^{[ 2 ]}

تستخدم طريقة "المرحلة الثانية" الأكثر كفاءة ضرب كثيرات الحدود المُنفذة عبر تحويل فورييه السريع . وقد تم عرض هذه الطريقة لأول مرة لخوارزمية لينسترا ECM بواسطة مونتغمري في عام 1992، ^{[ 3 ]} ولكن تم تكييفها منذ ذلك الحين لـ p -1 و p +1. ^{[ 2 ]}

إذا كانت المجموعة الجبرية هي المجموعة الضربية modulo N ، يتم التعرف على الهويات أحادية الجانب عن طريق حساب القواسم المشتركة الكبرى مع N ، والنتيجة هي طريقة p − 1   .

إذا كانت المجموعة الجبرية هي المجموعة الضربية لامتداد تربيعي لـ N ، فإن النتيجة هي طريقة p  +  1 ؛ يتضمن الحساب أزواجًا من الأعداد بتردد N. لا يمكن تحديد ما إذا كان${\displaystyle \mathbb {Z} /N\mathbb {Z} [{\sqrt {t}}]}$هي في الواقع امتداد تربيعي لـ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$دون معرفة تحليل العدد N إلى عوامله . يتطلب هذا معرفة ما إذا كان t باقيًا تربيعيًا بتردد N ، ولا توجد طرق معروفة للقيام بذلك دون معرفة التحليل. مع ذلك، إذا لم يكن لـ N عدد كبير جدًا من العوامل، وفي هذه الحالة يجب استخدام طريقة أخرى أولًا، فإن اختيار t عشوائيًا (أو بالأحرى اختيار A بحيث يكون t = A² ^- 4) سيؤدي بالصدفة إلى الحصول على باقي تربيعي غير بتردد N بسرعة. إذا كان t باقيًا تربيعيًا، فإن طريقة p+1 تتحول إلى شكل أبطأ من طريقة p - 1.    

إذا كانت المجموعة الجبرية منحنى إهليلجيًا ، فيمكن التعرف على المتطابقات أحادية الجانب من خلال فشل عملية الانعكاس في إجراء جمع نقاط المنحنى الإهليلجي، والنتيجة هي طريقة المنحنى الإهليلجي ؛ تنص نظرية هاس على أن عدد النقاط على منحنى إهليلجي modulo p يكون دائمًا ضمن${\displaystyle 2{\sqrt {p}}}$من ص .

تستخدم حزمة GMP-ECM جميع المجموعات الجبرية الثلاث المذكورة أعلاه، ^{[ 4 ]} والتي تتضمن تطبيقات فعالة للإجراء المكون من مرحلتين، وتطبيقًا لخوارزمية PRAC للأس الجماعي والتي تعتبر أكثر كفاءة من نهج الأس الثنائي القياسي .

يُقترح أحيانًا استخدام مجموعات جبرية أخرى - امتدادات من رتبة أعلى للمجموعة N أو مجموعات تُقابل منحنيات جبرية من جنس أعلى - لكنها غير عملية في أغلب الأحيان. على سبيل المثال، يمكن استخدام مُتَنَوِّع جاكوبي لمنحنى زائد إهليلجي ، والذي يتمتع بقانون مجموعة فعال. تنتهي هذه الطرق بقيود على سلاسة الأعداد من رتبة p ^d لبعض d  >  1، وهي أقل احتمالًا بكثير لأن تكون سلسة من الأعداد من رتبة p .

يستخدم المرحلة الأولى الساذجة${\displaystyle O(B_{1}\log(B_{1})M(\log(N)))}$عمليات البت، بينما تأخذ المرحلة الأولى التي تعتمد على القوى الأولية فقط${\displaystyle O(B_{1}M(\log(N)))}$، حيث N هو العدد المراد تحليله إلى عوامله الأولية و${\displaystyle M(x)}$يشير إلى تكلفة ضرب عددين صحيحين مكونين من x بت (عمليًا)${\displaystyle M(\log(N))=O(N\log(N)\log \log(N))}$(باستخدام طرق تعتمد على تحويل فورييه السريع). ^{[ 1 ]}

تستخدم المرحلة الثانية القياسية (القائمة على الفرق)${\displaystyle O((B_{2}-B_{1})M(\log(N)))}$عمليات البت. ^{[ 1 ]} تستخدم المرحلة الثانية القائمة على كثيرات الحدود${\displaystyle O({\sqrt {B_{2}-B_{1}}}\log(B_{2}-B_{1})M(\log(N)))}$عمليات البت (الـ${\displaystyle B_{1}}$يمكن تجاهل المصطلح بافتراض${\displaystyle B_{2}>>B_{1}}$(وهو ما يحدث غالبًا). يؤدي تغيير حجم الالتفاف إلى مفاضلة بين الذاكرة والمساحة: فمقابل كل مضاعفة لاستخدام الذاكرة، يتضاعف مقدار التقدم في${\displaystyle B_{2}}$يمكن إجراؤها بنفس القدر من الحساب. ^{[ 2 ]}

انظر إلى Kruppa (2010) القسمين 5.3 و 5.4. ^{[ 5 ]}