تحليل الأعداد الصحيحة إلى عواملها الأولية

مشكلة لم تُحل في علوم الحاسوب

هل يمكن حل مسألة تحليل الأعداد الصحيحة إلى عواملها الأولية في وقت متعدد الحدود على جهاز كمبيوتر تقليدي؟

في الرياضيات ، يُعرف تحليل الأعداد الصحيحة إلى عواملها الأولية بأنه تفكيك عدد صحيح موجب إلى حاصل ضرب أعداد صحيحة. كل عدد صحيح موجب أكبر من 1 هو إما حاصل ضرب عاملين صحيحين أو أكثر أكبر من 1، وفي هذه الحالة يكون عددًا مركبًا ، أو ليس كذلك، وفي هذه الحالة يكون عددًا أوليًا . على سبيل المثال، $15$ عدد مركب لأن $15 = 3 \times 5$ ، بينما $7$ عدد أولي لأنه لا يمكن تحليله بهذه الطريقة. إذا كان أحد العوامل مركبًا، فيمكن كتابته بدوره كحاصل ضرب عوامل أصغر، على سبيل المثال $60 = 3 \times 20 = 3 \times (5 \times 4)$ . يُطلق على استمرار هذه العملية حتى يصبح كل عامل أوليًا اسم التحليل إلى العوامل الأولية ؛ وتكون النتيجة دائمًا فريدة حتى رتبة العوامل وفقًا لنظرية التحليل إلى العوامل الأولية .

لتحليل عدد صحيح صغير $n$ إلى عوامله الأولية باستخدام الحساب الذهني أو الورقي، فإن أبسط طريقة هي القسمة التجريبية : التحقق مما إذا كان العدد يقبل القسمة على الأعداد الأولية $2$ ، $3$ ، $5$ ، وهكذا، حتى الجذر التربيعي لـ $n$ . أما بالنسبة للأعداد الأكبر، وخاصة عند استخدام الحاسوب، فإن خوارزميات التحليل إلى العوامل الأولية الأكثر تطورًا تكون أكثر كفاءة. تتضمن خوارزمية التحليل إلى العوامل الأولية عادةً اختبار ما إذا كان كل عامل أوليًا في كل مرة يتم فيها العثور على عامل.

عندما تكون الأعداد كبيرة بما يكفي، لا توجد خوارزمية فعّالة لتحليل الأعداد الصحيحة إلى عواملها الأولية غير الكمومية . مع ذلك، لم يُثبت عدم وجود مثل هذه الخوارزمية. تُعدّ الصعوبة المفترضة لهذه المسألة مهمة للخوارزميات المستخدمة في علم التشفير ، مثل تشفير المفتاح العام RSA والتوقيع الرقمي RSA . ^[¹^] وقد استُخدمت العديد من مجالات الرياضيات وعلوم الحاسوب في حلّ هذه المسألة، بما في ذلك المنحنيات الإهليلجية ، ونظرية الأعداد الجبرية ، والحوسبة الكمومية.

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

تعتمد العديد من بروتوكولات التشفير على الصعوبة المفترضة لتحليل الأعداد الصحيحة المركبة الكبيرة إلى عواملها الأولية، أو على مشكلة مشابهة - على سبيل المثال، مشكلة RSA . إن وجود خوارزمية قادرة على تحليل أي عدد صحيح بكفاءة إلى عوامله الأولية سيجعل التشفير بالمفتاح العام القائم على RSA غير آمن.

التحلل الأولي

التحليل الأولي للعدد $n = 864$ هو $25 \times 3 3$

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

