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

قد تكون هذه المقالة تقنية للغاية بحيث يصعب على معظم القراء فهمها . يرجى المساعدة في تحسينها لجعلها مفهومة لغير الخبراء ، دون إزالة التفاصيل التقنية. ( ديسمبر 2020 ) ( تعرف على كيفية ومتى يمكنك إزالة هذه الرسالة )

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

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

تعمل طريقة تحليل المنحنى الإهليلجي لينسترا لإيجاد عامل لعدد طبيعي معين على النحو التالي: ${\displaystyle n}$

1. اختر منحنى إهليلجي عشوائي على (الأعداد الصحيحة modulo )، مع معادلة النموذج مع نقطة غير تافهة عليه. ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle n}$${\displaystyle y^{2}=x^{3}+ax+b{\pmod{n}}}$ ${\displaystyle P(x_{0},y_{0})}$

   يمكن القيام بذلك عن طريق اختيار عشوائي أولاً ، ثم ضبطه للتأكد من أن النقطة تقع على المنحنى.${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} }$${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod{n}}}$

2. يمكن تعريف جمع نقطتين على المنحنى لتحديد مجموعة . قوانين الجمع موضحة في المقالة حول المنحنيات الإهليلجية .

   يمكننا تكوين مضاعفات متكررة لنقطة : . تتضمن صيغ الجمع أخذ المنحدر النمطي لوتر يربط بين و ، وبالتالي القسمة بين فئات البقايا modulo ، والتي يتم إجراؤها باستخدام خوارزمية إقليدية ممتدة . على وجه الخصوص، تتضمن القسمة على بعض حساب .${\displaystyle P}$${\displaystyle [k]P=P+\ldots +P{\text{ (k مرة)}}}$${\displaystyle P}$${\displaystyle س}$${\displaystyle n}$${\displaystyle v{\bmod {n}}}$${\displaystyle \gcd(v,n)}$

   بافتراض أننا نحسب ميلًا من النموذج مع ، فإذا كانت ، فإن نتيجة جمع النقاط ستكون ، النقطة "عند اللانهاية" المقابلة لتقاطع الخط "الرأسي" الذي يربط المنحنى. ومع ذلك، إذا كانت ، فإن جمع النقاط لن ينتج نقطة ذات معنى على المنحنى؛ ولكن الأهم من ذلك، هو عامل غير تافه لـ .${\displaystyle u/v}$${\displaystyle \gcd(u,v)=1}$${\displaystyle v=0{\bmod {n}}}$${\displaystyle \infty }$${\displaystyle P(x,y),P'(x,-y)}$${\displaystyle \gcd(v,n)\neq 1,n}$${\displaystyle \gcd(v,n)}$${\displaystyle n}$

3. احسب على المنحنى الإهليلجي ( )، حيث هو حاصل ضرب العديد من الأعداد الصغيرة: على سبيل المثال، حاصل ضرب الأعداد الأولية الصغيرة المرفوعة إلى قوى صغيرة، كما في خوارزمية p-1 ، أو العامل لبعض الأعداد غير الكبيرة جدًا . يمكن القيام بذلك بكفاءة، عامل صغير واحد في كل مرة. على سبيل المثال، للحصول على ، احسب أولاً ، ثم ، ثم ، وهكذا. يتم اختيار أن يكون صغيرًا بما يكفي بحيث يمكن إجراء إضافة نقطة - بحكمة في وقت معقول. ${\displaystyle [k]P}$${\displaystyle {\bmod {n}}}$${\displaystyle k}$ ${\displaystyle ب!}$${\displaystyle B}$${\displaystyle [B!]P}$${\displaystyle [2]ص}$${\displaystyle [3]([2]P)}$${\displaystyle [4]([3!]P)}$${\displaystyle B}$${\displaystyle B}$
   • إذا أنهينا جميع العمليات الحسابية أعلاه دون مواجهة عناصر غير قابلة للعكس ( )، فهذا يعني أن ترتيب المنحنيات الإهليلجية (modulo primes) ليس سلسًا بدرجة كافية، لذا نحتاج إلى المحاولة مرة أخرى بمنحنى ونقطة بداية مختلفين.${\displaystyle {\bmod {n}}}$
   • إذا واجهنا فإننا ننتهي: إنه عامل غير تافه من .${\displaystyle \gcd(v,n)\neq 1,n}$${\displaystyle n}$

تعتمد التعقيد الزمني على حجم أصغر عامل أولي للعدد ويمكن تمثيله بواسطة exp[( √ 2  +  o (1)) √ ln  p  ln ln  p ] ، حيث p هو أصغر عامل لـ n ، أو ، في صيغة L.${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]}$

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

إن ECM في جوهره عبارة عن تحسين لخوارزمية p −  1 القديمة . تجد خوارزمية p  − 1 العوامل الأولية p بحيث تكون p  − 1 سلسة أسية للقيم الصغيرة لـ 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)، مع إضافة بعض التفاصيل.

