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

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

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

اكتشف غاري ل. ميلر الاختبار عام 1976. نسخة ميلر من الاختبار حتمية ، لكن صحتها تعتمد على فرضية ريمان الموسعة غير المثبتة . ^{[ 1 ]} عدّل مايكل أو. رابين الاختبار عام 1980 للحصول على خوارزمية احتمالية غير مشروطة. ^{[ 2 ]}^{[ أ ]}

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

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

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

الخاصية هي التالية. بالنسبة لعدد صحيح فردي معين $n>2$ لنكتب $n-1$ مثل $2^{s}d$ أين $s$ هو عدد صحيح موجب و $d$ هو عدد صحيح موجب فردي. لنفترض عددًا صحيحًا $a$ ، ويسمى أساسًا ، وهو عدد أولي نسبيًا لـ $n$ . ثم، $n$ يُقال إنه عدد أولي قوي محتمل كأساس إذا تحققت إحدى علاقات التطابق هذه:

$a^{d}\equiv 1\!\!\!{\pmod {n}}$ ، أو
$a^{2^{r}d}\equiv -1\!\!\!{\pmod {n}}$ بالنسبة للبعض $0\leq r<s$ .

هذا يتبسط إلى التحقق أولاً من $a^{d}\equiv 1{\pmod {n}}$ وثم $a^{2^{r}d}\equiv n-1{\pmod {n}}$ للقيم المتتالية لـ $r$ لكل قيمة من $r$ يمكن حساب قيمة التعبير باستخدام القيمة التي تم الحصول عليها للقيمة السابقة لـ $r$ عن طريق التربيع تحت معيار $n$ .

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

بحسب نظرية فيرما الصغرى ، $a^{n-1}\equiv 1{\pmod {n}}$ (هذه الخاصية وحدها تحدد المفهوم الأضعف للعدد الأولي المحتمل للأساس $a$ ، والتي يستند إليها اختبار فيرما)؛
الجذور التربيعية الوحيدة للعدد 1 بتردد صفري $n$ هما 1 و -1.

وبالتالي، بالاستدلال العكسي ، إذا $n$ ليس احتمالًا قويًا لعدد أولي أساسي $a$ ، ثم $n$ هو مركب بالتأكيد، $a$ يُطلق عليه شاهد على تركيب $n$ .

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

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

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

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

لاحظ أن $العلاقة$ $a \equiv 1 (mod n)$ صحيحة بشكل بديهي عندما يكون $a$ $\equiv 1 (mod n)$ ، لأن علاقة التطابق متوافقة مع عملية الأسس . كما أن $العلاقة$ $a$ $\equiv -1 (mod n)$ صحيحة بشكل بديهي عندما يكون $a \equiv -1 (mod n)$ لأن $d$ عدد فردي، وللسبب نفسه. لهذا السبب، عادةً ما يتم اختيار قيم عشوائية $لـ$ $a$ ضمن الفترة $1 < a < n - 1$ .

لاختبار قيمة $n$ كبيرة بشكل تعسفي ، يعد اختيار القواعد عشوائيًا أمرًا ضروريًا، لأننا لا نعرف توزيع الشهود والكاذبين القويين بين الأرقام 2، 3، ...، $n -$ 2. ^{[ ب ]}

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

البراهين

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

دليل

بالتأكيد، عند تربيع العددين 1 و -1 بتردد n ، نحصل دائمًا على 1. ويبقى إثبات أنه لا توجد جذور تربيعية أخرى للعدد 1 بتردد n . هذه حالة خاصة، تُطبق هنا على متعددة الحدود X² - 1 على الحقل المنتهي Z / nZ ، من الحقيقة العامة القائلة بأن متعددة الحدود على حقل ^ما لا تحتوي على جذور أكثر من درجتها (تنتج هذه النظرية من وجود قسمة إقليدية لمتعددات الحدود ). فيما يلي برهان أبسط. لنفترض أن x هو جذر تربيعي للعدد 1 بتردد n . إذن:

(x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}}.

بمعنى آخر، يقسم العدد n حاصل ضرب ( x - 1)( x + 1) . وبحسب مبرهنة إقليدس ، ولأن n عدد أولي، فإنه يقسم أحد العاملين x - 1 أو x + 1، مما يعني أن x يطابق إما 1 أو -1 بتردد n .

إليكم برهان على أنه إذا كان n عددًا أوليًا فرديًا، فإنه عدد أولي محتمل قوي ليكون أساسًا لـ a .

دليل

إذا كان n عددًا أوليًا فرديًا، وكتبنا n − 1 = 2 ^s d حيث s عدد صحيح موجب و d عدد صحيح فردي موجب، فبحسب نظرية فيرما الصغرى:

a^{2^{s}d}\equiv 1{\pmod {n}}.

كل حد من حدود المتتالية $a^{2^{s}d},a^{2^{s-1}d},\dots ,a^{2d},a^{d}$ هو الجذر التربيعي للحد السابق. بما أن الحد الأول يطابق 1، فإن الحد الثاني هو الجذر التربيعي لـ 1 بتردد n . وفقًا للنتيجة السابقة ، فهو يطابق إما 1 أو -1 بتردد n . إذا كان يطابق -1، فقد انتهينا. وإلا، فهو يطابق 1 ويمكننا تكرار الاستدلال . في النهاية، إما أن يكون أحد الحدود يطابق -1، أو أن تكون جميعها تطابق 1، وبالتحديد الحد الأخير، a ^d ، كذلك.

مثال

لنفترض أننا نرغب في تحديد ما إذا $n=221$ هو عدد أولي. نكتب $n-1{\text{ as }}2^{2}\times 55$ لذلك لدينا $s=2{\text{ and }}d=55$ نختار رقماً عشوائياً $a$ بحيث $2\leq a\leq n-2$ .

يقول $a=174$ :

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Since }}47\neq 1{\text{ and }}47\neq n-1{\text{, we continue.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}$

منذ $220\equiv -1{\text{ mod }}n$ إما أن يكون العدد 221 عددًا أوليًا، أو أن العدد 174 عدد كاذب قوي بالنسبة للعدد 221. نجرب عددًا عشوائيًا آخر. $a$ ، هذه المرة اختيار $a=137$ :

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}$