باستخدام خوارزمية عامة لتحليل الأعداد الصحيحة إلى عواملها الأولية، يمكن تحليل أي عدد صحيح إلى عوامله الأولية المكونة له بتطبيق هذه الخوارزمية بشكل متكرر. يصبح الوضع أكثر تعقيدًا مع خوارزميات التحليل المتخصصة، التي قد لا تُحقق فوائدها بنفس الكفاءة أو حتى على الإطلاق مع العوامل الناتجة أثناء التحليل. على سبيل المثال، إذا كان $n = 171 \times p \times q$ حيث $p < q$ أعداد أولية كبيرة جدًا، فإن القسمة التجريبية ستنتج بسرعة العاملين 3 و19، ولكنها ستتطلب $p$ عملية قسمة لإيجاد العامل التالي. كمثال معاكس، إذا كان $n$ هو حاصل ضرب الأعداد الأولية $13729$ و $1372933$ و $18848997161$ ، حيث $13729 \times 1372933 = 18848997157$ ، فإن طريقة فيرما للتحليل إلى عوامل ستبدأ بـ $⌈ \sqrt n ⌉ = 18848997159$ والتي تعطي مباشرة $b = \sqrt a 2 - n = \sqrt 4 = 2$ وبالتالي العوامل $a - b = 18848997157$ و $a + b = 18848997161$ . في حين أنه من السهل التعرف على هذه الأعداد على أنها مركبة وأولية على التوالي، فإن طريقة فيرما ستستغرق وقتًا أطول بكثير لتحليل العدد المركب لأن القيمة الابتدائية لـ $⌈ \sqrt 18848997157 ⌉ = 137292$ لـ $a$ هي عامل 10 من $1372933$ .

أحدث التقنيات

من بين الأعداد المكونة $من b$ بت، تُعدّ الأعداد شبه الأولية التي تتشابه عواملها في الحجم، الأصعب في التحليل العملي باستخدام الخوارزميات الحالية . ولهذا السبب، تُستخدم هذه الأعداد الصحيحة في التطبيقات التشفيرية.

في عام 2019، تمكن فريق من الباحثين، من بينهم بول زيمرمان ، من تحليل عدد مكون من 240 رقمًا (795 بت) ( RSA-240 ) ، مستخدمين ما يقارب 900 سنة من قوة الحوسبة. ^[²^] وقدّر هؤلاء الباحثون أن تحليل معامل RSA مكون من 1024 بت سيستغرق وقتًا أطول بنحو 500 مرة. ^[³^]

أكبر عدد شبه أولي تم تحليله حتى الآن هو RSA-250 ، وهو عدد مكون من 829 بتًا و250 رقمًا عشريًا، وذلك في فبراير 2020. استغرقت عملية التحليل ما يقارب 2700 سنة معالجة باستخدام معالج Intel Xeon Gold 6130 بسرعة 2.1 جيجاهرتز. وكما هو الحال مع جميع الأرقام القياسية الحديثة في تحليل الأعداد، فقد تم إنجاز هذا التحليل باستخدام تطبيق مُحسَّن للغاية لخوارزمية غربلة حقول الأعداد العامة ، والتي تم تشغيلها على مئات الأجهزة.

تعقيد الخطة

لم تُنشر أي خوارزمية قادرة $على$ تحليل جميع الأعداد الصحيحة إلى عواملها الأولية في زمن متعدد الحدود ، أي خوارزمية قادرة على تحليل عدد مكون من $b بت$ $n$ في زمن $O (bk)$ حيث $k$ ثابت . لم يُثبت وجود أو عدم وجود مثل هذه الخوارزميات، ولكن يُشتبه عمومًا في عدم وجودها. ^{[ 4 ]}^{[ 5 ]}

توجد خوارزميات منشورة أسرع من $O((1 + ε) b)$ لجميع $قيم ε$ الموجبة ، أي أنها أسرع من الخوارزمية شبه الأسية . اعتبارًا من عام 2022، الخوارزمية ذات أفضل وقت تشغيل نظري تقاربي هي غربال حقل الأرقام العام (GNFS)، الذي نُشر لأول مرة في عام 1993، ^{[ 6 ]} ويعمل على عدد مكون من $b بت$ $n$ في الوقت:

\exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).

بالنسبة للحواسيب الحالية، تُعدّ خوارزمية GNFS أفضل خوارزمية منشورة $للأعداد$ الكبيرة (أكثر من 400 بت تقريبًا). أما بالنسبة للحواسيب الكمومية ، فقد اكتشف بيتر شور في عام 1994 خوارزميةً تُحلّ هذه المسألة في زمن متعدد الحدود. تستغرق خوارزمية شور زمنًا قدره $O$ $(b³) ومساحةً قدرها$ $O(b)$ فقط عند إدخال أعداد مكونة $من b$ بت. في عام 2001، طُبّقت خوارزمية شور لأول مرة باستخدام تقنيات الرنين المغناطيسي النووي على جزيئات تُوفّر سبعة كيوبتات. ^{[ 7 ]}

