غربال حقل الأرقام العام

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 12 صور
الموسوعة الحرة

في نظرية الأعداد ، يُعد غربال حقل الأعداد العام ( GNFS ) أكثر الخوارزميات الكلاسيكية كفاءةً لتحليل الأعداد الصحيحة الأكبر من 10 ^100 . وبشكل تقريبي ، فإن تعقيده لتحليل عدد صحيح n (يتكون من ⌊log 2 n ⌋ + 1 بت) يكون على الشكل التالي:

خبرة⁡(((64/9)1/3+o(1))(سجل⁡ن)1/3(سجل⁡سجل⁡ن)2/3)=لن[1/3،(64/9)1/3]{\displaystyle {\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{aligned}}}

في ترميز Big-O و L. [ 1 ] إنه تعميم لغربال حقل الأعداد الخاص : في حين أن الأخير لا يمكنه تحليل الأعداد إلا من شكل خاص معين، فإن غربال حقل الأعداد العام يمكنه تحليل أي عدد باستثناء القوى الأولية (التي يسهل تحليلها عن طريق أخذ الجذور).

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

حجم مُدخلات الخوارزمية هو log₂ n  أو عدد البتات في التمثيل الثنائي لـ n . أي عنصر من الرتبة n c ، حيث c ثابت، يكون أُسّيًا بالنسبة إلى log₂ n  . زمن تشغيل غربال حقل الأعداد هو زمن فائق متعدد الحدود ولكنه دون أُسّي بالنسبة إلى حجم المُدخلات.

حقول الأرقام

لنفترض أن f هي متعددة حدود من الدرجة k علىسؤال{\textstyle \mathbb {Q} }(الأعداد النسبية)، و r جذر مركب للدالة f . عندئذٍ، f ( r )  =  0 ، والتي يمكن إعادة ترتيبها للتعبير عن rk كمزيج خطي من قوى r الأقل من k . يمكن استخدام هذه المعادلة لاختزال أي قوى لـ r ذات أس e ≥ k . على سبيل المثال، إذا كانت f ( x ) = x² + 1 و r هي الوحدة التخيلية i ، فإن i² + 1 = 0 ، أو i² = -1 . وهذا يسمح لنا بتعريف الضرب المركب :          

(أ+بأنا)(ج+دأنا)=أج+(أد+بج)أنا+(بد)أنا2=(أج-بد)+(أد+بج)أنا.{\displaystyle {\begin{aligned}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+(ad+bc)i.\end{aligned}}}

بشكل عام، يؤدي هذا مباشرة إلى حقل الأعداد الجبريةسؤال[ر]{\textstyle \mathbb {Q} [r]}والتي يمكن تعريفها بأنها مجموعة الأعداد المركبة المعطاة بالصيغة التالية:

أك-1رك-1+⋯+أ1ر1+أ0ر0، أين أ0،...،أك-1∈سؤال.{\displaystyle a_{k-1}r^{k-1}+\cdots +a_{1}r^{1}+a_{0}r^{0},{\text{ حيث }}a_{0},\ldots ,a_{k-1}\in \mathbb {Q} .}

يمكن حساب حاصل ضرب أي قيمتين من هذا النوع بأخذ حاصل الضرب على شكل كثيرات حدود، ثم اختزال أي قوى لـ r ذات أس e ≥ k كما هو موضح أعلاه، مما ينتج عنه قيمة بنفس الشكل. ولضمان أن هذا الحقل ذو بُعد k بالفعل ولا ينهار إلى حقل أصغر، يكفي أن تكون f كثيرة حدود غير قابلة للاختزال على الأعداد النسبية. وبالمثل، يمكن تعريف حلقة الأعداد الصحيحة.ياسؤال[ر]{\textstyle \mathbb {O} _{\mathbb {Q} [r]}}باعتبارها مجموعة فرعية منسؤال[ر]{\textstyle \mathbb {Q} [r]}وهي جذور لكثيرات الحدود أحادية المعامل ذات المعاملات الصحيحة. في بعض الحالات، تكون حلقة الأعداد الصحيحة هذه مكافئة للحلقةZ[ر]{\textstyle \mathbb {Z} [r]}ومع ذلك، هناك العديد من الاستثناءات. [ 2 ]

طريقة

الاختيار متعدد الحدود

