تعداد الأعداد الأولية الكبيرة (المكونة من 20 رقمًا) [المحتملة]

Question

بالنظر إلى A، في حدود 10^20، أود الحصول سريعًا على قائمة بالأعداد الأولية القليلة الأولى الأكبر من A.حسنًا، احتياجاتي ليست دقيقة تمامًا - فلا بأس إذا انتهى الأمر أحيانًا برقم مركب في القائمة.

ما هي أسرع طريقة لتعداد الأعداد الأولية (المحتملة) الأكبر من A؟

هل هناك طريقة أسرع من المرور عبر جميع الأعداد الصحيحة الأكبر من A (بخلاف المضاعفات الواضحة مثل 2 و3) وإجراء اختبار الأولية لكل منها؟إذا لم يكن الأمر كذلك، والطريقة الوحيدة هي اختبار كل عدد صحيح، ما هو اختبار البدائية الذي يجب أن أستخدمه؟

Answer 1

سؤال عظيم. لم يثبت هذا أنه في وقت متعدد الحدود (متعدد الحدود في عدد الأرقام ، هنا 20) - كان هذا هو العثور على الأعداد الأولية Polymath Project ، حيث حاول العديد من علماء الرياضيات (بما في ذلك ميداليات الحقول تيرينس تاو وتيم جويرز! التوصل إلى خوارزمية ، لكن يبدو أن المشروع لم يكن له أي نتائج ملموسة حتى الآن.

على أي حال ، هناك العديد من الأشياء التي يمكنك القيام بها. واحد منهم ، كما أشار أنت والآخرون ، هو جرب كل رقم وتحقق مما إذا كان ذلك رئيسيًا ، مع اختبار البدائية السريع مثل ميلر -رابين. حسب العدد المعروف عن الاستدلال النظري (استنادًا إلى نظرية العدد الرئيسي) ، "احتمال" رقم بالقرب من كونه prime هو حوالي 1/ln (n) ، لذلك مع 10^20 ، حوالي في كل 46 أرقام سيكون prime. لذا ، إذا كنت تريد أرقام K من رقم 20 ، فستقوم بتشغيل اختبار Miller-Rabin على حوالي 50 ألف رقم.

النهج الثاني ، الذي أنا فكر في قد يكون أسرع إذا كنت تفعل هذا للعديد من A (لم تفكر بعناية) هو استخدام أ غربال, ، مثل ال غربال eratosthenes. إذا كنت تريد k الأعداد الأولية ، فقم بعمل صفيف بحوالي 50 ألفًا (أو أكثر ليكون آمنًا) ، والخلاب من خلالها. ستبدأ بقائمة مسبقة من الأعداد الأولية أقل من بعض الأرقام. (10¹⁰ لكي تكون صحيحًا تمامًا ، ولكن نظرًا لأنك على استعداد للتسامح أول 50 مليون برامز, ، يضمن أن أرقامك ليس لها عوامل رئيسية أقل من 982،451،653 ، وليس هناك الكثير منها.)

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

Answer 2

هل هناك طريقة أسرع من التجول في جميع الأعداد الصحيحة أكبر من (بخلاف المضاعفات الواضحة من القول ، 2 و 3) وإجراء اختبار البدائية لكل منهم؟

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

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

Answer 3

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

Answer 4

الأعداد الأولية هي أعداد متكررة هادئة.تردد الأعداد الأولية هو log(n) وهذا يعني أنه في المتوسط ​​كل رقم 46 هو أولي حيث n=10^20.وهذا يعني أن التحقق من كل رقم للأولوية ليس من هذا القبيل.