من أجل الحديث عن فئات التعقيد مثل P و NP و co-NP، يجب صياغة المشكلة كمشكلة قرار .

مسألة القرار (تحليل الأعداد الصحيحة إلى عواملها الأولية) - لكل عدد طبيعي $n$ و $k$ هل يوجد لـ $n$ عامل أصغر من $k$ غير 1؟

من المعروف أن هذه المسألة تنتمي إلى فئتي $NP و co-NP، مما يعني إمكانية التحقق من صحة إجابتي "نعم" و "لا" في وقت متعدد الحدود. يمكن إثبات صحة إجابة "نعم" بإظهار تحليل n = d(n$ / d ) حيث $d \leq k . ويمكن إثبات صحة إجابة$ " $لا "$ $بإظهار$ تحليل $n$ إلى عوامل أولية مختلفة، جميعها أكبر من $k ؛ ويمكن التحقق$ $من$ أوليتها باستخدام اختبار AKS للأولية ، ثم ضربها للحصول على $n$ . تضمن النظرية الأساسية للحساب وجود سلسلة واحدة فقط من الأعداد الأولية المتزايدة التي سيتم قبولها، مما يدل على أن المسألة تنتمي إلى فئتي UP و co-UP. ^{[ 8 ]} ومن المعروف أنها تنتمي إلى فئة BQP بفضل خوارزمية شور.

يُشتبه في أن المشكلة تقع خارج نطاق فئات التعقيد الثلاث: P، وNP-complete، ^{[ 9 ]} و co-NP-complete . ولذلك فهي مرشحة لفئة التعقيد NP-intermediate .

على النقيض من ذلك، تبدو مسألة تحديد ما إذا كان العدد $n$ عددًا مركبًا (أو ما يعادله: هل $n عددًا أوليًا؟) أسهل بكثير من مسألة تحديد عوامل$ $n$ . يمكن حل مسألة التركيب/الأولية في وقت متعدد الحدود (بالنسبة لعدد أرقام $n ، وهو$ $b$ ) باستخدام اختبار AKS للأولية . إضافةً إلى ذلك، توجد العديد من الخوارزميات الاحتمالية التي يمكنها اختبار أولية الأعداد بسرعة كبيرة عمليًا إذا تم قبول احتمال ضئيل للغاية للخطأ. تُعد سهولة اختبار أولية الأعداد جزءًا أساسيًا من خوارزمية RSA ، إذ يتطلب الأمر إيجاد أعداد أولية كبيرة في البداية.

خوارزميات التحليل إلى عوامل

أغراض خاصة

يعتمد وقت تشغيل خوارزمية التحليل إلى عوامل ذات غرض خاص على خصائص العدد المراد تحليله أو على أحد عوامله المجهولة: الحجم، الشكل الخاص، إلخ. تختلف المعلمات التي تحدد وقت التشغيل بين الخوارزميات.

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

قسم المحاكمة
تحليل العجلة
خوارزمية بولارد رو ، والتي لها نوعان شائعان لتحديد دورات المجموعة : أحدهما من قبل فلويد والآخر من قبل برنت.
خوارزميات تحليل المجموعات الجبرية ، ومن بينها خوارزمية بولارد $p - 1$ ، وخوارزمية ويليامز $p + 1$ ، وتحليل منحنى لينسترا الإهليلجي
طريقة فيرما للتحليل إلى عوامل
طريقة أويلر للتحليل إلى عوامل
غربال حقل الأرقام الخاص
الفرق بين مربعين

متعدد الأغراض

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

خوارزميات أخرى بارزة

خوارزمية شور ، لأجهزة الكمبيوتر الكمومية

وقت التشغيل الاستدلالي

في نظرية الأعداد، هناك العديد من خوارزميات تحليل الأعداد الصحيحة التي لها وقت تشغيل متوقع بشكل استدلالي

L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}

في تدوين θ الصغير و L. من أمثلة هذه الخوارزميات طريقة المنحنى الإهليلجي والمنخل التربيعي . ومن الخوارزميات الأخرى طريقة علاقات زمرة الفئات التي اقترحها شنور ^{[ 11 ]} ، وسيسن ^{[ 12 ]} ، ولينسترا ^{[ 13 ]} ، والتي أثبتوها بافتراض فرضية ريمان المعممة غير المثبتة .

