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

اختبار فيرما لأولية عدد ما هو اختبار احتمالي لتحديد إذا كان عدد طبيعي ما عددا أوليا محتملا.

فكرة

بحسب مبرهنة فيرما الصغرى، والتي بحسبها فإن لكل عدد أوّلي p، وعدد a بحيث أن p لا يـُقـسِّم a يتحققّ:

$a^{p-1}\equiv 1(modp)$

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

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

مثال

لنفتَرض أنّ لدينا عدد n = 221 ونودّ التحقق ما إذا كان أوّليا. اختر بشكل عشوائي عدد $1<a<221$ ، مثلاً a = 38. الآن نفحص ما إذا كان العدد الذي اخترناه يُحقق المعادلة في الأعلى.

$a^{n-1}=38^{220}\equiv 1(\mathrm{mod}221).$

لذلك فإن العدد الذي اخترناه يُحقق المعادلة. الآن هنالك احتمالين، إمّا أن يكون 221 عدداً أوّليّا حقاً، أو عدد «فيرما كاذب». لذلك نقوم باختيار عدد آخر، مثلاً a = 24.

$a^{n-1}=24^{220}\equiv 81\equiv ̸1(\mathrm{mod}221).$

لذلك فإن 221 ليس عدد أوّلي والعدد 38 هو في الحقيقة عدد «فيرما كاذب»، علاوة على ذلك، فإن العدد 24 شاهد على كوَن العدد 221 عدد غير أوّلي.