تحليل منحنى لينسترا الإهليلجي

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

من الناحية العملية، يُعتبر ECM خوارزمية تحليل عوامل ذات غرض خاص، حيث إنها الأنسب لإيجاد العوامل الصغيرة. حاليًالا تزال هذه الخوارزمية الأفضل للقواسم التي لا تتجاوز 50 إلى 60 رقمًا ، إذ يهيمن حجم أصغر عامل p على وقت تشغيلها أكثر من حجم العدد n المراد تحليله. غالبًا ما تُستخدم خوارزمية ECM لإزالة العوامل الصغيرة من عدد صحيح كبير جدًا ذي عوامل متعددة؛ فإذا كان العدد المتبقي لا يزال عددًا مركبًا، فإنه يحتوي فقط على عوامل كبيرة ويُحلل باستخدام تقنيات عامة. أكبر عامل تم اكتشافه باستخدام خوارزمية ECM حتى الآن يتكون من 83 رقمًا عشريًا، وقد اكتشفه ر. بروبر في 7 سبتمبر 2013. ^{[ 1 ]} زيادة عدد المنحنيات المختبرة تُحسّن فرص إيجاد عامل، لكنها لا تتناسب خطيًا مع زيادة عدد الأرقام.

إذا كان p و q قاسمين أوليين للعدد n ، فإن ^{المعادلة} y² = x³ + ^ax    + b (mod n ) تستلزم نفس المعادلة بتردد p و بتردد q . هاتان المنحنيتان الإهليلجيتان الأصغر حجمًا مع      ${\displaystyle \boxplus }$تُعدّ مجموعات الجمع الآن مجموعات حقيقية . إذا احتوت هذه المجموعات على _Np و Nq عنصرًا على التوالي، فإنه لأي نقطة P على المنحنى الأصلي، وبحسب نظرية لاغرانج ، يكون k > 0 هو أصغر _عدد صحيح موجب بحيث  ${\displaystyle kP=\infty }$على المنحنى modulo p يعني أن k يقسم N _p ؛ علاوة على ذلك،${\displaystyle N_{p}P=\infty }$ينطبق البيان المماثل على المنحنى بتردد q . عند اختيار المنحنى الإهليلجي عشوائيًا، فإن Np و Nq عددان عشوائيان قريبان من p + 1 و q + 1 على التوالي (انظر أدناه). لذا _، من غير المرجح أن تكون معظم العوامل الأولية لـ _Np و Nq _{متطابقة} ، ومن المرجح جدًا أنه أثناء حساب eP ، سنصادف kP يكون ∞ بتردد p ولكنه ليس بتردد q _، أو العكس. في هذه الحالة، لا يوجد kP على المنحنى الأصلي، وفي الحسابات وجدنا v بحيث يكون القاسم المشترك الأكبر لـ v و p إما p أو q ، ولكن ليس كليهما . أي أن القاسم المشترك الأكبر لـ v و n يعطي عاملًا غير تافه هو n .             

تُعدّ خوارزمية ECM في جوهرها تحسينًا لخوارزمية p − 1 القديمة   . تجد خوارزمية p − 1   العوامل الأولية p بحيث يكون p − 1   سلسًا من الدرجة b لقيم b الصغيرة . لأي عدد e ، وهو مضاعف لـ p − 1،   وأي عدد a أولي نسبيًا مع p ، وبحسب نظرية فيرما الصغرى ، لدينا a ^e ≡ 1 ( mod p )   . عندئذٍ، من المرجح أن ينتج عن gcd ( a ^e − 1, n )    عاملًا من n . مع ذلك، تفشل الخوارزمية عندما يكون لـ p  −  1 عوامل أولية كبيرة، كما هو الحال بالنسبة للأعداد التي تحتوي على أعداد أولية قوية ، على سبيل المثال.

يتغلب ECM على هذه العقبة من خلال النظر في مجموعة منحنى إهليلجي عشوائي على الحقل المنتهي Z _p ، بدلاً من النظر في المجموعة الضربية لـ Z _p التي لها دائمًا رتبة p − 1.   