وقت تشغيل صارم

لقد أثبت لينسترا وبوميرانس ^{[ 14 ]} بدقة أن خوارزمية شنور-سيسن-لينسترا الاحتمالية تتمتع بوقت تشغيل متوقع $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ عن طريق استبدال فرضية GRH باستخدام المضاعفات. تستخدم الخوارزمية زمرة فئات الأشكال التربيعية الثنائية الموجبة للمميز Δ، $والتي$ يُرمز لها بـ $G Δ$ . $G Δ$ هي مجموعة ثلاثيات الأعداد الصحيحة $(a, b, c)$ حيث تكون هذه الأعداد أولية نسبية.

خوارزمية شنور-سايسن-لينسترا

بفرض وجود عدد صحيح $n$ يُراد تحليله إلى عوامله الأولية، حيث $n$ عدد صحيح فردي موجب أكبر من ثابت معين. في خوارزمية التحليل هذه، يُختار المميز $Δ$ كمضاعف لـ $n$ ، أي $Δ = - dn$ ، حيث $d$ مُضاعِف موجب. تفترض الخوارزمية أنه بالنسبة لقيمة $d$ معينة ، توجد أشكال سلسة كافية في $GΔ .$ وقد بيّن لينسترا وبوميرانس أنه يمكن حصر اختيار $d$ في مجموعة صغيرة لضمان الحصول على نتيجة سلسة.

لنرمز بـ $PΔ إلى$ مجموعة جميع الأعداد الأولية $q$ التي يكون $رمز$ كرونكر لها $($ $Δ / q) = 1. من$ $خلال$ إنشاء مجموعة مولدات GΔ والأشكال الأولية $fq$ لـ $GΔ$ حيث $q$ ينتمي إلى $PΔ$ $،$ $نحصل على$ سلسلة من العلاقات بين مجموعة المولدات و $fq$ $.$ $يمكن$ تحديد حجم $q$ بالعلاقة $c₀$ $(log$ $|$ $Δ$ $|$ $)$ $²$ $،$ حيث $c₀$ $ثابت$ $.$

العلاقة المستخدمة هي علاقة بين حاصل ضرب القوى الذي يساوي العنصر المحايد في $GΔ .$ تُستخدم هذه العلاقات لإنشاء ما يُسمى بالصيغة المبهمة لـ $GΔ ،$ وهي عنصر من $GΔ$ رتبته تقسم 2. بحساب التحليل المُناظر لـ $Δ$ وإيجاد القاسم المشترك الأكبر، تُوفر هذه الصيغة المبهمة التحليل الكامل للعدد $n$ $إلى$ عوامله الأولية . تتضمن هذه الخوارزمية الخطوات الرئيسية التالية:

ليكن $n$ هو العدد المراد تحليله إلى عوامله الأولية.

ليكن $Δ$ عددًا صحيحًا سالبًا مع $Δ = - dn$ ، حيث $d$ هو عامل الضرب و $Δ$ هو المميز السالب لبعض الأشكال التربيعية.
خذ الأعداد $الأولية$ الأولى $p 1 = 2،$ p $2$ $=$ $3،$ $p$ $3$ $= 5، ...،$ $p$ $t$ ، لبعض $t \in N.$
ليكن $f q$ شكلاً أولياً عشوائياً لـ $G Δ$ مع $(⁠ Δ / q ⁠) = 1$ .
أوجد مجموعة مولدة $X$ للمجموعة $G Δ$ .
اجمع سلسلة من العلاقات بين المجموعة $X$ و ${f q : q \in P Δ}$ التي تحقق ما يلي:
$\left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.$
قم بإنشاء شكل غامض $(a, b, c)$ وهو عنصر $f \in G Δ$ من الرتبة التي تقسم 2 للحصول على تحليل أولي مشترك لأكبر قاسم فردي لـ $Δ$ حيث $Δ = -4ac أو$ Δ $= a (a - 4c) أو$ Δ $= (b - 2a) (b + 2a)$ .
إذا كانت الصيغة المبهمة تُعطي تحليلًا لـ $n$ ، فتوقف، وإلا فابحث عن صيغة مبهمة أخرى حتى تجد التحليل لـ $n$ . ولمنع توليد صيغ مبهمة غير مفيدة، قم ببناء زمرة سيلو 2- $Sill 2 (Δ)$ لـ $G (Δ)$ .

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