لذا، يُعدّ العدد 137 دليلاً على تركيب العدد 221، بينما كان العدد 174 في الواقع عددًا غير متطابق. تجدر الإشارة إلى أن هذا لا يُخبرنا شيئًا عن عوامل العدد 221 (وهي 13 و17). مع ذلك، يُبيّن المثال الذي سيُعرض لاحقًا مع العدد 341 كيف يُمكن لهذه الحسابات أن تُنتج أحيانًا عاملًا من النوع n .

للحصول على دليل عملي لاختيار قيمة a ، انظر الاختبار مقابل مجموعات صغيرة من القواعد .

اختبار ميلر-رابين

يمكن كتابة الخوارزمية بلغة شبه رمزية كما يلي. يحدد المعامل k دقة الاختبار. كلما زاد عدد الجولات، زادت دقة النتيجة. ^{[ 6 ]}

المدخل رقم 1 : n > 2، عدد فردي يُراد اختبار أوليته. المدخل رقم 2 : k ، عدد جولات الاختبار. المخرج : " مركب " إذا كان n مركبًا، " أولي على الأرجح " خلاف ذلك.

ليكن s > 0 و d فردي > 0 بحيث يكون n − 1 = 2 ^s d # باستخراج قوى 2 من n − 1 كرر k مرة : a ← random(2, n − 2) # n دائمًا عدد أولي محتمل للأساس 1 و n − 1 x ← a ^d mod n كرر s مرة : y ← x ² mod n إذا كان y = 1 و x ≠ 1 و x ≠ n − 1 فإن # جذر تربيعي غير تافه للعدد 1 modulo n أرجع " مركب " x ← y إذا كان y ≠ 1 فإن أرجع " مركب " أرجع " عدد أولي محتمل "

تعقيد

باستخدام التربيع المتكرر ، يكون زمن تشغيل هذه الخوارزمية $O (kⁿ³)$ ، لعدد $مكون$ $من$ n خانة، حيث k هو عدد الجولات المُنفذة؛ وبالتالي فهي خوارزمية فعالة ذات زمن متعدد الحدود. يمكن $لعملية$ $الضرب القائمة على تحويل$ فورييه السريع ، مثل خوارزمية شونهاج-ستراسن ، أن تُقلل زمن التشغيل إلى $O (kⁿ² logⁿ log logⁿ) = Õ (kⁿ²) .$

دقة

يُقاس الخطأ في اختبار أولية الأعداد باحتمالية اعتبار عدد مركب أوليًا على الأرجح. كلما زاد عدد القواعد a المُجرَّبة، تحسَّنت دقة الاختبار. يمكن إثبات أنه إذا كان n عددًا مركبًا، فإن ربع القواعد a على الأكثر تُعتبر قواعد خاطئة قوية لـ n . ^[²^]^[⁷^]^[⁸^] ونتيجةً لذلك، إذا كان n عددًا مركبًا ، فإن إجراء k تكرارًا لاختبار ميلر-رابين سيُعلن أن n أولي على الأرجح باحتمالية لا ^تتجاوز4 - k^.

يُعدّ هذا تحسينًا لاختبار سولوفاي-ستراسن ، الذي يبلغ حدّ خطأ أسوأ حالاته 2 ^{− k} . علاوة على ذلك، يُعتبر اختبار ميلر-رابين أقوى من اختبار سولوفاي-ستراسن من حيث أنه لكل عدد مركب n ، فإن مجموعة الكاذبين الأقوياء لـ n هي مجموعة جزئية من مجموعة كاذبي أويلر لـ n ، وبالنسبة للعديد من قيم n ، تكون المجموعة الجزئية صحيحة.

بالإضافة إلى ذلك، بالنسبة للقيم الكبيرة لـ n ، غالبًا ما يكون احتمال اعتبار عدد مركب أوليًا على الأرجح أقل بكثير من 4 ^{- k} . على سبيل المثال، بالنسبة لمعظم الأعداد n ، يكون هذا الاحتمال محدودًا بـ 8 ^{- k} ؛ وتتلاشى نسبة الأعداد n التي تُبطل هذا الحد الأعلى عند النظر في قيم أكبر لـ n . ^{[ 9 ]} وبالتالي، فإن الحالة المتوسطة تتمتع بدقة أفضل بكثير من 4 ^{- k} ، وهي حقيقة يمكن استغلالها لتوليد أعداد أولية محتملة (انظر أدناه ). ومع ذلك، لا ينبغي الاعتماد على حدود الخطأ المحسّنة هذه للتحقق من الأعداد الأولية التي لا يمكن التحكم في توزيع احتمالاتها ، حيث قد يرسل خصم تشفيري عددًا زائفًا أوليًا مختارًا بعناية لإفشال اختبار أولية العدد. ^{[ ج ]} في مثل هذه السياقات، لا يمكن الاعتماد إلا على حد الخطأ في أسوأ الحالات وهو 4 ^{- k .}

مقياس الخطأ المذكور أعلاه هو احتمال إعلان عدد مركب كعدد أولي قوي الاحتمال بعد k جولة من الاختبار؛ بعبارة رياضية، هو الاحتمال الشرطي $\Pr(M\!R_{k}\mid \lnot P)$ حيث P هو حدث كون العدد الذي يتم اختباره عددًا أوليًا، و MR _k هو حدث اجتيازه لاختبار ميلر-رابين مع k جولة. غالبًا ما نهتم بدلًا من ذلك بالاحتمال الشرطي العكسي. $\Pr(\lnot P\mid M\!R_{k})$ احتمال أن يكون العدد الذي تم الإعلان عنه كعدد أولي قوي الاحتمال عددًا مركبًا في الواقع. ويرتبط هذان الاحتمالان بقانون بايز .

{\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}

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

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)