نريد أن نحلل n = 455839 إلى عواملها. فلنختر المنحنى الإهليلجي y ² = x ³ + 5 x – 5، مع النقطة P = (1, 1) عليه، ولنحاول حساب (10!) P.

ميل الخط المماس عند نقطة ما A =( x , y ) هو s = (3 x ² + 5)/(2 y ) (mod n) . باستخدام s يمكننا حساب 2 A. إذا كانت قيمة s من النموذج a/b حيث b > 1 و gcd( a , b ) = 1، فيجب علينا إيجاد المعكوس النمطي لـ b . إذا لم يكن موجودًا، فإن gcd( n , b ) هو عامل غير تافه لـ n .

أولاً نحسب 2 P. لدينا s ( P ) = s (1,1) = 4، لذا فإن إحداثيات 2 P = ( x ′ , y ′ ) هي x ′ = s ² – 2 x = 14 و y ′ = s ( x – x ′ ) – y = 4(1 – 14) – 1 = –53، كل الأرقام مفهومة (mod n ). فقط للتأكد من أن 2 P هذه موجودة بالفعل على المنحنى: (–53) ² = 2809 = 14 ³ + 5·14 – 5.

ثم نحسب 3(2 P ). لدينا s (2 P ) = s (14,-53) = –593/106 (mod n ). باستخدام الخوارزمية الإقليدية : 455839 = 4300·106 + 39، ثم 106 = 2·39 + 28، ثم 39 = 28 + 11، ثم 28 = 2·11 + 6، ثم 11 = 6 + 5، ثم 6 = 5 + 1. وبالتالي، فإن القاسم المشترك الأعظم (455839، 106) = 1، والعمل في الاتجاه المعاكس (نسخة من الخوارزمية الإقليدية الممتدة ): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. ومن ثم 106 ⁻¹ = 81707 (mod 455839)، و -593/106 = -133317 (mod 455839). وبالنظر إلى هذا s ، يمكننا حساب إحداثيات 2(2 P )، تمامًا كما فعلنا أعلاه: 4 P = (259851، 116255). فقط للتحقق من أن هذه نقطة على المنحنى بالفعل: y ² = 54514 = x ³ + 5 x – 5 (mod 455839). بعد ذلك، يمكننا حساب . ${\displaystyle 3(2P)=4P\boxزائد 2P}$

يمكننا حساب 4! P ، وهكذا، ولكن 8! P تتطلب عكس 599 (mod 455839). تعطي الخوارزمية الإقليدية أن 455839 قابل للقسمة على 599، وقد وجدنا تحليل العوامل 455839 = 599·761.

السبب وراء نجاح ذلك هو أن المنحنى (mod 599) به 640 = 2 ⁷ ·5 نقطة، بينما (mod 761) به 777 = 3·7·37 نقطة. علاوة على ذلك، فإن 640 و777 هما أصغر عددين صحيحين موجبين k بحيث يكون kP = ∞ على المنحنى (mod 599) و (mod 761)، على التوالي. نظرًا لأن 8! مضاعف لـ 640 ولكنه ليس مضاعفًا لـ 777، فلدينا 8! P = ∞ على المنحنى (mod 599)، ولكن ليس على المنحنى (mod 761)، ومن ثم فإن الجمع المتكرر قد فشل هنا، مما أدى إلى التحليل إلى عوامل.

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

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

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