مدة التشغيل المتوقعة

الخوارزمية كما هي مذكورة هي خوارزمية احتمالية لأنها تقوم باختيارات عشوائية. زمن تشغيلها المتوقع هو على الأكثر $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ . ^{[ 14 ]}

انظر أيضاً

تحليل أوريفويل
خوارزمية باخ – لتوليد أعداد عشوائية مُحللة إلى عوامل
التمثيل المتعارف عليه لعدد صحيح موجب
التحليل إلى عوامل
التقسيم الضربي – طريقة لكتابة عدد كحاصل ضرب أعداد أخرى
التقييم $p -adic$
تجزئة الأعداد الصحيحة – تحليل عدد صحيح إلى مجموع أعداد صحيحة موجبة

ملحوظات

^ Lenstra، Arjen K. (2011)، “Integer Factoring”، in van Tilborg، Henk CA؛ Jajodia، Sushil (eds.)، موسوعة التشفير والأمن ، بوسطن: سبرينغر، الصفحات من 611 إلى 618، دوى : 10.1007/978-1-4419-5906-5_455 ، ISBN 978-1-4419-5905-8
↑ " [ Cado-nfs-discuss ] تحليل الأعداد ذات 795 بت واللوغاريتمات المنفصلة" . مؤرشف من الأصل بتاريخ 2019-12-02.
^ كلينجونج ، ثورستن. أوكي، كازومارو؛ فرانكي، ينس؛ لينسترا، آرجين ك.؛ تومي، إيمانويل. بوس، جوبي دبليو؛ جودري، بيريك. كروبا، الكسندر؛ مونتغمري، بيتر L.؛ أوسفيك، داج آرني؛ تي رييل ، هيرمان جيه جيه ؛ تيموفيف، أندريه؛ زيمرمان، بول (2010). “تحليل معامل RSA 768 بت” (PDF) . في رابين، تل (محرر). التقدم في علم التشفير - CRYPTO 2010، مؤتمر التشفير السنوي الثلاثين، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 15-19 أغسطس 2010. الإجراءات . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 6223. سبرينغر. ص 333 – 350. دوى : 10.1007 / 978-3-642-14623-7_18 . رقم ISBN 978-3-642-14622-0.
↑ كرانز، ستيفن ج. (2011)، الدليل يكمن في التجربة: الطبيعة المتغيرة للبرهان الرياضي ، نيويورك: سبرينغر، ص 203، doi : 10.1007/978-0-387-48744-1 ، ISBN 978-0-387-48908-7MR 2789493
↑ أرورا، سانجيف ؛ باراك، بواز (2009)، التعقيد الحسابي ، كامبريدج: مطبعة جامعة كامبريدج، ص 230، doi : 10.1017/CBO9780511804090 ، ISBN 978-0-521-42426-4، MR 2500087 ، S2CID 215746906
↑ بوهلر، جيه بي؛ لينسترا، إتش دبليو جونيور؛ بوميرانس، كارل (1993). "تحليل الأعداد الصحيحة باستخدام غربال حقل الأعداد". تطوير غربال حقل الأعداد . سلسلة محاضرات في الرياضيات. المجلد 1554. سبرينغر. الصفحات 50-94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4تم الاطلاع عليه بتاريخ 12 مارس 2021 .
↑ فاندرسايبن، ليفين إم كيه، وآخرون (2001). "التطبيق التجريبي لخوارزمية شور للتحليل الكمي باستخدام الرنين المغناطيسي النووي". مجلة نيتشر . 414 (6866): 883-887 . arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID: 11780055. S2CID : 4400832 .
↑ لانس فورتناو (2002-09-13). "مدونة التعقيد الحسابي: درس التعقيد لهذا الأسبوع: التحليل إلى عوامل" .
↑ غولدريتش، أوديد ؛ ويغدرسون، آفي (2008)، "IV.20 التعقيد الحسابي"، في غاورز، تيموثي ؛ بارو-غرين، جون ؛ ليدر، إيمري (محررون)، دليل برينستون للرياضيات ، برينستون، نيو جيرسي: مطبعة جامعة برينستون، ص 575-604 ، ISBN 978-0-691-11880-2MR 2467561 انظر على وجه الخصوص الصفحة 583 .
1 2 ديفيد بريسود وستان واجن (2000). دورة في نظرية الأعداد الحسابية . دار نشر كي كوليدج/سبرينجر. الصفحات 168-169 . ISBN 978-1-930190-10-8.
↑ شنور، كلاوس ب. (1982). "تحليل مُحسَّن وتحسينات على بعض خوارزميات التحليل إلى عوامل" . مجلة الخوارزميات . 3 (2): 101-127 . doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. مؤرشف من الأصل في 24 سبتمبر 2017.
↑ سيسن، مارتن (1987). "خوارزمية تحليل احتمالية مع أشكال تربيعية للمميز السالب" . رياضيات الحساب . 48 (178): 757-780 . doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .
↑ لينسترا، أرجين ك (1988). "التحليل السريع والدقيق في ظل فرضية ريمان المعممة" (ملف PDF) . Indagationes Mathematicae . 50 (4): 443–454 . doi : 10.1016/S1385-7258(88)80022-2 .
لينسترا ، إتش دبليو ؛ بوميرانس، كارل (يوليو 1992). "حد زمني دقيق لتحليل الأعداد الصحيحة" (ملف PDF) . مجلة الجمعية الرياضية الأمريكية . 5 (3): 483-516 . doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