لذا، فإن هذا الاحتمال الشرطي لا يرتبط فقط بمقياس الخطأ المذكور أعلاه - والذي يقتصر على 4 ^{− k} - بل يرتبط أيضًا بتوزيع احتمالية الرقم المُدخل. في الحالة العامة، وكما ذُكر سابقًا، يتحكم في هذا التوزيع خصم تشفيري، وبالتالي فهو مجهول، لذا لا يمكننا استنتاج الكثير بشأنه. $\Pr(\lnot P\mid M\!R_{k})$ ومع ذلك، في حالة استخدام اختبار ميلر-رابين لتوليد الأعداد الأولية (انظر أدناه )، يتم اختيار التوزيع بواسطة المولد نفسه، لذلك يمكننا استغلال هذه النتيجة.

دمج اختبارات متعددة

يشير كالدول ^{[ 11 ]} إلى أن اختبارات احتمالية الأعداد الأولية القوية لقواعد مختلفة قد توفر أحيانًا اختبارًا إضافيًا للأعداد الأولية. فكما يتحقق الاختبار القوي من وجود أكثر من جذرين تربيعيين للعدد 1 بتردد n ، يمكن لاختبارين من هذا النوع التحقق أحيانًا من وجود أكثر من جذرين تربيعيين للعدد -1.

لنفترض أننا، خلال اختباراتنا الأولية المحتملة، نصادف أساسين a و a ′ بحيث $a^{2^{r}d}\equiv a^{\prime \,2^{r'}d}\equiv -1{\pmod {n}}$ مع r و r ′ ≥ 1. هذا يعني أننا قمنا بحساب جذرين تربيعيين كجزء من الاختبار، ويمكننا التحقق مما إذا كان $a^{2^{r-1}d}\equiv \pm a^{\prime \,2^{r'-1}d}{\pmod {n}}$ . يجب أن يكون هذا صحيحًا دائمًا إذا كان n عددًا أوليًا؛ وإلا، فقد وجدنا أكثر من جذرين تربيعيين لـ -1 وأثبتنا أن n عدد مركب.

هذا ممكن فقط إذا كان n ≡ 1 (mod 4)، ونجتاز اختبارات الأعداد الأولية المحتملة مع أساسين أو أكثر a بحيث يكون a ^d ≢ ±1 (mod n )، ولكنه إضافة غير مكلفة لاختبار ميلر-رابين الأساسي.

المتغيرات الحتمية

اختبار ميلر

يمكن جعل خوارزمية ميلر-رابين حتميةً بتجربة جميع القيم الممكنة لـ a التي تقل عن حد معين. باعتبار n هو الحد، فإن ذلك يعني $O(n)$ من المحاولات، وبالتالي سيكون زمن التشغيل أُسّيًا بالنسبة لحجم المدخلات $log n$ . لتحسين زمن التشغيل، يكمن التحدي في خفض الحد قدر الإمكان مع الحفاظ على موثوقية الاختبار.

إذا كان العدد المختبر n عددًا مركبًا، فإن الأعداد الكاذبة القوية a، وهي أعداد أولية فيما بينها مع n، تقع ضمن زمرة جزئية فعلية من الزمرة ( Z / nZ )*. وهذا يعني أنه إذا اختبرنا جميع الأعداد a من مجموعة تولد ( Z / nZ )*، فلا بد أن يقع أحدها خارج هذه الزمرة الجزئية، وبالتالي يكون شاهدًا على كون n عددًا مركبًا . بافتراض صحة فرضية ريمان المعممة (التي يسميها ميلر، بشكل مربك، " فرضية ريمان الموسعة ")، فمن المعروف أن الزمرة تتولد من عناصرها الأصغر من $O(($ $ln$ $n$ $)$ $²$ $)$ ، وهو ما أشار إليه ميلر سابقًا. ^[¹^] وقد اختُزل الثابت المستخدم في ترميز Big O إلى 2 بواسطة إريك باخ . ^[¹²^] يؤدي هذا إلى خوارزمية اختبار أولية الأعداد التالية، والمعروفة باسم اختبار ميلر ، وهي حتمية بافتراض صحة فرضية ريمان الموسعة:

المدخلات : n > 2، عدد فردي يُراد اختبار أوليته. المخرجات : " مركب " إذا كان n مركبًا، و" أولي " خلاف ذلك.

ليكن s > 0 و d فردي > 0 بحيث يكون n − 1 = 2 ^s d # باستخراج قوى 2 من n − 1 لجميع قيم a في النطاق [2, min( n − 2, ⌊2(ln n ) ² ⌋)]: x ← a ^d mod n كرر s مرة : y ← x ² mod n إذا كان y = 1 و x ≠ 1 و x ≠ n − 1 فإن # الجذر التربيعي غير التافه للعدد 1 modulo n أرجع " مركب " x ← y إذا كان y ≠ 1 فإن أرجع " مركب " أرجع " أولي "

لا يلزم استخدام القوة الكاملة لفرضية ريمان المعممة لضمان صحة الاختبار: بما أننا نتعامل مع مجموعات فرعية ذات دليل زوجي ، يكفي افتراض صحة فرضية ريمان المعممة للخصائص التربيعية لـ Dirichlet . ^{[ 7 ]}

زمن تشغيل الخوارزمية، وفقًا لترميز soft-O ، هو $Õ((log n) 4)$ (باستخدام الضرب القائم على تحويل فورييه السريع). ^{[ 13 ]}

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

الاختبار مقابل مجموعات صغيرة من القواعد

عندما يكون العدد n المراد اختباره صغيرًا، لا داعي لتجربة جميع الحالات التي يكون فيها $a < 2(ln n) 2$ ، إذ من المعروف أن مجموعات أصغر بكثير من الشهود المحتملين تكفي. على سبيل المثال، تحقق كل من بوميرانس وسيلفريدج وواغستاف ^{[ 4 ]} وياشكه ^{[ 14 ] من ذلك.}