1. إختر بـ ≠ 0.${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$
2. احسب . يكون المنحنى الإهليلجي E في صيغة فايرستراس ويعطى بواسطة وباستخدام إحداثيات إسقاطية يتم إعطاء المنحنى الإهليلجي بواسطة المعادلة المتجانسة . وله النقطة .${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$${\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. اختر الحد الأعلى لهذا المنحنى الإهليلجي. ملاحظة: لن تجد العوامل p إلا إذا كان ترتيب المجموعة للمنحنى الإهليلجي E على (المشار إليه بواسطة ) هو B-smooth ، مما يعني أن جميع العوامل الأولية لـ يجب أن تكون أقل من أو تساوي B.${\displaystyle B\in \mathbb {Z} }$${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
4. احسب .${\displaystyle k={\rm {lcm}}(1,\dots ,B)}$
5. احسب ( k مرات) في الحلقة . لاحظ أنه إذا كان B -smooth وكان n أوليًا (وبالتالي فهو حقل) فإن . ومع ذلك، إذا كان B-smooth فقط لبعض المقسومات p لـ n ، فقد لا يكون المنتج (0:1:0) لأن الجمع والضرب غير محددين جيدًا إذا لم يكن n أوليًا. في هذه الحالة، يمكن إيجاد مقسوم غير تافه.${\displaystyle kP:=P+P+\cdots +P}$${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \#E(\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle kP=(0:1:0)}$${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$
6. إذا لم يحدث ذلك، فارجع إلى الخطوة 2. إذا حدث هذا، فستلاحظ ذلك عند تبسيط المنتج${\displaystyle kP.}$

في النقطة 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)}$.

إذا فشلت عملية الجمع، فسوف يكون ذلك بسبب فشل الحساب ، وخاصةً لأنه لا يمكن دائمًا حساب n إذا لم يكن n عددًا أوليًا (وبالتالي ليس حقلًا). وبدون الاستفادة من كونه حقلًا، يمكن للمرء أن يحسب: ${\displaystyle \lambda .}$${\displaystyle (x_{1}-x_{2})^{-1}}$${\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} }$

الحالات الأكثر إثارة للاهتمام لـ ECM هي و ، حيث إنها تجبر أوامر المجموعة لمنحنى modulo primes على أن تكون قابلة للقسمة على 12 و16 على التوالي. المنحنيات التالية لها مجموعة التواء متماثلة إلى : ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$${\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 بالطرق الموضحة أعلاه. المنحنيات ذات المجموعة الالتوائية المتماثلة مع و قد تكون أكثر كفاءة في إيجاد الأعداد الأولية. ^[2]${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$

يتعلق النص أعلاه بالمرحلة الأولى من تحليل المنحنى الإهليلجي. وفي هذه المرحلة نأمل في العثور على قاسم أولي p بحيث يكون العنصر المحايد لـ . وفي المرحلة الثانية نأمل في العثور على قاسم أولي q بحيث يكون له ترتيب أولي صغير في . ${\displaystyle sP}$${\displaystyle E(\mathbb {Z} /p\mathbb {Z} )}$${\displaystyle sP}$${\displaystyle E(\mathbb {Z} /q\mathbb {Z} )}$

نأمل أن يكون الترتيب بين و ، حيث يتم تحديده في المرحلة 1 و هو معلمة جديدة للمرحلة 2. يمكن التحقق من الترتيب الصغير لـ ، عن طريق حساب modulo n لكل عدد أولي l . ${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\displaystyle sP}$${\displaystyle (ls)P}$

لقد استخدم بيرنشتاين وآخرون ^[2] منحنيات إدواردز الإهليلجية الملتوية، بالإضافة إلى تقنيات أخرى ، لتوفير تنفيذ محسن لـ ECM. العيب الوحيد في هذه التقنية هو أنها تعمل على أعداد مركبة أصغر من التنفيذ الأكثر عمومية، GMP-ECM لـ Zimmerman.

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

يقترح بيرنشتاين وهينينجر ولو وفالينتا GEECM، وهي نسخة كمية من ECM مع منحنيات إدواردز. [ ^3] تستخدم خوارزمية جروفر لمضاعفة طول الأعداد الأولية الموجودة تقريبًا مقارنةً بـ 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. السيد  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. برلين: سبرينغر فيرلاغ. doi :10.1007/BFb0091534. ISBN 978-3-540-57013-4. السيد  1321216.
• لينسترا جونيور، إتش دبليو (1987). "تحليل الأعداد الصحيحة باستخدام المنحنيات الإهليلجية" (ملف PDF) . حوليات الرياضيات . 126 (3): 649–673. doi :10.2307/1971363. hdl : 1887/2140 . JSTOR  1971363. MR  0916721.
• بوميرانس، كارل ؛ كراندال، ريتشارد (2005). الأعداد الأولية: منظور حسابي (الطبعة الثانية). نيويورك: سبرينغر. رقم ISBN 978-0-387-25282-7. السيد  2156291.
• بوميرانس، كارل (1985). "خوارزمية تحليل العوامل المنخلية التربيعية". التقدم في علم التشفير، وقائع يوروكريبت 84. محاضرات في علوم الكمبيوتر. المجلد 209. برلين: سبرينغر فيرلاغ. ص 169-182. doi :10.1007/3-540-39757-4_17. ISBN 978-3-540-16076-2. السيد  0825590.
• بوميرانس، كارل (1996). "حكاية منخلين" (PDF) . إشعارات الجمعية الرياضية الأمريكية . 43 (12): 1473-1485. MR  1416721.
• سيلفرمان، روبرت د. (1987). "الغربال التربيعي متعدد الحدود". رياضيات الحوسبة . 48 (177): 329-339. doi : 10.1090/S0025-5718-1987-0866119-8 . MR  0866119.
• Trappe, W.; Washington, LC (2006). Introduction to Cryptography with Coding Theory (Second ed.). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5. السيد  2372272.
• صامويل س. واجستاف الابن (2013). متعة التحليل إلى عوامل. بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية. ص 173-190. رقم ISBN 978-1-4704-1048-3.
• واتراس، مارسين (2008). التشفير وتحليل الأرقام والأعداد الكبيرة جدًا . بيدغوز: فويتشوفسكي-شتاينهاجن. PL:5324564.

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