مراجع

ريتشارد كراندال وكارل بوميرانس (2001). الأعداد الأولية: منظور حسابي . سبرينغر. ISBN 0-387-94777-9.الفصل الخامس: خوارزميات التحليل إلى العوامل الأسية، الصفحات 191-226. الفصل السادس: خوارزميات التحليل إلى العوامل شبه الأسية، الصفحات 227-284. القسم 7.4: طريقة المنحنى الإهليلجي، الصفحات 301-313.
دونالد كنوث . فن برمجة الحاسوب ، المجلد الثاني: الخوارزميات شبه العددية ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89684-2القسم 4.5.4: التحليل إلى الأعداد الأولية، الصفحات 379-417.
صموئيل س. واغستاف الابن (2013). متعة التحليل إلى عوامل . بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات. ISBN 978-1-4704-1048-3..
وارن، هنري س. الابن (2013). متعة المخترق ( الطبعة الثانية). أديسون ويسلي - بيرسون للتعليم، المحدودة. رقم ISBN 978-0-321-84268-8.

روابط خارجية

ساعدت msieve – SIQS و NFS – في إكمال بعض من أكبر عمليات التحليل العام المعروفة
ريتشارد ب. برنت، "التقدم الأخير وآفاق خوارزميات تحليل الأعداد الصحيحة إلى عواملها الأولية"، الحوسبة والتوافقية ، 2000، الصفحات 3-22. تحميل
مانيندرا أغراوال ، نيراج كيال، نيتين ساكسينا، "PRIMES موجود في P." حوليات الرياضيات 160(2): 781-793 (2004). نسخة أغسطس 2005 بصيغة PDF
إريك دبليو. وايسشتاين، "تحليل RSA-640" ، أخبار عناوين ماث وورلد ، 8 نوفمبر 2005
حاسبة تحليل الأعداد الصحيحة من داريو ألبيرن – تطبيق ويب لتحليل الأعداد الصحيحة الكبيرة

[1] Lenstra، Arjen K. (2011)، “Integer Factoring”، in van Tilborg، Henk CA؛ Jajodia، Sushil (eds.)، موسوعة التشفير والأمن ، بوسطن: سبرينغر، الصفحات من 611 إلى 618، دوى : 10.1007/978-1-4419-5906-5_455 ، ISBN 978-1-4419-5905-8

[2] " [ Cado-nfs-discuss ] تحليل الأعداد ذات 795 بت واللوغاريتمات المنفصلة" . مؤرشف من الأصل بتاريخ 2019-12-02.