إذا كان n < 2047، يكفي اختبار a = 2؛
إذا كان n < 1,373,653، فإنه يكفي اختبار a = 2 و 3؛
إذا كان n < 9,080,191، فإنه يكفي اختبار a = 31 و 73؛
إذا كان n < 25,326,001، فإنه يكفي اختبار a = 2 و 3 و 5؛
إذا كان n < 3,215,031,751، فإنه يكفي اختبار a = 2، 3، 5، و7؛
إذا كان n < 4,759,123,141، فإنه يكفي اختبار a = 2 و 7 و 61؛
إذا كان n < 1,122,004,669,633، فإنه يكفي اختبار a = 2، 13، 23، و 1662803؛
إذا كان n < 2,152,302,898,747، فإنه يكفي اختبار a = 2، 3، 5، 7، و 11؛
إذا كان n < 3,474,749,660,383، فإنه يكفي اختبار a = 2، 3، 5، 7، 11، و 13؛
إذا كان n < 341,550,071,728,321، فإنه يكفي اختبار a = 2، 3، 5، 7، 11، 13، و 17.
إن إضافة اختبار بقيمة a = 19 لا يحسن الحد السابق.

باستخدام عمل Feitsma و Galway لعام 2010 ^{[ 15 ]} الذي يسرد جميع الأعداد الأولية الزائفة ذات الأساس 2 حتى ²⁶⁴ ، تم توسيع هذا (انظر OEIS : A014233 )، مع عرض النتيجة الأولى لاحقًا باستخدام طرق مختلفة في Jiang و Deng: ^{[ 16 ]}

إذا كان n < 3,825,123,056,546,413,051، فإنه يكفي اختبار a = 2، 3، 5، 7، 11، 13، 17، 19، و 23.
إن إضافة الاختبارات مع a = 29 و 31 لا يحسن الحد السابق.
إذا كان n < 2 ⁶⁴ = 18,446,744,073,709,551,616، فإنه يكفي اختبار a = 2، 3، 5، 7، 11، 13، 17، 19، 23، 29، 31، و 37.

قام سورنسون وويبستر ^{[ 17 ]} بالتحقق من ما سبق وحساب النتائج الدقيقة لهذه النتائج الأكبر من 64 بت:

إذا كان n < 318,665,857,834,031,151,167,461، فإنه يكفي اختبار a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, و 37.
إذا كان n < 3,317,044,064,679,887,385,961,981، فإنه يكفي اختبار a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, و 41.

يقدم تشانغ (2007)، من خلال التركيز على أعداد صحيحة محددة، تنبؤات إضافية، مثل أن 18 عددًا أوليًا متتاليًا ستكون كافية لـ n < 1,543,267,864,443,420,616,877,677,640,751,301. ومع ذلك، فإن إثبات صحة ذلك لجميع الأعداد الصحيحة حتى هذا الحد يُعد أكثر صعوبة بكثير. ^{[ 18 ]}

توجد معايير أخرى من هذا النوع، غالبًا ما تكون أكثر كفاءة (تتطلب عددًا أقل من القواعد) من تلك الموضحة أعلاه، وذلك بإزالة شرط أن تكون القواعد متتالية. ^{[ 11 ]}^{[ 19 ]}^{[ 20 ]} على سبيل المثال، يكفي استخدام قاعدتين a = 336,781,006,125 و 9,639,812,373,923,155 عندما يكون n < 1,050,535,501؛ وسبع قواعد عندما يكون n < 2^ ⁶⁴ . يتضمن تحسين إضافي من ستيف وورلي وآخرين تقسيم الأعداد الصحيحة الأقل من N إلى مجموعات فرعية واختيار شهود مسبقًا لتقييم جميع عناصر تلك المجموعة الفرعية بشكل صحيح. يمكن لمثل هذا الاختبار استخدام شاهدين فقط لجميع قيم N الأقل من 2^64. ^{[ 21 ]}

توجد قائمة صغيرة من الشهود المحتملين لكل حجم إدخال ممكن (بحد أقصى b قيمة للأعداد ذات b بت). مع ذلك، لا تكفي أي مجموعة محدودة من القواعد لجميع الأعداد المركبة. وقد أثبت ألفورد، وغرانفيل، وبوميرانس وجود عدد لا نهائي من الأعداد المركبة n التي يكون أصغر شاهد تركيب لها على الأقل $(ln n) 1/(3ln ln ln n)$ . ^{[ 22 ]} كما جادلوا، استنادًا إلى الاستدلال، بأن أصغر عدد w بحيث يكون لكل عدد مركب أقل من n شاهد تركيب أقل من w يجب أن يكون من رتبة $Θ (log n log log n).$

طرق مختلفة لإيجاد العوامل

بإدخال حسابات القاسم المشترك الأكبر في الخوارزمية المذكورة أعلاه، يمكننا أحيانًا الحصول على عامل من عوامل n بدلًا من مجرد تحديد أن n عدد مركب. يحدث هذا، على سبيل المثال، عندما يكون n عددًا أوليًا محتملًا للأساس a ولكنه ليس عددًا أوليًا محتملًا قويًا للأساس a . ^{[ 23 ]}^{: 1402}

إذا كان x جذرًا تربيعيًا غير تافه للعدد 1 بتردد n ،

بما أن $x 2 \equiv 1 (mod n)$ ، فإننا نعلم أن n يقسم $x 2 - 1 = (x - 1)(x + 1)$ ؛
بما أن $x ≢ \pm1 (mod n)$ ، فإننا نعلم أن n لا يقسم $x - 1$ ولا $x + 1$ .

نستنتج من ذلك أن $A = gcd(x - 1, n)$ و $B = gcd(x + 1, n)$ عاملان غير تافهين (ليسا بالضرورة أوليين) للعدد n (في الواقع، بما أن n عدد فردي، فإن هذين العاملين أوليان فيما بينهما، وبالتالي n = AB ). لذا، إذا كان الهدف هو التحليل إلى عوامل، فيمكن إدخال حسابات القاسم المشترك الأكبر هذه في الخوارزمية بتكلفة حسابية إضافية بسيطة. وهذا يؤدي إلى الشفرة الزائفة التالية، حيث تم تمييز الشفرة المضافة أو المعدلة:

المدخل رقم 1 : n > 2، عدد صحيح فردي يُراد اختباره لمعرفة ما إذا كان أوليًا. المدخل رقم 2 : k ، عدد جولات الاختبار المطلوب إجراؤها. المخرج : (" مضاعف لـ "، m ) إذا تم العثور على عامل غير تافه m للعدد n ، " مركب " إذا تبين أن n مركب. " ربما يكون سعره الأساسي " خلاف ذلك