تم اختيار كثيرتي حدود f ( x ) و g ( x ) من درجتين صغيرتين d و e ، بمعاملات صحيحة، وغير قابلة للاختزال على الأعداد النسبية ، ولها جذر صحيح مشترك m عند تفسيرها modulo n . لا توجد استراتيجية مثلى لاختيار هاتين الكثيرتي الحدود؛ إحدى الطرق البسيطة هي الحصول على f من توسيع n في النظام ذي الأساس m لاختيار مناسب لـ m . بتعبير أدق: لأي اختيار لـ m ، فإن كتابة n في النظام ذي الأساس m هي، بحكم التعريف، إيجاد أرقامأ0،أ1،...،أد{\textstyle a_{0},a_{1},\ldots ,a_{d}}أين0≤أأنا<م{\textstyle 0\leq a_{i}<m}لكل i ، بحيث

ن=أدمد+⋯+أ1م+أ0{\displaystyle n=a_{d}m^{d}+\cdots +a_{1}m+a_{0}}،

وهذا بدوره يعني أن m هو جذر لكثير الحدودو(x)=أدxد+⋯+أ1x+أ0{\textstyle f(x)=a_{d}x^{d}+\cdots +a_{1}x+a_{0}}modulo n . لأغراض غربلة حقل الأعداد العامة، نحدد أولاً درجة مناسبة d ، ثم نجري التوسع المذكور أعلاه لعدد من القيم m من الرتبة n 1/ d ، وبعد ذلك نختار متعددة الحدود f لتكون تلك التي تكون معاملاتها أصغر ما يمكن بين المرشحين الذين تم الحصول عليهم بهذه الطريقة. ثم نضع ببساطةز(x)=x-م{\textstyle g(x)=xm}.

تحسين اختيار كثيرات الحدود

يُمكن أن يؤثر اختيار كثير الحدود بشكل كبير على الوقت اللازم لإكمال ما تبقى من الخوارزمية. إن طريقة اختيار كثيرات الحدود بناءً على توسيع n في الأساس m الموضحة أعلاه ليست مثالية في العديد من الحالات العملية، مما أدى إلى تطوير طرق أفضل.

اقترح مورفي وبرينت إحدى هذه الطرق؛ [ 3 ] يقدمون درجة من جزأين لكثيرات الحدود، بناءً على وجود الجذور modulo الأعداد الأولية الصغيرة وعلى القيمة المتوسطة التي تأخذها كثيرة الحدود على منطقة الغربلة.

تم تحقيق أفضل النتائج المبلغ عنها [ 4 ] بواسطة طريقة ثورستن كلاينجونج ، [ 5 ] والتي تسمح بـ g ( x ) = ax  + b  ، والبحث على a مكونة من عوامل أولية صغيرة متطابقة مع 1 modulo 2d وعلى المعاملات الرئيسية لـ f التي تقبل القسمة على 60.

توليد أزواج العلاقات (الغربلة)

لنفترض حلقتي حقل الأعداد Z [ r1 ] و Z [ r2 ] ، حيث r1 و r2 هما جذرا كثيرتي الحدود f و g . بما أن f من الدرجة d بمعاملات صحيحة، فإذا كان a و b عددين صحيحين ، فإن b = d · f ( a / b ) سيكون كذلك ، وهو ما نسميه r . وبالمثل، s = be · g ( a / b ) عدد صحيح. الهدف هو إيجاد قيم صحيحة لـ a و b تجعل r و s سلستين في آن واحد بالنسبة لقاعدة الأعداد الأولية المختارة. إذا كانت a و b صغيرتين، فإن r و s ستكونان صغيرتين أيضًا، بحجم m تقريبًا ، وبالتالي تزداد احتمالية أن تكونا سلسلتين في الوقت نفسه. أفضل طريقة معروفة حاليًا لهذا البحث هي غربلة الشبكة ؛ وللحصول على نتائج مقبولة، من الضروري استخدام قاعدة عوامل كبيرة. تُسمى هذه الأزواج أيضًا "علاقات". [ 6 ]

المعالجة اللاحقة

