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

'''اختبار ميلر ورابين لأولية عدد ما''' {{إنج|Miller–Rabin primality test}} هو [[اختبار أولية عدد ما|اختبار]] احتمالي لمعرفة إذا ما كان [[عدد أولي|العدد أوليّاً]]: وهو [[خوارزمية]] تحدد فيما إذا كان العدد المعطى من [[عدد أولي محتمل|المحتمل أن يكون أوليًا]] ، على غرار [[اختبار فيرما لأولية عدد ما|اختبار فيرمات لأولية عدد ما]] [[اختبار سولوفاي - ستراسن البدائية|واختبار سولوفاي-ستراسن لأولية عدد ما]].

لهذا الاختبار أهمية تاريخية في البحث عن اختبار الأولية الحتمية في مجال [[تعقيد الوقت]]، حيث لا يزال متغيره الاحتمالي مستخدمًا على نطاق واسع في الممارسة، كواحد من أبسط وأسرع الاختبارات المعروفة. اقترح {{وإو|لغ=EN|تر=Gary Miller (computer scientist)|عر=غاري ميلر (عالم حاسوب)|نص=غاري ميلر}} هذا الاختبار عام 1976، نسخة ميلر من اختبار [[خوارزمية حتمية|الحتمية]]، لكن صحتها تعتمد على [[فرضية ريمان المعممة]] غير المثبتة.<ref name="miller">{{استشهاد|الأخير=Miller|الأول=Gary L.|سنة=1976|عنوان=Riemann's Hypothesis and Tests for Primality|مؤلف-وصلة=Gary Miller (computer scientist)|صحيفة=Journal of Computer and System Sciences|المجلد=13|العدد=3|صفحات=300–317|DOI=10.1145/800116.803773}}</ref> عدلها [[مايكل رابين]] للحصول على [[خوارزمية عشوائية]] غير مشروطة عام 1980.

<ref name="rabin">{{استشهاد|الأخير=Rabin|الأول=Michael O.|سنة=1980|عنوان=Probabilistic algorithm for testing primality|مؤلف-وصلة=Michael O. Rabin|صحيفة=Journal of Number Theory|المجلد=12|العدد=1|صفحات=128–138|DOI=10.1016/0022-314X(80)90084-0}}</ref>


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

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

=== الأعداد الأولية القوية المحتملة ===
بنية الخوارزمية هي: بالنسبة إلى عدد صحيح فردي معين {{بدون لف|''n'' > 2}} ، لنكتب ''n'' في صورة {{بدون لف|2<sup>''s''</sup>⋅''d'' + 1}} حيث ''s'' و ''d'' عددان صحيحان موجبان و ''d'' عدد فردي. لنفكر في عدد صحيح ''a''، يسمى القاعدة، يحقق {{بدون لف|0 < ''a'' > ''n''}} . بعد ذلك، يعتبر العدد ''n'' عدداً '''[[عدد أولي محتمل|أولياً محتملاً]]''' للقاعدة ''a'' إذا كانت إحدى [[حسابيات معيارية|علاقات التطابق]] هذه صحيحة:
<div style="direction: ltr">
* <math>a^{d} \equiv 1 \pmod{n}</math> ؛
* <math>a^{2^r\cdot d} \equiv -1 \pmod{n}</math> {{بدون لف|0≤ r <s}} .
</div>

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

* من خلال [[مبرهنة فيرما الصغرى]]، <math>a^{n-1} \equiv 1 \pmod{n}</math> (تحدد هذه الخاصية وحدها المفهوم الأضعف ''للقيمة الأولية المحتملة للقاعدة a'' ، والتي يعتمد عليها اختبار فيرما).
* باقي [[باق تربيعي|الجذور التربيعية]] الوحيدة لـ1 مع باقي القسمة للعدد n هي 1 و -1.

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

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

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

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



== مثال ==
== مراجع ==
{{مراجع}}

{{خوارزميات نظرية الأعداد}}
{{شريط بوابات|تعمية|علم الحاسوب|نظرية الأعداد}}

[[تصنيف:اختبارات أولية العدد]]
[[تصنيف:حقول منتهية]]