يتغير ترتيب زمرة منحنى إهليلجي على Z _p (بشكل عشوائي تقريبًا) بين p  +  1 − 2 √ p   و p  +  1  +  2 √ p وفقًا لنظرية هاس ، ومن المرجح أن يكون أملسًا لبعض المنحنيات الإهليلجية. على الرغم من عدم وجود دليل قاطع على إمكانية إيجاد ترتيب زمرة أملس في فترة هاس، إلا أنه باستخدام الطرق الاحتمالية الاستدلالية ، ونظرية كانفيلد-إردوش-بوميرانس مع اختيارات مُحسَّنة للمعاملات، ورمز L ، يُمكننا توقع تجربة L [ √2 / 2 , √2 ] من المنحنيات قبل الحصول على ترتيب زمرة أملس. هذا التقدير الاستدلالي موثوق للغاية عمليًا.

المثال التالي مأخوذ من كتاب Trappe & Washington (2006) ، مع إضافة بعض التفاصيل.

نريد أن نأخذ في الاعتبار${\displaystyle n=455839}$لنختر المنحنى الإهليلجي${\displaystyle y^{2}=x^{3}+5x-5}$، مع النقطة${\displaystyle P=(1,1)}$لنبدأ، ولنحاول حساب النقطة${\displaystyle (10!)P}$.

ميل الخط المماس عند نقطة ما${\displaystyle A=(x,y)}$على المنحنى${\displaystyle \lambda ={\frac {3x^{2}+5}{2y}}\ (\mathrm {mod} \ n)}$. استخدام${\displaystyle \lambda }$يمكننا حساب النقطة${\displaystyle 2A}$إذا كانت قيمة${\displaystyle \lambda }$غير موجود، نتيجة لـ${\displaystyle y}$إذا لم يكن له معكوس معياري ،${\displaystyle \gcd(n,y)}$وهو عامل غير تافه في${\displaystyle n}$.

أولاً، نقوم بالحساب${\displaystyle 2!P}$باستخدام مضاعفة النقاط ، لدينا${\displaystyle \lambda (P)=\lambda (1,1)=4}$إذن، إحداثيات النقطة${\displaystyle 2P=(x',y')}$نكون