بوجود عدد كافٍ من هذه الأزواج، وباستخدام طريقة الحذف الغاوسي ، يمكن الحصول على حاصل ضرب قيم معينة لـ r وحاصل ضرب القيم المناظرة لها s ، بحيث تكون مربعات في الوقت نفسه. يلزم شرط أقوى قليلاً، وهو أن تكون هذه القيم معايير مربعات في حقول الأعداد لدينا، ولكن يمكن تحقيق هذا الشرط بهذه الطريقة أيضًا. كل قيمة r هي معيار لـ a  − r 1 b ، وبالتالي فإن حاصل ضرب العوامل المناظرة a − r 1 b هو مربع في Z [ r 1 ]، وله "جذر تربيعي" يمكن تحديده (كحاصل ضرب عوامل معروفة في Z [ r 1 ])، وعادةً ما يُعبَّر عنه بعدد جبري غير نسبي . وبالمثل، فإن حاصل ضرب العوامل a − r 2 b هو مربع في Z [ r 2 ]، وله "جذر تربيعي" يمكن حسابه أيضًا. تجدر الإشارة إلى أن استخدام طريقة الحذف الغاوسي لا يُعطي الوقت الأمثل لتشغيل الخوارزمية. بدلاً من ذلك، يتم استخدام خوارزميات حل المصفوفات المتفرقة مثل Block Lanczos أو Block Wiedemann .     

بما أن m جذر لكل من f و g بتردد n ، توجد تشاكلات من الحلقتين Z [ r1 ] و Z [ r2 ] إلى الحلقة Z / nZ (الأعداد الصحيحة بتردد n )، والتي تربط r1 و r2 بـ m ، وهذه التشاكلات تربط كل "جذر تربيعي" ( الذي لا يُمثَّل عادةً كعدد نسبي) بممثله الصحيح. الآن، يمكن الحصول على حاصل ضرب العوامل a − mb بتردد n كمربع بطريقتين - واحدة لكل تشاكل. بالتالي، يمكن إيجاد عددين x و y ، بحيث يكون x² − y² قابلاً للقسمة على n، ومرة ​​أخرى ، باحتمالية لا تقل عن النصف، نحصل على عامل من عوامل n بإيجاد القاسم المشترك الأكبر لـ n و x − y .      

تتضمن خطوة المعالجة اللاحقة كميات كبيرة من البيانات الناتجة عن الخطوتين السابقتين. ويتم ذلك عمليًا بتقسيمها إلى ثلاث مراحل: [ 6 ]

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

الحوسبة الموزعة

تتطلب خوارزمية GNFS كميات هائلة من الحوسبة، وتستلزم شكلاً من أشكال الحوسبة الموزعة لإتمامها ضمن أطر زمنية عملية، خاصةً مع الأعداد الكبيرة مثل RSA-768 . يمكن تنفيذ الخطوات التالية بالتوازي: [ 7 ]

  • عملية الفرز، التي قد تُنتج علاقات مكررة وتتطلب كميات هائلة من الحسابات.
  • إزالة العلاقات المكررة، وإزالة العلاقات الفردية
  • الجبر الخطي، الذي يتطلب كميات هائلة من العمليات الحسابية

يمكن تطبيق اختبار الخاصية التربيعية على نتائج حل المصفوفات لتحديد الحلول الصحيحة. في حالة RSA-768، كانت 460 من أصل 512 حلاً صحيحة. تم اختيار ثمانية منها لخطوة التربيع، مما أدى إلى إنتاج 5 تحليلات متطابقة في الخطوة النهائية بعد قدر ضئيل نسبيًا من العمليات الحسابية. [ 7 ]

يمكن الاطلاع على وصف أكثر تفصيلاً للجهود الموزعة لـ RSA-240 وDLP-240 وRSA-250، باستخدام برنامج CADO-NFS. تتوفر ملفات إعادة الإنتاج الكاملة في مستودع مرتبط بملحق الورقة البحثية. [ 8 ]

التطبيقات

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

حتى عام 2007، كان المعيار الذهبي للتنفيذ عبارة عن مجموعة برامج طورتها ووزعتها شركة CWI في هولندا، وكانت متاحة فقط بموجب ترخيص مقيد نسبيًا. في عام 2007، طور جيسون بابادوبولوس تنفيذًا أسرع للمعالجة النهائية كجزء من برنامج msieve، وهو متاح للاستخدام العام. يتميز كلا التنفيذين بإمكانية توزيعهما على عدة عُقد في مجموعة حاسوبية ذات اتصال سريع كافٍ.

  • برنامج GGNFS (مرخص بموجب رخصة جنو العمومية العامة) من تطوير كريس مونيكو، آخر تحديث عام ٢٠٠٥. يُمكنه تنفيذ جميع الخطوات. يدعم حوالي ١٦٠ رقمًا لـ SNFS و١٣٥ رقمًا لـ GNFS. يتضمن هذه الأجزاء أيضًا بموجب رخصة جنو العمومية العامة:
    • pol5: اختيار متعدد الحدود بواسطة كلاينجونج 2005
    • lasieve4: الغربلة الشبكية بواسطة فرانكي وكلينجونج 2001 – 2004
  • عامل بواسطة gnfs ، كود C++ بواسطة كريس ديبونا وكريس كارد، آخر تحديث 2024. GNU GPL.
  • CADO-NFS ، تطبيق بلغة C/C++ لجميع الخطوات من قِبل فريق كبير في INRIA . آخر تحديث 2025 (اعتبارًا من 2025). رخصة جنو العمومية العامة المحدودة (GNU LGPL).
  • msieve . يحتوي على كود المعالجة النهائية، واختيار متعدد الحدود مُحسَّن للأعداد الصغيرة، وتنفيذ لغربال الخط. المجال العام.
  • kmGNFS . التنفيذ الأساسي لجميع الخطوات بواسطة كريستوس باكوجيانيس ونيكولاوس كارابانوس، آخر تحديث 2009.
  • يافو . تنفيذ جميع الخطوات بواسطة بن بوهرو. آخر تحديث 2025 (اعتبارًا من 2025). ملكية عامة.