ليكن s > 0 و d فردي > 0 بحيث يكون n − 1 = 2 ^s d # باستخراج قوى 2 من n − 1 كرر k مرة : a ← random(2, n − 2) # n دائمًا عدد أولي محتمل للأساس 1 و n − 1 x ← a ^d mod n كرر s مرة : y ← x ² mod n إذا كان y = 1 و x ≠ 1 و x ≠ n − 1 فإن # الجذر التربيعي غير التافه لـ 1 modulo n أرجع (" مضاعف لـ ", gcd( x − 1, n )) x ← y إذا كان y ≠ 1 فإن أرجع " مركب " أرجع " أولي محتمل "

هذه ليست خوارزمية تحليل احتمالية، لأنها لا تستطيع إيجاد عوامل إلا للأعداد n التي هي أعداد شبه أولية بالنسبة للأساس a (أي الأعداد n التي تحقق $a <sub> n -1 </sub> \equiv 1 mod n$ ). أما بالنسبة للأعداد الأخرى، فإن الخوارزمية تُرجع فقط "مركب" دون أي معلومات إضافية.

على سبيل المثال، لنفترض أن n = 341 و a = 2. لدينا $n - 1 = 85 \times 4.$ إذن، $285 mod 341 = 32$ و $322 mod 341 = 1.$ هذا يدل على أن n عدد أولي زائف أساسه 2، ولكنه ليس عددًا أوليًا زائفًا قويًا أساسه 2. بحساب القاسم المشترك الأكبر في هذه المرحلة، نجد عاملًا للعدد 341: $gcd(32 - 1, 341) = 31.$ في الواقع، $341 = 11 \times 31$ .

يمكن تطبيق الأسلوب نفسه على الجذور التربيعية لأي قيمة أخرى، وخاصة الجذور التربيعية للعدد -1 المذكورة في قسم " دمج الاختبارات المتعددة" . إذا أثبت اختباران قويان محتملان للأعداد الأولية أن $x²$ $\equiv -1 (mod n)$ و $y² \equiv -1 (mod n) ،$ ولكن $x ≢ \pm y (mod n)$ ، فإن $القاسم المشترك الأكبر (x - y, n)$ والقاسم $المشترك الأكبر (x + y, n)$ هما عاملان غير تافهين للعدد n . ^{[ 11 ]}

على سبيل المثال، $n = 46,856,248,255,981$ هو عدد أولي زائف قوي للأساسين 2 و7، ولكن أثناء إجراء الاختبارات نجد

2^{(n-1)/2}\equiv 7^{(n-1)/2}\equiv -1{\pmod {n}},

2^{(n-1)/4}\equiv 34456063004337{\pmod {n}},{\text{ and}}

7^{(n-1)/4}\equiv 21307242304265{\pmod {n}}.

وهذا يعطينا العامل $gcd(34456063004337 - 21307242304265, n) = 4840261$ .

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

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

المدخل رقم 1 : b ، عدد بتات النتيجة. المدخل رقم 2 : k ، عدد جولات الاختبار المطلوب إجراؤها. المخرج : عدد أولي قوي محتمل n

بينما صحيح: اختر عددًا فرديًا عشوائيًا n في النطاق [2b ^{- 1} , ^2b - 1] ، إذا أعاد اختبار ميلر-رابين مع المدخلات n و k القيمة " ربما يكون عددًا أوليًا "، فأعد n .

تعقيد

بالطبع، أسوأ حالة لوقت التشغيل هي اللانهاية، لأن الحلقة الخارجية قد لا تنتهي أبدًا، ولكن هذا يحدث باحتمالية صفر. وفقًا للتوزيع الهندسي ، فإن العدد المتوقع للسحوبات هو ${\tfrac {1}{\Pr(M\!R_{k})}}$ (إعادة استخدام الرموز من السابق ).

بما أن أي عدد أولي يجتاز الاختبار، فإن احتمال كونه عددًا أوليًا يُعطي حدًا أدنى تقريبيًا لاحتمال اجتيازه الاختبار. إذا سحبنا أعدادًا فردية بشكل منتظم في النطاق [2b ^{− 1} , ^1b −1]، فسنحصل على:

\Pr(M\!R_{k})>\Pr(1)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}

حيث π هي دالة عدّ الأعداد الأولية . باستخدام التوسع التقاربي لـ π (وهو امتداد لنظرية الأعداد الأولية )، يمكننا تقريب هذا الاحتمال عندما يؤول b إلى اللانهاية. نجد:

\Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)

{\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)

وبالتالي، يمكننا أن نتوقع ألا يُجري المولد اختبارات ميلر-رابين أكثر من عدد يتناسب مع b . مع الأخذ في الاعتبار تعقيد أسوأ حالة لكل اختبار ميلر-رابين (انظر سابقًا )، فإن وقت التشغيل المتوقع للمولد مع المدخلات b و k يكون محدودًا بـ $O(k b 4)$ (أو $Õ(k b 3)$ باستخدام الضرب القائم على تحويل فورييه السريع).

دقة

مقياس الخطأ لهذا المولد هو احتمال أن يُخرج عددًا مركبًا.

باستخدام العلاقة بين الاحتمالات الشرطية (الموضحة في قسم سابق ) والسلوك التقاربي لـ $\Pr(P)$ (كما هو موضح أعلاه)، يمكن إعطاء مقياس الخطأ هذا حدًا أعلى تقريبيًا:

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).

وبالتالي، بالنسبة لقيم b الكبيرة بما يكفي ، يكون مقياس الخطأ هذا أقل من ${\tfrac {\ln 2}{2}}4^{-k}b$ ومع ذلك، توجد حدود أفضل بكثير.

باستخدام حقيقة أن اختبار ميلر-رابين نفسه غالبًا ما يكون له حد خطأ أصغر بكثير من 4 − ^{k (} انظر سابقًا )، استنتج دامغارد ولاندروك وبوميرانس عدة حدود خطأ للمولد، مع فئات مختلفة من المعاملات b و k . ^[⁹^] تسمح حدود الخطأ هذه للمنفذ باختيار قيمة معقولة لـ k للحصول على الدقة المطلوبة.

