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

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

فكرة

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

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

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