عدد أولي زائف

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

تستخدم بعض المصادر مصطلح "الأعداد الأولية الزائفة" لوصف جميع الأعداد الأولية المحتملة، سواء كانت أعدادًا مركبة أو أعدادًا أولية فعلية.

تُعدّ الأعداد شبه الأولية ذات أهمية بالغة في التشفير بالمفتاح العام ، الذي يستغل صعوبة تحليل الأعداد الكبيرة إلى عواملها الأولية. قدّر كارل بوميرانس في عام 1988 أن تحليل عدد مكون من 144 رقمًا سيكلف 10 ملايين دولار، بينما سيكلف تحليل عدد مكون من 200 رقم 100 مليار دولار (انخفضت التكلفة اليوم بشكل كبير، لكنها لا تزال باهظة). ^{[ 1 ] [ 2 ]} إلا أن إيجاد عددين أوليين كبيرين، كما هو مطلوب لهذا الاستخدام، مكلف أيضًا، لذا تُستخدم اختبارات احتمالية مختلفة للأعداد الأولية ، والتي قد يُعطي بعضها، في حالات نادرة، أعدادًا مركبة بدلًا من الأعداد الأولية. من ناحية أخرى، لا تُعطي اختبارات الأعداد الأولية القطعية، مثل اختبار AKS للأعداد الأولية ، نتائج إيجابية خاطئة ؛ ولهذا السبب، لا توجد أعداد شبه أولية فيما يتعلق بها.

تنص نظرية فيرما الصغرى على أنه إذا كان p عددًا أوليًا وكان a عددًا أوليًا نسبيًا مع p ، فإن a ^{( p⁻¹} - 1) يقبل القسمة على p . بالنسبة لعدد صحيح a > 1 ، إذا كان عدد صحيح مركب x يقسم a( ^{x⁻¹ -} 1) ، فإن x يُسمى عددًا أوليًا زائفًا لفيرما للأساس a . ويترتب على ذلك أنه إذا كان x عددًا أوليًا زائفًا لفيرما للأساس a ، فإن x يكون أوليًا نسبيًا مع a . تستخدم بعض المصادر صيغًا مختلفة لهذا التعريف، على سبيل المثال للسماح فقط للأعداد الفردية بأن تكون أعدادًا أولية زائفة. ^{[ 3 ]}

يُطلق على العدد الصحيح x الذي يكون عددًا أوليًا زائفًا من نوع فيرما لجميع قيم a التي تكون أولية نسبيًا مع x اسم عدد كارمايكل .