أحد حدود الخطأ هذه هو 4 ^{− k} ، وهو صحيح لجميع قيم b ≥ 2 (أظهر المؤلفون ذلك فقط لقيم b ≥ 51، بينما أكمل رونالد بيرث الابن البرهان بالقيم المتبقية 2 ≤ b ≤ 50 ^{[ 24 ]} ). ويمكن تحسين هذا الحد البسيط لقيم b الكبيرة . على سبيل المثال، حد آخر استنتجه المؤلفون أنفسهم هو:

\left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}

وهذا ينطبق على جميع قيم b ≥ 21 و k ≥ b /4. هذا الحد أصغر من 4 ^{− k} بمجرد أن تصبح b ≥ 32.

ملحوظات

↑ غالبًا ما يُقال خطأً أن اختبار ميلر-رابين قد اكتشفه إم إم أرتيهوف في عام 1967؛ إن قراءة ورقة أرتيهوف^{[ 3 ]} (وخاصة نظريته E ) تُظهر أنه في الواقع اكتشف اختبار سولوفاي-ستراسن.
↑ على سبيل المثال، في عام 1995، قدم أرنو عددًا مركبًا مكونًا من 397 رقمًا تكون جميع قواعده الأقل من 307 كاذبة قوية؛ وقد تم الإبلاغ عن أن هذا العدد أولي بواسطة دالة Mapleisprime() ، لأنه طبق اختبار ميلر-رابين مع القواعد المحددة 2 و3 و5 و7 و11.^{[ 5 ]}
↑ على سبيل المثال، في عام 2018، تمكن ألبريشت وآخرون من إنشاء أعداد مركبة للعديد من مكتبات التشفير مثل OpenSSL و GNU GMP ، والتي أعلنت هذه المكتبات أنها أعداد أولية، مما يدل على أنها لم تُنفذ مع وضع سياق معادٍ في الاعتبار.^{[ 10 ]}

مراجع

