مرجع
آخر الزيارات

اختبار ميلر ورابين لأولية عدد ما

575 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: اختبار ميلر ورابين لأولية عدد ما هو اختبار احتمالي لمعرفة إذا ما كان العدد أوليّاً: وهو خوارزمية تحدد فيما إذا كان العدد المعطى من المحتمل أن يكون أوليًا ، على غرار اختبار فيرمات لأولية عدد ما واختبار سولوفاي-ستراسن لأولية عدد ما. تجد هنا «الأعداد الأولية القوية المحتملة»، «المفهوم الرياضي» و«اختيار القواعد».
المحتويات
  1. الأعداد الأولية القوية المحتملة
  2. المفهوم الرياضي
  3. اختيار القواعد

بدايةً، اختبار ميلر ورابين لأولية عدد ما هو اختبار احتمالي لمعرفة إذا ما كان العدد أوليّاً: وهو خوارزمية تحدد فيما إذا كان العدد المعطى من المحتمل أن يكون أوليًا ، على غرار اختبار فيرمات لأولية عدد ما واختبار سولوفاي-ستراسن لأولية عدد ما. وفيما يلي تفاصيل أوسع عن ذلك.

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

الأعداد الأولية القوية المحتملة

من جانب آخر، الفكرة الكامنة وراء هذا الاختبار هي أنه عندما يكون n عددًا أوليًا فردياً، فإنه يجتاز الاختبار لوجود حقيقتين:

علاوةً على ذلك، من خلال مبرهنة فيرما الصغرى، (تحدد هذه الخاصية وحدها المفهوم الأضعف للقيمة الأولية المحتملة للقاعدة a ، والتي يعتمد عليها اختبار فيرما).

؛

من جانب آخر، بنية الخوارزمية هي: بالنسبة إلى عدد صحيح فردي معين ، لنكتب n في صورة حيث s و d عددان صحيحان موجبان و d عدد فردي. لنفكر في عدد صحيح a، يسمى القاعدة، يحقق . لاحقًا، يعتبر العدد n عدداً أولياً محتملاً للقاعدة a إذا كانت إحدى علاقات التطابق هذه صحيحة:

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

.

إضافةً إلى ذلك، باقي الجذور التربيعية الوحيدة لـ1 مع باقي القسمة للعدد n هي 1 و -1.

المفهوم الرياضي

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

اختيار القواعد

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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