${\displaystyle x'=4^{2}-2(1)=14}$

${\displaystyle y'=4(1-14)-1=-53}$

التنازل عن النقطة${\displaystyle 2P=(14,-53)}$.

بعد ذلك، نقوم بالحساب${\displaystyle 3!P}$لدينا${\displaystyle \lambda (2P)=\lambda (14,-53)=-593/106\ (\mathrm {mod} \ n)}$. منذ${\displaystyle \gcd(106,455839)=1}$يوجد معكوس معياري للعدد 106. باستخدام خوارزمية إقليدس الموسعة ، يمكننا الحصول على ذلك.${\displaystyle \lambda =-593/106=322522\ (\mathrm {mod} \ 455839)}$.

وبناءً على ذلك، يمكننا حساب إحداثيات${\displaystyle 2(2P)}$تمامًا كما فعلنا أعلاه. إحداثيات النقطة${\displaystyle 4P=(x',y')}$نكون

${\displaystyle x'=322522^{2}-2(14)=259851{\pmod {455839}}}$

${\displaystyle y'=322522(14-259851)-(-53)=116255{\pmod {455839}}}$

وهذا ينتج عنه${\displaystyle 4P=(259851,116255)}$.

بعد ذلك، يمكننا الحساب${\displaystyle 3(2P)=4P+2P}$باستخدام جمع النقاط . الخط الواصل${\displaystyle 4P}$و${\displaystyle 2P}$له ميل${\displaystyle \lambda =116308/259837=206097\ (\mathrm {mod} \ n)}$إذن، إحداثيات${\displaystyle 6P=(x',y')}$نكون

${\displaystyle x'=206097^{2}-14-259851=179685{\pmod {455839}}}$

${\displaystyle y'=206097(14-179685)-(-53)=427131{\pmod {455839}}}$

التنازل عن النقطة${\displaystyle 6P=(179685,427131)}$

يمكننا بالمثل حساب النقاط${\displaystyle 4!P}$،${\displaystyle 5!P}$وهكذا دواليك، ولكن الحوسبة${\displaystyle 8!P}$يتطلب ذلك عكس 599 (mod 455839) ، وهو أمر غير ممكن لأن${\displaystyle \gcd(599,455839)=599\neq 1}$وبالتالي فإن 599 هو قاسم للعدد 455839. بعد عملية قسمة سريعة، نحصل على 455839 = 599 × 761 .

يكمن سبب نجاح هذه الطريقة في أن المنحنى (mod 599) يحتوي على 640 = ^27.5 نقطة ، بينما يحتوي (mod 761) على 777 = 3.7.37 نقطة. علاوة على ذلك، فإن 640 و777 هما أصغر عددين صحيحين موجبين k بحيث يكون kP = ∞ على المنحنى (mod 599) و (mod 761) على التوالي. وبما أن 8! مضاعف للعدد 640 ولكنه ليس مضاعفًا للعدد 777، فإن 8! P = ∞ على المنحنى (mod 599)، ولكن ليس على المنحنى (mod 761)، وبالتالي فشلت عملية الجمع المتكرر هنا، مما أدى إلى التحليل إلى عوامل.

قبل النظر في المستوى الإسقاطي فوق${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim ,}$لنفترض أولاً فضاءً إسقاطياً "عادياً" فوق${\displaystyle \mathbb {R} }$بدلاً من النقاط، تُدرس الخطوط المارة بنقطة الأصل. ويمكن تمثيل الخط بنقطة غير صفرية.${\displaystyle (x,y,z)}$، في ظل علاقة تكافؤ ~ معطاة بواسطة:${\displaystyle (x,y,z)\sim (x',y',z')}$⇔ يوجد عدد صحيح c ≠ 0 بحيث يكون x' = c x و y' = c y و z' = c z . وبموجب علاقة التكافؤ هذه، يُطلق على الفضاء اسم المستوى الإسقاطي.${\displaystyle \mathbb {P} ^{2}}$النقاط، المشار إليها بـ${\displaystyle (x:y:z)}$، تُقابل خطوطًا في فضاء ثلاثي الأبعاد تمر عبر نقطة الأصل. لاحظ أن النقطة${\displaystyle (0:0:0)}$لا يوجد في هذا الفضاء لأنه لرسم خط في أي اتجاه ممكن يتطلب على الأقل واحداً من x' أو y' أو z' ≠ 0. لاحظ الآن أن جميع الخطوط تقريبًا تمر عبر أي مستوى مرجعي معين - مثل المستوى ( X , Y , 1)، بينما تحدد الخطوط الموازية تمامًا لهذا المستوى، والتي لها إحداثيات ( X, Y , 0)، اتجاهات بشكل فريد، كـ "نقاط في اللانهاية" تُستخدم في المستوى الأفيني ( X, Y ) الذي يقع فوقه.

الإحداثيات ${\displaystyle (x:y:z)}$يتوافق مع ${\displaystyle (x/z:y/z)}$في الفضاء الأفيني. ^{[ 2 ]}

في الخوارزمية، يتم فقط تحديد بنية المجموعة لمنحنى إهليلجي فوق الحقل${\displaystyle \mathbb {R} }$يتم استخدامه. بما أننا لسنا بحاجة بالضرورة إلى الحقل${\displaystyle \mathbb {R} }$كما يوفر الحقل المنتهي بنية زمرة على منحنى إهليلجي. ومع ذلك، عند النظر إلى المنحنى نفسه والعملية عليه${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$لا يُنتج العدد n غير الأولي زمرة. وتستفيد طريقة المنحنى الإهليلجي من حالات فشل قانون الجمع.

نعرض الآن الخوارزمية في الإحداثيات الإسقاطية. ويُعطى العنصر المحايد حينها بالنقطة عند اللانهاية.${\displaystyle (0:1:0)}$. ليكن n عددًا صحيحًا (موجبًا) يتم تحليله إلى عوامله الأولية، ولنعتبر المنحنى الإهليلجي (مجموعة من النقاط ذات بنية معينة عليه).${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )=\{(x:y:z)\in \mathbb {P} ^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz^{3}\}}$.

1. يختار${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$مع ≠ 0.
2. احسب${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$يكون المنحنى الإهليلجي E حينها في صيغة فايرشتراس المعطاة بواسطة${\displaystyle y^{2}=x^{3}+ax+b}$وباستخدام الإحداثيات الإسقاطية، يُعطى المنحنى الإهليلجي بالمعادلة المتجانسة${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$هذا صحيح.${\displaystyle P=(x_{P}:y_{P}:1)}$.
3. اختر حدًا أعلى${\displaystyle B\in \mathbb {Z} }$بالنسبة لهذا المنحنى الإهليلجي.
   • ملاحظة: لن تجد العوامل p إلا إذا كانت رتبة المجموعة g للمنحنى الإهليلجي E على${\displaystyle \mathbb {Z} /p\mathbb {Z} }$(يرمز إليه بـ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$) سلسة من النوع B ، مما يعني أن جميع العوامل الأولية لـ${\displaystyle n}$يجب أن تكون أقل من أو تساوي B.
4. احسب${\displaystyle k={\rm {lcm}}(1,\dots ,B)}$.
5. احسب${\displaystyle kP:=P+P+\cdots +P}$(الضرب هو جمع متكرر) في الحلقة${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$.
   • إذا نجحت العملية الحسابية${\displaystyle kP=(0:1:0)}$هذا يعني أن الدالة g ليست سلسة من النوع B أو أن n عدد أولي. ارجع إلى الخطوة 2 لاختيار منحنى آخر.
   • إذا فشلت العملية الحسابية في مرحلة ما، فهذا يعني إمكانية إيجاد قاسم غير تافه. قد تفشل العملية لأن الجمع والضرب غير مُعرّفين جيدًا إذا لم يكن n عددًا أوليًا، ولكن هذا يحدث فقط عند محاولة إيجاد معكوس باقي قسمة معين v . في هذه الحالة، يُوجد العامل على النحو التالي:${\displaystyle \gcd(v,n)}$كما سبق.

يذكر في النقطة 5 أنه في ظل ظروف معينة، يمكن إيجاد قاسم غير تافه. وكما أشير في مقال لينسترا (تحليل الأعداد الصحيحة باستخدام المنحنيات الإهليلجية)، فإن عملية الجمع تتطلب افتراضًا.${\displaystyle \gcd(x_{1}-x_{2},n)=1}$. لو${\displaystyle P,Q}$ليست${\displaystyle (0:1:0)}$وإذا كانت القيم متميزة (وإلا فإن عملية الجمع تعمل بشكل مشابه، ولكنها تختلف قليلاً)، فإن عملية الجمع تعمل على النحو التالي:

• لحساب:${\displaystyle R=P+Q;}$${\displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$،
• ${\displaystyle \lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}}$،
• ${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$،
• ${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$،
• ${\displaystyle R=P+Q=(x_{3}:y_{3}:1)}$.

إذا فشلت عملية الجمع، فسيكون ذلك بسبب خطأ في الحساب.${\displaystyle \lambda .}$على وجه الخصوص، لأن${\displaystyle (x_{1}-x_{2})^{-1}}$لا يمكن حسابها دائمًا إذا لم يكن n عددًا أوليًا (وبالتالي${\displaystyle \mathbb {Z} /n\mathbb {Z} }$(ليس حقلاً). دون الاستفادة من${\displaystyle \mathbb {Z} /n\mathbb {Z} }$وباعتباره حقلاً، يمكن للمرء أن يحسب:

• ${\displaystyle \lambda '=y_{1}-y_{2}}$،
• ${\displaystyle x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}}$،
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$،
• ${\displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})}$، وبسطها إن أمكن.

هذا الحساب قانوني دائمًا، وإذا كان القاسم المشترك الأكبر للإحداثي Z مع n ≠ (1 أو n )، لذلك عندما يفشل التبسيط، يتم العثور على قاسم غير تافه لـ n .

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

التعريف. ليكن${\displaystyle k}$أن يكون مجالًا${\displaystyle 2\neq 0}$ودع${\displaystyle a,d\in k\setminus \{0\}}$مع${\displaystyle a\neq d}$ثم منحنى إدواردز الملتوي${\displaystyle E_{E,a,d}}$يُعطى بواسطة${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$منحنى إدواردز هو منحنى إدواردز ملتوٍ حيث${\displaystyle a=1}$.

هناك خمس طرق معروفة لبناء مجموعة من النقاط على منحنى إدواردز: مجموعة النقاط الأفينية، ومجموعة النقاط الإسقاطية، ومجموعة النقاط المعكوسة، ومجموعة النقاط الممتدة، ومجموعة النقاط المكتملة.

مجموعة النقاط الأفينية معطاة بالصيغة التالية:

${\displaystyle \{(x,y)\in \mathbb {A} ^{2}:ax^{2}+y^{2}=1+dx^{2}y^{2}\}}$.

قانون الجمع معطى بالصيغة التالية

${\displaystyle (e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-aeg}{1-degfh}}\right).}$

النقطة (0,1) هي عنصرها المحايد ومعكوسها${\displaystyle (e,f)}$يكون${\displaystyle (-e,f)}$.

يتم تعريف التمثيلات الأخرى بشكل مشابه لكيفية اشتقاق منحنى وييرشتراس الإسقاطي من الخط الأفيني.

أي منحنى إهليلجي في صيغة إدواردز له نقطة من الرتبة 4. لذا فإن مجموعة الالتواء لمنحنى إدواردز فوق${\displaystyle \mathbb {Q} }$متماثل مع إما${\displaystyle \mathbb {Z} /4\mathbb {Z} ,\mathbb {Z} /8\mathbb {Z} ,\mathbb {Z} /12\mathbb {Z} ,\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$أو${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$.

أكثر الحالات إثارة للاهتمام في مجال إدارة المحتوى الإلكتروني هي${\displaystyle \mathbb {Z} /12\mathbb {Z} }$و${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$لأنها تجبر رتب المجموعة للمنحنى، بتردد الأعداد الأولية، على أن تكون قابلة للقسمة على 12 و16 على التوالي. المنحنيات التالية لها مجموعة التواء متماثلة مع${\displaystyle \mathbb {Z} /12\mathbb {Z} }$:

• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$مع نقطة${\displaystyle (a,b)}$أين${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)}$و${\displaystyle d=-(2b+1)/(a^{2}b^{2})}$
• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$مع نقطة${\displaystyle (a,b)}$أين${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$و${\displaystyle d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^{2}}},u\notin \{0,\pm 1\}.}$

يمكن كتابة كل منحنى إدواردز بنقطة من الرتبة 3 بالطرق الموضحة أعلاه. المنحنيات ذات مجموعة الالتواء المتماثلة مع${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$و${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$قد يكون أكثر كفاءة في إيجاد الأعداد الأولية. ^{[ 6 ]}

GMP-ECM من تطوير بول زيمرمان هو تطبيق عام لخوارزمية لينسترا، يعتمد على مكتبة GNU للحسابات متعددة الدقة . وقد تم تحديثه باستمرار، حيث كان أحدث إصدار له هو 7.0.6 (سبتمبر 2025) من يوليو 2024. يدعم هذا التطبيق منحنيات مونتغمري، وويرستراس، وهيسيان (الملتوية). ويمكنه تشغيل المرحلة الأولى لمجموعة فرعية من منحنيات مونتغمري على وحدة معالجة رسومية CUDA ، حيث تم استبدال التطبيق السابق الذي طوره سيريل بوفير عام 2012 بتطبيق أحدث من سيث ترويسي عام 2021. يتضمن الإصدار 7.0.6 أيضًا تطبيقًا لطريقة HECM (الموصوفة أدناه)، وطريقتي p-1 و p+1، وإثبات أولية الأعداد باستخدام APRCL. ^{[ 7 ]} يُستخدم GMP-ECM في SageMath .

نشر دانيال ج. بيرنشتاين وزملاؤه سلسلة من التطبيقات القائمة على منحنيات إدواردز الإهليلجية الملتوية بين عامي 2008 و2010. وتزعم جميعها تفوقها على النسخة المعاصرة من GMP-ECM، وأحدثها EECM-MPFQ الصادر عام 2008. كما يتوفر تطبيقان لوحدة معالجة الرسومات (GPU) من بيرنشتاين، أحدثهما وأسرعهما هو CUDA-EECM الصادر عام 2009. ^{[ 6 ] [ 8 ]}

يتضمن برنامج Prime95 تطبيقًا لخوارزمية Lenstra ECM لمنحنيات Montgomery وEdwards. يُستخدم هذا التطبيق في مشروع ECM الفرعي ضمن مشروع البحث عن أعداد Mersenne الأولية على الإنترنت ، والذي يهدف إلى تحليل أعداد Mersenne المركبة التي لا يقل حجمها عن 2^ ¹²¹³ . ^{[ 9 ]} يستطيع البرنامج إنتاج مخرجات المرحلة الأولى المتوافقة مع GMP-ECM، بالإضافة إلى استهلاك مخرجات المرحلة الأولى من GMP-ECM. ^{[ 10 ]} وهو أسرع من GMP-ECM في المرحلة الأولى. ^{[ 11 ]}

نشر جون ولوكا وزملاؤه في عام 2020 برنامج ecmongpu، وهو تطبيق للمرحلتين الأولى والثانية من خوارزمية Lenstra ECM القائمة على منحنيات إدواردز الإهليلجية الملتوية. وتتناول ورقتهم البحثية أداء تحليل المعاملات التي يصل طولها إلى 448 بت (بين 2447 ^و 2448 ^- 1). ^{[ 12 ]}

جميع البرامج المذكورة أعلاه مفتوحة المصدر. بالإضافة إلى ذلك، يحتوي كل من برنامج PARI/GP مفتوح المصدر وبرنامج Magma (نظام الجبر الحاسوبي) الخاص على "تطبيقات جيدة لخوارزمية ECM" وفقًا لبول زيمرمان. ^{[ 11 ]} وهناك تطبيق برمجي سابق ذو 16 بت ^{[ 13 ]} وهو giantint من تطوير ريتشارد كراندال. ^{[ 11 ]}

هناك تطورات حديثة في استخدام المنحنيات الإهليلجية الفائقة لتحليل الأعداد الصحيحة. يُبين كوسيت في مقالته (المنشورة عام 2010) أنه يمكن إنشاء منحنى إهليلجي فائق من النوع الثاني (أي منحنى${\displaystyle y^{2}=f(x)}$باستخدام دالة من الدرجة  الخامسة (f)، نحصل على نفس نتيجة استخدام منحنيين إهليلجيين "عاديين" في آن واحد. وباستخدام سطح كومر، تصبح الحسابات أكثر كفاءة. وتُعوَّض عيوب المنحنى الإهليلجي الفائق (مقارنةً بالمنحنى الإهليلجي) بهذه الطريقة البديلة للحساب. لذا، يزعم كوسيت تقريبًا أن استخدام المنحنيات الإهليلجية الفائقة في التحليل ليس أسوأ من استخدام المنحنيات الإهليلجية.

يقترح كل من بيرنشتاين وهينينجر ولو وفالينتا خوارزمية GEECM، وهي نسخة كمومية من خوارزمية ECM مع منحنيات إدواردز. ^{[ 14 ]} تستخدم هذه الخوارزمية خوارزمية جروفر لمضاعفة طول الأعداد الأولية التي تم العثور عليها تقريبًا مقارنةً بخوارزمية EECM القياسية، بافتراض وجود حاسوب كمومي مزود بعدد كافٍ من الكيوبتات وبسرعة مماثلة للحاسوب الكلاسيكي الذي يشغل خوارزمية EECM.

• بيرنشتاين، دانيال ج. بيركنر، بيتر؛ لانج، تانيا؛ بيترز، كريستيان (2013). "ECM باستخدام منحنيات إدواردز" . الرياضيات الحسابية . 82 (282): 1139–1179 . دوى : 10.1090/S0025-5718-2012-02633-0 . السيد 3008853 . 
• بوسما، دبليو؛ هولست، MPM فان دير (1990). البدائية تثبت مع بضع التدوير . دكتوراه. أطروحة، جامعة فان أمستردام. او سي ال سي 256778332 . 
• برنت، ريتشارد ب. (1999). "تحليل العدد العاشر من فيرما إلى عوامله الأولية" . رياضيات الحساب . 68 (225): 429-451 . Bibcode : 1999MaCom..68..429B . doi : 10.1090/S0025-5718-99-00992-8 . MR 1489968 . 
• كوهين، هنري (1993). دورة في نظرية الأعداد الجبرية الحاسوبية . نصوص الدراسات العليا في الرياضيات. المجلد  138. برلين: سبرينغر-فيرلاغ. doi : 10.1007/978-3-662-02945-9 . ISBN 978-0-387-55640-6. MR 1228206 . S2CID 118037646 .  
• كوسيت، ر. (2010). "التحليل باستخدام منحنيات من النوع 2". رياضيات الحساب . 79 (270): 1191-1208 . arXiv : 0905.2325 . Bibcode : 2010MaCom..79.1191C . doi : 10.1090/S0025-5718-09-02295-9 . MR 2600562. S2CID 914296 .  
• لينسترا، أ.ك .؛ لينسترا الابن، هـ.و.، محرران. (1993). تطور غربال حقل الأعداد . سلسلة محاضرات في الرياضيات. المجلد  1554. برلين: سبرينغر-فيرلاغ. الصفحات 11-42 . doi : 10.1007/BFb0091534 . ISBN  978-3-540-57013-4MR 1321216 .​ 
• لينسترا الابن، إتش دبليو (1987). " تحليل الأعداد الصحيحة باستخدام المنحنيات الإهليلجية" (ملف PDF) . حوليات الرياضيات . 126 (3): 649-673 . doi : 10.2307/1971363 . hdl : 1887/2140 . JSTOR 1971363. MR 0916721 .  
• بوميرانس، كارل ؛ كراندال، ريتشارد (2005). الأعداد الأولية: منظور حسابي (  الطبعة الثانية). نيويورك: سبرينغر. ISBN 978-0-387-25282-7MR 2156291 .​ 
• بوميرانس، كارل (1985). "خوارزمية تحليل المنخل التربيعي". التطورات في علم التشفير، وقائع مؤتمر يورو كريبت 84. سلسلة محاضرات في علوم الحاسوب. المجلد  209. برلين: سبرينغر-فيرلاغ. الصفحات 169-182 . doi : 10.1007/3-540-39757-4_17 . ISBN  978-3-540-16076-2MR 0825590 .​ 
• بوميرانس، كارل (1996). "حكاية غربالين" (ملف PDF) . إشعارات الجمعية الرياضية الأمريكية . 43 (12): 1473-1485 . MR 1416721 . 
• سيلفرمان، روبرت د. (1987). "المنخل التربيعي متعدد الحدود" . رياضيات الحساب . 48 (177): 329-339 . doi : 10.1090/S0025-5718-1987-0866119-8 . MR 0866119 . 
• ترابي، دبليو؛ واشنطن، إل سي (2006). مقدمة في علم التشفير مع نظرية الترميز (  الطبعة الثانية). سادل ريفر، نيوجيرسي: بيرسون برنتيس هول. ISBN 978-0-13-186239-5MR 2372272 .​ 
• صموئيل س. واغستاف الابن (2013). متعة التحليل إلى عوامل . بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات. الصفحات 173-190 . ISBN  978-1-4704-1048-3.
• واتراس، مارسين (2008). التشفير، تحليل الأعداد، والأعداد الكبيرة جدًا . بيدغوشتش: فويتشوفسكي-شتاينهاغن. PL:5324564.

• التحليل باستخدام طريقة المنحنى الإهليلجي ، وهو تطبيق WebAssembly يستخدم ECM ويتحول إلى الغربال التربيعي ذاتي التهيئة عندما يكون أسرع.
• تمت أرشفة GMP-ECM في 12-09-2009 على Wayback Machine ، وهو تطبيق فعال لـ ECM.
• ECMNet ، وهو تطبيق سهل للعميل والخادم يعمل مع العديد من مشاريع التحليل.
• pyecm ، وهو تطبيق بايثون لـ ECM.
• مشروع الحوسبة الموزعة yoyo@Home المشروع الفرعي ECM هو برنامج لتحليل المنحنى الإهليلجي والذي يستخدم لإيجاد عوامل لأنواع مختلفة من الأرقام.
• شفرة المصدر لخوارزمية تحليل المنحنى الإهليلجي Lenstra، شفرة المصدر لخوارزمية تحليل المنحنى الإهليلجي بلغة C البسيطة و GMP.
• EECM-MPFQ هو تطبيق لـ ECM باستخدام منحنيات إدواردز مكتوب باستخدام مكتبة MPFQ للحقول المحدودة.