اختبار لوكاس للأولوية

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

ليكن n عددًا صحيحًا موجبًا. إذا وُجد عدد صحيح a ، حيث 1  < a < n ، بحيث   

${\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}\,}$

ولكل عامل أولي q للعدد n − 1  

${\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}\,}$

إذا كان n عددًا أوليًا ، فإن n يكون إما 1 أو 2 أو عددًا مركبًا .

يكمن سبب صحة هذا الادعاء فيما يلي: إذا تحققت المعادلة الأولى للعدد a ، نستنتج أن a و n عددان أوليان فيما بينهما . وإذا تحققت المعادلة الثانية أيضًا للعدد a، فإن رتبة a في المجموعة ( Z / nZ ) * تساوي n - 1، مما يعني أن رتبة تلك المجموعة هي n - 1 (لأن رتبة أي عنصر في المجموعة تقسم رتبة المجموعة)، وهذا يستلزم أن n عدد أولي . وعلى العكس، إذا كان n عددًا أوليًا، فإنه يوجد جذر أولي بتردد n ، أو مولد للمجموعة ( Z / nZ )*. رتبة هذا المولد هي |( Z / nZ ) *| = n - 1 ، وتتحقق المعادلتان لأي جذر أولي من هذا النوع.        

لاحظ أنه إذا كان هناك a <  n بحيث يفشل التكافؤ الأول، فإن a يسمى شاهد فيرما على تركيب n . 

على سبيل المثال، لنفترض أن n = 71. إذن n − 1 = 70، والعوامل الأولية للعدد 70 هي 2 و5 و7. نختار عشوائيًا قيمة a = 17 < n . الآن نحسب:      

${\displaystyle 17^{70}\ \equiv \ 1{\pmod {71}}.}$

من المعروف أن لكل عدد صحيح a

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}\ {\text{ إذا وفقط إذا }}{\text{ ord}}(a)\mid (n-1).}$

لذا، فإنّ الترتيب الضربي للعدد 17 (mod 71) ليس بالضرورة 70، لأنّ أحد عوامل 70 قد يكون صحيحًا أيضًا. لذا، جرّب قسمة 70 على عوامله الأولية.

${\displaystyle 17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.}$

للأسف، نحصل على أن 17 ¹⁰ ≡ 1 (mod 71). لذا ما زلنا لا نعرف ما إذا كان 71 عددًا أوليًا أم لا.    

نجرب قيمة عشوائية أخرى لـ a ، وهذه المرة نختار a  =  11. الآن نحسب:

${\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}.}$

مرة أخرى، هذا لا يُثبت أن الترتيب الضربي للعدد 11 (mod 71) هو 70، لأن أحد عوامل العدد 70 قد يكون صحيحًا أيضًا. لذا، تحقق من قسمة 70 على عوامله الأولية:

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}.}$

إذن فإن الترتيب الضربي للعدد 11 (mod 71) هو 70، وبالتالي فإن 71 عدد أولي.

(لإجراء عمليات الأسس المعيارية هذه ، يمكن للمرء استخدام خوارزمية أسية سريعة مثل الأسية الثنائية أو الأسية لسلسلة الجمع ).

يمكن كتابة الخوارزمية بلغة شبه رمزية كما يلي:

خوارزمية اختبار لوكاس للأعداد الأولية تأخذ المدخلات التالية : n > 2، وهو عدد فردي يُراد اختباره لتحديد أوليته. k ، وهو مُعامل يُحدد دقة الاختبار. تُخرج الخوارزمية : عددًا أوليًا إذا كان n عددًا أوليًا، وإلا عددًا مُركبًا أو قد يكون مُركبًا . حدد العوامل الأولية للعدد n − 1. الحلقة 1: كرر k مرة: اختر قيمة عشوائية في النطاق [2، n − 1] إذا${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ثم أعد المركب وإلا |${\displaystyle \color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}}$ الحلقة 2: لجميع العوامل الأولية q للعدد n − 1: إذا${\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}$ثم إذا تحققنا من هذه المساواة لجميع العوامل الأولية لـ n − 1 ، فأرجع عددًا أوليًا، وإلا فتابع الحلقة 2،  وإلا #${\displaystyle \color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}}$استمر في الحلقة 1 قد يكون العائد مركباً .

• إدوارد لوكاس ، الذي سُمّي هذا الاختبار باسمه
• نظرية فيرما الصغيرة
• اختبار بوكلينغتون للأعداد الأولية ، وهو نسخة محسنة من هذا الاختبار لا تتطلب سوى تحليل جزئي لـ n  −  1
• شهادة الأولوية