[rsa768-3] كلينجونج ، ثورستن. أوكي، كازومارو؛ فرانكي، ينس؛ لينسترا، آرجين ك.؛ تومي، إيمانويل. بوس، جوبي دبليو؛ جودري، بيريك. كروبا، الكسندر؛ مونتغمري، بيتر L.؛ أوسفيك، داج آرني؛ تي رييل ، هيرمان جيه جيه ؛ تيموفيف، أندريه؛ زيمرمان، بول (2010). “تحليل معامل RSA 768 بت” (PDF) . في رابين، تل (محرر). التقدم في علم التشفير - CRYPTO 2010، مؤتمر التشفير السنوي الثلاثين، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 15-19 أغسطس 2010. الإجراءات . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 6223. سبرينغر. ص 333 – 350. دوى : 10.1007 / 978-3-642-14623-7_18 . رقم ISBN 978-3-642-14622-0.

[4] كرانز، ستيفن ج. (2011)، الدليل يكمن في التجربة: الطبيعة المتغيرة للبرهان الرياضي ، نيويورك: سبرينغر، ص 203، doi : 10.1007/978-0-387-48744-1 ، ISBN 978-0-387-48908-7MR 2789493

[5] أرورا، سانجيف ؛ باراك، بواز (2009)، التعقيد الحسابي ، كامبريدج: مطبعة جامعة كامبريدج، ص 230، doi : 10.1017/CBO9780511804090 ، ISBN 978-0-521-42426-4، MR 2500087 ، S2CID 215746906

[6] بوهلر، جيه بي؛ لينسترا، إتش دبليو جونيور؛ بوميرانس، كارل (1993). "تحليل الأعداد الصحيحة باستخدام غربال حقل الأعداد". تطوير غربال حقل الأعداد . سلسلة محاضرات في الرياضيات. المجلد 1554. سبرينغر. الصفحات 50-94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4تم الاطلاع عليه بتاريخ 12 مارس 2021 .

[7] فاندرسايبن، ليفين إم كيه، وآخرون (2001). "التطبيق التجريبي لخوارزمية شور للتحليل الكمي باستخدام الرنين المغناطيسي النووي". مجلة نيتشر . 414 (6866): 883-887 . arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID: 11780055. S2CID : 4400832 .

[8] لانس فورتناو (2002-09-13). "مدونة التعقيد الحسابي: درس التعقيد لهذا الأسبوع: التحليل إلى عوامل" .

[9] غولدريتش، أوديد ؛ ويغدرسون، آفي (2008)، "IV.20 التعقيد الحسابي"، في غاورز، تيموثي ؛ بارو-غرين، جون ؛ ليدر، إيمري (محررون)، دليل برينستون للرياضيات ، برينستون، نيو جيرسي: مطبعة جامعة برينستون، ص 575-604 ، ISBN 978-0-691-11880-2MR 2467561 انظر على وجه الخصوص الصفحة 583 .

[Bressoud_and_Wagon-10] 1 2 ديفيد بريسود وستان واجن (2000). دورة في نظرية الأعداد الحسابية . دار نشر كي كوليدج/سبرينجر. الصفحات 168-169 . ISBN 978-1-930190-10-8.

[1982-schnorr-11] شنور، كلاوس ب. (1982). "تحليل مُحسَّن وتحسينات على بعض خوارزميات التحليل إلى عوامل" . مجلة الخوارزميات . 3 (2): 101-127 . doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. مؤرشف من الأصل في 24 سبتمبر 2017.

[1987-seysen-12] سيسن، مارتن (1987). "خوارزمية تحليل احتمالية مع أشكال تربيعية للمميز السالب" . رياضيات الحساب . 48 (178): 757-780 . doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .

[1988-lenstra-13] لينسترا، أرجين ك (1988). "التحليل السريع والدقيق في ظل فرضية ريمان المعممة" (ملف PDF) . Indagationes Mathematicae . 50 (4): 443–454 . doi : 10.1016/S1385-7258(88)80022-2 .

[lenstra-pomerance-14] لينسترا ، إتش دبليو ؛ بوميرانس، كارل (يوليو 1992). "حد زمني دقيق لتحليل الأعداد الصحيحة" (ملف PDF) . مجلة الجمعية الرياضية الأمريكية . 5 (3): 483-516 . doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]