اختبار بيبان

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

يترك${\displaystyle F_{n}=2^{2^{n}}+1}$ليكن العدد النوني لفرما. ينص اختبار بيبين على أنه بالنسبة لـ n > 0،

${\displaystyle F_{n}}$يكون عدد أولي إذا وفقط إذا${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

التعبير${\displaystyle 3^{(F_{n}-1)/2}}$يمكن تقييمها بوحدة${\displaystyle F_{n}}$عن طريق التربيع المتكرر . وهذا ما يجعل الاختبار خوارزمية سريعة ذات زمن متعدد الحدود . مع ذلك، تتزايد أعداد فيرما بسرعة كبيرة بحيث لا يمكن اختبار سوى عدد قليل منها في وقت ومساحة معقولين.

يمكن استخدام قواعد أخرى بدلاً من القاعدة 3. وهذه القواعد هي:

3، 5، 6، 7، 10، 12، 14، 20، 24، 27، 28، 39، 40، 41، 45، 48، 51، 54، 56، 63، 65، 75، 78، 80، 82، 85، 90، 91، 96، 102، 105، 108، 112، 119، 125، 126، 130، 147، 150، 156، 160، ... (التسلسل A129802 في OEIS ) .

تُسمى الأعداد الأولية في التسلسل أعلاه بالأعداد الأولية النخبة ، وهي:

3، 5، 7، 41، 15361، 23041، 26881، 61441، 87041، 163841، 544001، 604801، 6684673، 14172161، 159318017، 446960641، 1151139841، 3208642561، 38126223361، 108905103361، 171727482881، 318093312001، 443069456129، 912680550401، ... (التسلسل A102742 في OEIS )

بالنسبة للأعداد الصحيحة b > 1، يمكن استخدام الأساس b إذا وفقط إذا كان عدد محدود فقط من أعداد فيرما F _n يحقق ما يلي:${\displaystyle \left({\frac {b}{F_{n}}}\right)=1}$، أين${\displaystyle \left({\frac {b}{F_{n}}}\right)}$هو رمز جاكوبي .

في الواقع، اختبار بيبين هو نفسه اختبار أويلر-جاكوبي لأعداد فيرما، لأن رمز جاكوبي${\displaystyle \left({\frac {b}{F_{n}}}\right)}$هو −1، أي لا توجد أعداد فيرما التي هي أعداد أولية زائفة من نوع أويلر-جاكوبي لهذه القواعد المدرجة أعلاه.

الكفاية: افترض أن التطابق

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$

يوقف. ثم${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$وبالتالي فإن الترتيب الضربي للعدد 3 modulo${\displaystyle F_{n}}$يقسم${\displaystyle F_{n}-1=2^{2^{n}}}$وهو قوة للعدد اثنين. من ناحية أخرى، لا يقسم الترتيب${\displaystyle (F_{n}-1)/2}$وبالتالي يجب أن يكون مساوياً لـ${\displaystyle F_{n}-1}$وعلى وجه الخصوص، هناك على الأقل${\displaystyle F_{n}-1}$الأرقام أدناه${\displaystyle F_{n}}$عدد أولي نسبيًا لـ${\displaystyle F_{n}}$وهذا لا يمكن أن يحدث إلا إذا${\displaystyle F_{n}}$هو عدد أولي.

الضرورة: افترض أن${\displaystyle F_{n}}$هو عدد أولي. وفقًا لمعيار أويلر ،

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$،

أين${\displaystyle \left({\frac {3}{F_{n}}}\right)}$هو رمز ليجندر . من خلال التربيع المتكرر، نجد أن${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$، هكذا${\displaystyle F_{n}\equiv 2{\pmod {3}}}$، و${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$. مثل${\displaystyle F_{n}\equiv 1{\pmod {4}}}$نختتم${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$من قانون التبادل التربيعي .

نظراً لندرة أعداد فيرما، لم يُجرَ اختبار بيبين إلا ثماني مرات (على أعداد فيرما التي لم تكن حالات أوليتها معروفة مسبقاً). ^{[ 1 ] [ 2 ] [ 3 ]} ويتكهن ماير وبابادوبولوس وكراندال بأنه في الواقع، ونظراً لحجم أعداد فيرما التي لم تُحدد بعد، سيتطلب الأمر تقدماً كبيراً في التكنولوجيا قبل أن يُتاح إجراء المزيد من اختبارات بيبين في فترة زمنية معقولة. ^{[ 4 ]}

سنة	المُختبِرون	رقم فيرما	نتيجة اختبار بيبين	تم العثور على العامل لاحقًا؟
1905	مورهد وويسترن​	${\displaystyle F_{7}}$	مركب	نعم (1970)
1909	مورهد وويسترن	${\displaystyle F_{8}}$	مركب	نعم (1980)
1952	روبنسون	${\displaystyle F_{10}}$	مركب	نعم (1953)
1960	باكسون	${\displaystyle F_{13}}$	مركب	نعم (1974)
1961	سيلفريدج آند هورويتز	${\displaystyle F_{14}}$	مركب	نعم (2010)
1987	بويل ويونغ​	${\displaystyle F_{20}}$	مركب	لا
1993	كراندال ، دونياس، نوري ويونغ	${\displaystyle F_{22}}$	مركب	نعم (2010)
1999	ماير، بابادوبولوس وكراندال	${\displaystyle F_{24}}$	مركب	لا

• بي. بيبان، حول الصيغة${\displaystyle 2^{2^{n}}+1}$، Comptes rendus de l'Académie des Sciences de Paris 85 (1877)، الصفحات من  329 إلى 333.

• المعجم الرئيسي: اختبار بيبين