كيفية بناء رقم اولي كبير | مجلة كوانتا

الأعداد الأولية هي أشياء صعبة. نتعلم في المدرسة أنها أرقام ليس لها عوامل سوى 1 وأنفسهم ، وأن علماء الرياضيات يعرفون منذ آلاف السنين أن عددًا لا حصر له منهم. لا يبدو أن إنتاج واحد بأمر كما لو كان صعبًا.

و لكنها. إن تكوين أعداد أولية كبيرة بشكل تعسفي أمر معقد بشكل ملحوظ. لديك أساسًا خياران حسابيان ، كلاهما له عيوب. يمكنك استخدام العشوائية والعثور على واحدة من خلال التخمين ، لكن الطريقة غير متسقة - فأنت تخاطر بتوليد أولي مختلف في كل مرة. أو يمكنك استخدام خوارزمية حتمية أكثر موثوقية ، ولكن بتكلفة حسابية باهظة.

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

قال: "لقد وضعوا سلسلة من المحاولات ، حاول كل منهم تكوين عدد أولي بطول مختلف ، وأظهروا أن إحدى المحاولات تعمل". روي أخبر، عالم كمبيوتر نظري في معهد الدراسات المتقدمة ولم يشارك في العمل. "إنه بناء ينتج أوليًا محددًا بشكل حتمي ، ولكنه يسمح لك برمي العملات المعدنية واتخاذ خيارات عشوائية في هذه العملية."

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

بمرور الوقت ، طور الباحثون الأساليب المذكورة أعلاه. إن أبسط طريقة هي التخمين فقط. إذا كنت تريد أولًا مكونًا من 1,000 رقم ، على سبيل المثال ، يمكنك اختيار عدد مكون من 1,000 رقم عشوائيًا ثم التحقق منه. قال: "إذا لم يكن عددًا أوليًا ، يمكنك فقط تجربة واحدة أخرى ، وأخرى ، وهكذا حتى تجد واحدة" راهول سانتانام، عالم كمبيوتر في جامعة أكسفورد ومؤلف مشارك للبحث الجديد. "نظرًا لوجود العديد من الأعداد الأولية ، ستمنحك هذه الخوارزمية بعض الأرقام الأولية ذات الاحتمالية العالية ، بعد عدد صغير نسبيًا من التكرارات." لكن استخدام العشوائية يعني أنك ستحصل على الأرجح على رقم مختلف في كل مرة. قد تكون هذه مشكلة إذا كنت بحاجة إلى الاتساق - إذا كنت تستخدم ، على سبيل المثال ، طريقة تشفير للأمان تعتمد على توفر الأعداد الأولية الكبيرة.

النهج الآخر هو اتباع خوارزمية حتمية. يمكنك اختيار نقطة البداية والبدء في اختبار الأرقام ، بالتتابع ، من أجل البدائية. في النهاية ، من المقرر أن تجد واحدة ، وستخرج الخوارزمية الخاصة بك باستمرار أول خوارزمية تجدها. لكن قد يستغرق الأمر بعض الوقت: إذا كنت تبحث عن عدد أولي مكون من 1,000 رقم ، حتى لو كنت تبحث عن عدد أولي مكون من 2 رقم⁵⁰⁰ الخطوات - التي تستغرق وقتًا أطول بكثير من عمر الكون - ليست كافية لضمان النجاح.

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

يُعرف هذا الحد الزمني بالزمن متعدد الحدود. تحل الخوارزمية مشكلة في وقت كثير الحدود إذا كان عدد الخطوات التي تتخذها ليس أكثر من دالة متعددة الحدود n، حجم المدخلات. (تتضمن الدالة كثيرة الحدود المصطلحات التي لها متغيرات مرفوعة إلى قوى صحيحة موجبة ، مثل n² أو 4n³.) في سياق بناء العدد الأولي ، n يشير إلى عدد الأرقام في البداية التي تريدها. من الناحية الحسابية ، هذا لا يكلف الكثير: يصف علماء الكمبيوتر المشكلات التي يمكن حلها بواسطة الخوارزميات في وقت متعدد الحدود على أنها سهلة. على النقيض من ذلك ، تستغرق المشكلة الصعبة وقتًا أسيًا ، مما يعني أنها تتطلب عددًا من الخطوات تقربها دالة أسية (والتي تتضمن مصطلحات مثل 2ⁿ).

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

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

منذ ذلك الحين ، كان الباحثون يستكشفون خوارزميات التحديد الكاذب. في عام 2017 ، سانتانام وإيجور أوليفيرا من جامعة وارويك (الذين ساهموا أيضًا في العمل الجديد) وصف مقاربة حتمية زائفة لبناء الأعداد الأولية التي تستخدم العشوائية وبدت حتمية بشكل مقنع ، لكنها عملت في زمن "أسي جزئي" - أسرع من الأسي ، ولكن أبطأ من الوقت متعدد الحدود. ثم في عام 2021 ، أخبر و ليجي تشين، عالم كمبيوتر في جامعة كاليفورنيا ، بيركلي ، استكشاف كيفية استخدام مشكلة صعبة لبناء مولد رقم شبه عشوائي (خوارزمية تولد سلسلة من الأرقام لا يمكن تمييزها عن الناتج العشوائي). قال تشين: "وجدنا علاقة جديدة بين الصلابة والعشوائية الزائفة".

اجتمعت القطع أخيرًا في ربيع عام 2023 ، خلال معسكر تدريب على التعقيد الحسابي في معهد سيمونز لنظرية الحوسبة في بيركلي ، عندما بدأ الباحثون العمل معًا لحل المشكلة ، ونسجوا معًا النتائج السابقة. بالنسبة للعمل الجديد ، قال تشين ، هانلين رين - عالِم الكمبيوتر في أكسفورد ومؤلف مشارك - لديه الأفكار الأولية لدمج نتيجة Chen-Tell مع نهج Santhanam-Oliveira بطريقة جديدة. ثم طور الفريق بأكمله الأفكار بشكل كامل لإنتاج الورقة الجديدة.

قال سانتانام إن خوارزمية التحديد الكاذب الناتجة استخدمت طرقًا جديدة للنظر في العمل السابق لإنتاج الأعداد الأولية في وقت متعدد الحدود. لقد استخدمت العشوائية لإخراج عدد أولي بطول معين ، والأداة أكثر دقة من التخمين العشوائي وأكثر كفاءة من الناحية الحسابية من الطحن الحتمي.

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

قال غروسمان: "سيكون من الرائع التخلص من هذا التحذير الصغير".

قال سانتانام إن الهدف النهائي هو إيجاد خوارزمية لا تتطلب العشوائية على الإطلاق. لكن هذا المسعى لا يزال مفتوحًا. قال "الحتمية هي ما نرغب في استخدامه".

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

قال تيل: "من المثير أن نحاول التفكير في أي مكان آخر ستؤدي إليه هذه الملاحظات الرائعة".