1 2 ميلر، غاري ل. (1976)، "فرضية ريمان واختبارات أولية الأعداد"، مجلة علوم الحاسوب والأنظمة ، 13 (3): 300-317 ، doi : 10.1145/800116.803773 ، S2CID 10690396
1 2 رابين، مايكل أو. (1980)، "خوارزمية احتمالية لاختبار أولية الأعداد"، مجلة نظرية الأعداد ، 12 (1): 128-138 ، doi : 10.1016/0022-314X(80)90084-0
↑ أرتيوهوف، م.م. (1966-1967)، "معايير معينة لأولية الأعداد مرتبطة بنظرية فيرما الصغرى"، أكتا أريثميتيكا ، 12 : 355-364 ، MR 0213289
1 2 كارل بوميرانس ؛ جون ل. سيلفريدج ؛ صموئيل س. واغستاف الابن (يوليو 1980). "الأعداد الأولية الزائفة حتى 25 × ^10⁹ " (ملف PDF) . رياضيات الحساب . 35 (151): 1003-1026 . doi : 10.1090/S0025-5718-1980-0572872-7 .
↑ ف. أرنو (أغسطس 1995). "بناء أعداد كارمايكل التي هي أعداد شبه أولية قوية لعدة قواعد" . مجلة الحساب الرمزي . 20 (2): 151-161 . doi : 10.1006/jsco.1995.1042 .
^ كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. "31". مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 968 – 971. ISBN 0-262-03384-4.
1 2 شوف، رينيه (2004)، "أربع خوارزميات لاختبار أولية الأعداد" (ملف PDF) ، نظرية الأعداد الخوارزمية: الشبكات، حقول الأعداد، المنحنيات والتشفير ، مطبعة جامعة كامبريدج، ISBN 978-0-521-80854-5
↑ سلون، ن. ج. أ. (محرر). "المتتالية A329759 (الأعداد المركبة الفردية k التي يكون عدد الأدلة على شبه أولية k فيها مساويًا لـ φ(k)/4)" . الموسوعة الإلكترونية لمتتاليات الأعداد الصحيحة . مؤسسة OEIS.
1 2 دامغارد، آي .؛ لاندروك، ب.؛ وبوميرانس ، سي. (1993)، "تقديرات الخطأ في الحالة المتوسطة لاختبار العدد الأولي القوي المحتمل" (ملف PDF) ، رياضيات الحساب ، 61 (203): 177-194 ، Bibcode : 1993MaCom..61..177D ، doi : 10.2307/2152945 ، JSTOR 2152945
↑ مارتن ر. ألبريشت؛ جيك ماسيمو؛ كينيث ج. باترسون؛ يوراي سوموروفسكي (15 أكتوبر 2018). الأعداد الأولية والتحيز: اختبار الأعداد الأولية في ظل ظروف معادية (ملف PDF) . مؤتمر ACM SIGSAC لأمن الحاسوب والاتصالات 2018. تورنتو: رابطة آلات الحوسبة . الصفحات 281-298 . doi : 10.1145/3243734.3243787 .
1 2 3 كالدول، كريس. "إيجاد الأعداد الأولية وإثبات أوليتها - 2.3: احتمالية أولية قوية واختبار عملي" . صفحات الأعداد الأولية . تم الاطلاع عليه في 24 فبراير 2019 .
↑ باخ، إريك (1990)، "حدود صريحة لاختبار أولية الأعداد والمشاكل ذات الصلة"، رياضيات الحساب ، 55 (191): 355-380 ، Bibcode : 1990MaCom..55..355B ، doi : 10.2307/2008811 ، JSTOR 2008811
↑ تشانغ، تشنشيانغ (2010-04-01). "حول فعالية تعميم نظرية ميلر للأعداد الأولية" . مجلة التعقيد . 26 (2): 200-208 . doi : 10.1016/j.jco.2010.01.002 . ISSN 0885-064X .
↑ ياشكه، جيرهارد (أكتوبر 1993)، "حول الأعداد الأولية الزائفة القوية لعدة قواعد" (ملف PDF) ، رياضيات الحساب ، 61 (204): 915-926 ، doi : 10.2307/2153262 ، JSTOR 2153262
↑ فيتسما، جان (25 أبريل 2013). غالواي، ويليام (محرر). "جداول الأعداد الأولية الزائفة والبيانات ذات الصلة" . مركز الرياضيات التجريبية والبنائية، جامعة سيمون فريزر . تاريخ الاسترجاع: 22 نوفمبر 2024 .
↑ جيانغ، يوبينغ؛ دينغ، يينغبو (2014). "الأعداد الأولية الزائفة القوية للأساسات الثمانية الأولى" . رياضيات الحساب . 83 (290): 2915-2924 . doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405 .
↑ سورنسون، جوناثان؛ ويبستر، جوناثان (2015). "الأعداد الأولية الزائفة القوية إلى اثني عشر أساسًا أوليًا". رياضيات الحساب . 86 (304): 985-1003 . arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S . doi : 10.1090/mcom/3134 . S2CID 6955806 .
↑ تشانغ، تشنشيانغ (1 أكتوبر 2007). "نوعان من الأعداد الأولية الزائفة القوية حتى 10^36" (ملف PDF) . رياضيات الحساب . 76 (260): 2095-2108 . doi : 10.1090/S0025-5718-07-01977-1 .
↑ تشانغ، تشنشيانغ وتانغ، مين (أكتوبر 2003)، "إيجاد الأعداد الأولية الزائفة القوية لعدة قواعد. الجزء الثاني" (ملف PDF) ، رياضيات الحساب ، 72 (44): 2085-2097 ، رمز Bibcode : 2003MaCom..72.2085Z ، doi : 10.1090/S0025-5718-03-01545-X
↑ سلون، ن. ج. أ. (محرر). "المتتالية A014233 (أصغر عدد فردي لا يكشف اختبار ميلر-رابين للأعداد الأولية على أساسات ≤ العدد الأولي النوني عن تركيبها)" . الموسوعة الإلكترونية لمتتاليات الأعداد الصحيحة . مؤسسة OEIS.
↑ إيزيكوفسكي، فويتش. "المتغيرات الحتمية لاختبار ميلر-رابين للأولية" . تم الاسترجاع في 24 فبراير 2019 .
↑ ألفورد، دبليو آر ؛ جرانفيل، أ .؛ بوميرانس، سي. (1994)، "حول صعوبة إيجاد شهود موثوقين"، نظرية الأعداد الخوارزمية (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 877، سبرينغر-فيرلاغ، الصفحات 1-16 ، doi : 10.1007/3-540-58691-1_36 ، ISBN 978-3-540-58691-3
↑ روبرت بيلي؛ صموئيل س. واغستاف الابن (أكتوبر 1980). "أعداد لوكاس الأولية الزائفة" (ملف PDF) . رياضيات الحساب . 35 (152): 1391-1417 . doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518 .
↑ بيرث الابن، رونالد ج. (1996)، "مزيد من التحقيقات باستخدام اختبار الاحتمال القوي للأعداد الأولية" (ملف PDF) ، رياضيات الحساب ، 65 (213): 373-381 ، Bibcode : 1996MaCom..65..373B ، doi : 10.1090/S0025-5718-96-00695-3

روابط خارجية

[4] غالبًا ما يُقال خطأً أن اختبار ميلر-رابين قد اكتشفه إم إم أرتيهوف في عام 1967؛ إن قراءة ورقة أرتيهوف^{[ 3 ]} (وخاصة نظريته E ) تُظهر أنه في الواقع اكتشف اختبار سولوفاي-ستراسن.

[7] على سبيل المثال، في عام 1995، قدم أرنو عددًا مركبًا مكونًا من 397 رقمًا تكون جميع قواعده الأقل من 307 كاذبة قوية؛ وقد تم الإبلاغ عن أن هذا العدد أولي بواسطة دالة Mapleisprime() ، لأنه طبق اختبار ميلر-رابين مع القواعد المحددة 2 و3 و5 و7 و11.^{[ 5 ]}

[13] على سبيل المثال، في عام 2018، تمكن ألبريشت وآخرون من إنشاء أعداد مركبة للعديد من مكتبات التشفير مثل OpenSSL و GNU GMP ، والتي أعلنت هذه المكتبات أنها أعداد أولية، مما يدل على أنها لم تُنفذ مع وضع سياق معادٍ في الاعتبار.^{[ 10 ]}

[miller-1] 1 2 ميلر، غاري ل. (1976)، "فرضية ريمان واختبارات أولية الأعداد"، مجلة علوم الحاسوب والأنظمة ، 13 (3): 300-317 ، doi : 10.1145/800116.803773 ، S2CID 10690396

[rabin-2] 1 2 رابين، مايكل أو. (1980)، "خوارزمية احتمالية لاختبار أولية الأعداد"، مجلة نظرية الأعداد ، 12 (1): 128-138 ، doi : 10.1016/0022-314X(80)90084-0

[3] أرتيوهوف، م.م. (1966-1967)، "معايير معينة لأولية الأعداد مرتبطة بنظرية فيرما الصغرى"، أكتا أريثميتيكا ، 12 : 355-364 ، MR 0213289

[PSW-5] 1 2 كارل بوميرانس ؛ جون ل. سيلفريدج ؛ صموئيل س. واغستاف الابن (يوليو 1980). "الأعداد الأولية الزائفة حتى 25 × ^10⁹ " (ملف PDF) . رياضيات الحساب . 35 (151): 1003-1026 . doi : 10.1090/S0025-5718-1980-0572872-7 .

[Arnault397Digit-6] ف. أرنو (أغسطس 1995). "بناء أعداد كارمايكل التي هي أعداد شبه أولية قوية لعدة قواعد" . مجلة الحساب الرمزي . 20 (2): 151-161 . doi : 10.1006/jsco.1995.1042 .

[8] كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. "31". مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 968 – 971. ISBN 0-262-03384-4.

[schoof-9] 1 2 شوف، رينيه (2004)، "أربع خوارزميات لاختبار أولية الأعداد" (ملف PDF) ، نظرية الأعداد الخوارزمية: الشبكات، حقول الأعداد، المنحنيات والتشفير ، مطبعة جامعة كامبريدج، ISBN 978-0-521-80854-5

[10] سلون، ن. ج. أ. (محرر). "المتتالية A329759 (الأعداد المركبة الفردية k التي يكون عدد الأدلة على شبه أولية k فيها مساويًا لـ φ(k)/4)" . الموسوعة الإلكترونية لمتتاليات الأعداد الصحيحة . مؤسسة OEIS.

[damgård-landrock-pomerance-11] 1 2 دامغارد، آي .؛ لاندروك، ب.؛ وبوميرانس ، سي. (1993)، "تقديرات الخطأ في الحالة المتوسطة لاختبار العدد الأولي القوي المحتمل" (ملف PDF) ، رياضيات الحساب ، 61 (203): 177-194 ، Bibcode : 1993MaCom..61..177D ، doi : 10.2307/2152945 ، JSTOR 2152945

[12] مارتن ر. ألبريشت؛ جيك ماسيمو؛ كينيث ج. باترسون؛ يوراي سوموروفسكي (15 أكتوبر 2018). الأعداد الأولية والتحيز: اختبار الأعداد الأولية في ظل ظروف معادية (ملف PDF) . مؤتمر ACM SIGSAC لأمن الحاسوب والاتصالات 2018. تورنتو: رابطة آلات الحوسبة . الصفحات 281-298 . doi : 10.1145/3243734.3243787 .

[prime-pages-14] 1 2 3 كالدول، كريس. "إيجاد الأعداد الأولية وإثبات أوليتها - 2.3: احتمالية أولية قوية واختبار عملي" . صفحات الأعداد الأولية . تم الاطلاع عليه في 24 فبراير 2019 .

[15] باخ، إريك (1990)، "حدود صريحة لاختبار أولية الأعداد والمشاكل ذات الصلة"، رياضيات الحساب ، 55 (191): 355-380 ، Bibcode : 1990MaCom..55..355B ، doi : 10.2307/2008811 ، JSTOR 2008811

[16] تشانغ، تشنشيانغ (2010-04-01). "حول فعالية تعميم نظرية ميلر للأعداد الأولية" . مجلة التعقيد . 26 (2): 200-208 . doi : 10.1016/j.jco.2010.01.002 . ISSN 0885-064X .

[17] ياشكه، جيرهارد (أكتوبر 1993)، "حول الأعداد الأولية الزائفة القوية لعدة قواعد" (ملف PDF) ، رياضيات الحساب ، 61 (204): 915-926 ، doi : 10.2307/2153262 ، JSTOR 2153262

[18] فيتسما، جان (25 أبريل 2013). غالواي، ويليام (محرر). "جداول الأعداد الأولية الزائفة والبيانات ذات الصلة" . مركز الرياضيات التجريبية والبنائية، جامعة سيمون فريزر . تاريخ الاسترجاع: 22 نوفمبر 2024 .

[19] جيانغ، يوبينغ؛ دينغ، يينغبو (2014). "الأعداد الأولية الزائفة القوية للأساسات الثمانية الأولى" . رياضيات الحساب . 83 (290): 2915-2924 . doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405 .

[20] سورنسون، جوناثان؛ ويبستر، جوناثان (2015). "الأعداد الأولية الزائفة القوية إلى اثني عشر أساسًا أوليًا". رياضيات الحساب . 86 (304): 985-1003 . arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S . doi : 10.1090/mcom/3134 . S2CID 6955806 .

[21] تشانغ، تشنشيانغ (1 أكتوبر 2007). "نوعان من الأعداد الأولية الزائفة القوية حتى 10^36" (ملف PDF) . رياضيات الحساب . 76 (260): 2095-2108 . doi : 10.1090/S0025-5718-07-01977-1 .

[22] تشانغ، تشنشيانغ وتانغ، مين (أكتوبر 2003)، "إيجاد الأعداد الأولية الزائفة القوية لعدة قواعد. الجزء الثاني" (ملف PDF) ، رياضيات الحساب ، 72 (44): 2085-2097 ، رمز Bibcode : 2003MaCom..72.2085Z ، doi : 10.1090/S0025-5718-03-01545-X

[23] سلون، ن. ج. أ. (محرر). "المتتالية A014233 (أصغر عدد فردي لا يكشف اختبار ميلر-رابين للأعداد الأولية على أساسات ≤ العدد الأولي النوني عن تركيبها)" . الموسوعة الإلكترونية لمتتاليات الأعداد الصحيحة . مؤسسة OEIS.

[24] إيزيكوفسكي، فويتش. "المتغيرات الحتمية لاختبار ميلر-رابين للأولية" . تم الاسترجاع في 24 فبراير 2019 .

[25] ألفورد، دبليو آر ؛ جرانفيل، أ .؛ بوميرانس، سي. (1994)، "حول صعوبة إيجاد شهود موثوقين"، نظرية الأعداد الخوارزمية (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 877، سبرينغر-فيرلاغ، الصفحات 1-16 ، doi : 10.1007/3-540-58691-1_36 ، ISBN 978-3-540-58691-3

[baillie-26] روبرت بيلي؛ صموئيل س. واغستاف الابن (أكتوبر 1980). "أعداد لوكاس الأولية الزائفة" (ملف PDF) . رياضيات الحساب . 35 (152): 1391-1417 . doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518 .

[burthe-27] بيرث الابن، رونالد ج. (1996)، "مزيد من التحقيقات باستخدام اختبار الاحتمال القوي للأعداد الأولية" (ملف PDF) ، رياضيات الحساب ، 65 (213): 373-381 ، Bibcode : 1996MaCom..65..373B ، doi : 10.1090/S0025-5718-96-00695-3

[ 1 ]

[ 2 ]

[ أ ]

[ 4 ]

[ ب ]

[ 6 ]

[

[

[ 9 ]

[ ج ]

[ 11 ]

[

[ 13 ]

[ 14 ] من ذلك.

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 3 ]

[ 5 ]

[ 10 ]