الحوسبة التطوعية

استمر مشروع يُدعى NFSNET من عام 2002 [ 9 ] وحتى عام 2007 على الأقل. وقد اعتمد على الحوسبة الموزعة التطوعية عبر الإنترنت . [ 10 ] وشارك فيه كل من بول ليلاند من المملكة المتحدة وريتشارد واكربارث من تكساس. [ 11 ]

لا تزال محاولة أحدث تُسمى NFS@Home قيد التشغيل حتى سبتمبر 2025. وقد استخدمت تاريخيًا نسخًا معدلة من msieve. وهي تستخدم عمومًا مناخل حقول أرقام خاصة.

ملحوظات

  1. ↑ بوميرانس، كارل (ديسمبر 1996). "حكاية غربالين" (ملف PDF) . إشعارات الجمعية الأمريكية للرياضيات . المجلد  43، العدد  12. الصفحات 1473-1485 . 
  2. ↑ ريبنبوم، باولو (1972). الأعداد الجبرية . وايلي-إنترساينس. ISBN 978-0-471-71804-8.
  3. ↑ مورفي ، ب.؛ برنت، ر.ب. (1998)، "حول كثيرات الحدود التربيعية لغربال حقل الأعداد" ، اتصالات علوم الحاسوب الأسترالية ، 20 : 199-213
  4. ↑ فرانك، ينس (2006)، حول RSA 200 والمشاريع الأكبر حجماً (PDF)
  5. ↑ كلاينجونج، ثورستن (أكتوبر 2006). "حول اختيار كثير الحدود لغربال حقل الأعداد العام" (ملف PDF) . رياضيات الحساب . 75 (256): 2037-2047 . Bibcode : 2006MaCom..75.2037K . doi : 10.1090/S0025-5718-06-01870-9 . تاريخ الاسترجاع: 13 ديسمبر 2007 .
  6. 1 2 "readme.nfs from msieve" .
  7. 1 2 "يسرنا أن نعلن عن تحليل RSA768، وهو الرقم التالي المكون من 768 بت و232 رقمًا من قائمة تحديات RSA:" .
  8. ↑ F. Boudot et al, “مقارنة صعوبة التحليل واللوغاريتم المنفصل: تجربة مكونة من 240 رقمًا,” 10 يونيو 2020.
  9. ↑ بول ليلاند (12 ديسمبر 2003). "شبكة NFSNET: السنة الأولى" . عرض تقديمي في ورشة عمل EIDMA-CWI حول تحليل الأعداد الكبيرة . تم الاطلاع عليه في 9 أغسطس 2011 .
  10. ↑ "مرحباً بكم في NFSNET" . 23 أبريل 2007. مؤرشف من الأصل في 22 أكتوبر 2007. تم الاطلاع عليه في 9 أغسطس 2011 .
  11. ↑ "حول NFSNET" . مؤرشف من الأصل في 9 مايو 2008. تم الاطلاع عليه في 9 أغسطس 2011 .

مراجع

  • أرجين ك. لينسترا وهـ . و. لينسترا الابن (محرران). "تطور غربال حقل الأعداد". سلسلة محاضرات في الرياضيات (1993) 1554. سبرينغر-فيرلاغ.
  • ريتشارد كراندال وكارل بوميرانس . الأعداد الأولية: منظور حسابي (2001). الطبعة الثانية، سبرينغر. ISBN 0-387-25282-7القسم 6.2: غربال حقل الأرقام، الصفحات  278-301.
  • ماثيو إي. بريغز: مقدمة إلى منخل حقل الأعداد العام، 1998