Pocklington primality test

In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington^[1] and Derrick Henry Lehmer.^[2] The test uses a partial factorization of ${\displaystyle N-1}$ to prove that an integer ${\displaystyle N}$ is prime.

It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of ${\displaystyle N-1}$.

The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows:

Let ${\displaystyle N>1}$ be an integer, and suppose there exist natural numbers a and p such that

${\displaystyle a^{N-1}\equiv 1{\pmod {N}}}$

1

p is prime, ${\displaystyle p\vert N-1}$ and ${\displaystyle p>{\sqrt {N}}-1}$

2

${\displaystyle \gcd {(a^{(N-1)/p}-1,N)}=1}$

3

Then N is prime.^[3] Here ${\displaystyle i\equiv j{\pmod {k}}}$ means that after finding the remainder of division by k, i and j are equal; ${\displaystyle i\vert j}$ means that i is a divisor for j; and gcd is the greatest common divisor.

Note: Equation (1) is simply a Fermat primality test. If we find any value of a, not divisible by N, such that equation (1) is false, we may immediately conclude that N is not prime. (This divisibility condition is not explicitly stated because it is implied by equation (3).) For example, let ${\displaystyle N=35}$. With ${\displaystyle a=2}$, we find that ${\displaystyle a^{N-1}\equiv 9{\pmod {N}}}$. This is enough to prove that N is not prime.

Proof

Suppose N is not prime. This means there must be a prime q, where ${\displaystyle q\leq {\sqrt {N}}}$ that divides N. Since ${\displaystyle p>{\sqrt {N}}-1\geq q-1}$, ${\displaystyle p>q-1}$, and since p is prime, ${\displaystyle \gcd {(p,q-1)}=1}$. Thus there must exist an integer u, a multiplicative inverse of p modulo q−1, with the property that ${\displaystyle up\equiv 1{\pmod {q-1}}}$ 4 and therefore, by Fermat's little theorem ${\displaystyle a^{up}\equiv a{\pmod {q}}}$ 5 This implies ${\displaystyle 1\;\;\equiv a^{N-1}{\pmod {q}}}$,     by (1) since ${\displaystyle q\vert N}$ ${\displaystyle \equiv (a^{N-1})^{u}\equiv a^{u(N-1)}\equiv a^{up((N-1)/p)}\equiv (a^{up})^{(N-1)/p}{\pmod {q}}}$, ${\displaystyle \equiv a^{(N-1)/p}{\pmod {q}}}$,     by (5) This shows that q divides the ${\displaystyle \gcd()}$ in (3), and therefore this ${\displaystyle \gcd()\neq 1}$; a contradiction.[3]

بفرض أن N عدد أولي ، إذا أمكن إيجاد قيمتين p و a تحققان شروط النظرية، فإن N عدد أولي. علاوة على ذلك، يشكل الزوج ( p , a ) دليلاً على أولية العدد، ويمكن التحقق منه بسرعة للتأكد من استيفائه شروط النظرية، مما يؤكد أن N عدد أولي.

تكمن الصعوبة الرئيسية في إيجاد قيمة لـ p تحقق الشرط ( 2 ). أولًا، من الصعب عادةً إيجاد عامل أولي كبير لعدد كبير. ثانيًا، بالنسبة للعديد من الأعداد الأولية N ، لا توجد قيمة لـ p تحقق هذا الشرط. على سبيل المثال،${\displaystyle N=17}$لا يوجد لديه قيمة p مناسبة لأن${\displaystyle N-1=2^{4}}$، و${\displaystyle p=2<{\sqrt {N}}-1}$وهذا يخالف المتباينة في ( 2 ) ؛ ومن الأمثلة الأخرى ${\displaystyle N=19,37,41,61,71,73,}$و${\displaystyle 97}$.

بمعرفة p ، فإن إيجاد a ليس بالأمر الصعب. ^{[ 4 ]} إذا كان N عددًا أوليًا، فبحسب نظرية فيرما الصغرى، فإن أي قيمة لـ a تقع في الفترة${\displaystyle 1\leq a\leq N-1}$سيحقق ( 1 ) (ومع ذلك، الحالات${\displaystyle a=1}$و${\displaystyle a=N-1}$هذه القيم تافهة ولن تحقق الشرط ( 3 ). سيحقق هذا المتغير a الشرط ( 3 ) طالما أن ord( a ) لا يقسم${\displaystyle (N-1)/p}$وبالتالي، يتم اختيار قيمة عشوائية a في الفترة الزمنية${\displaystyle 2\leq a\leq N-2}$لديه فرصة جيدة للنجاح. إذا كان a مولدًا modulo N ، فإن رتبته هي${\displaystyle N-1}$وبالتالي فإن هذه الطريقة مضمونة النجاح لهذا الخيار.

قد يكون من المستحيل أحيانًا تطبيق الصيغة المذكورة أعلاه لنظرية بوكلينجتون لأن بعض الأعداد الأولية${\displaystyle N}$هي من النوع الذي لا يوجد فيه عدد أولي${\displaystyle p}$الفاصل${\displaystyle N-1}$أين${\displaystyle p>{\sqrt {N}}-1}$الصيغة المعممة التالية لنظرية بوكلينغتون قابلة للتطبيق على نطاق أوسع. ^{[ 5 ] : النتيجة 1}

نظرية: حلل العدد N − 1   إلى N − 1 = AB    ، حيث A و B عددان أوليان فيما بينهما.${\displaystyle A>{\sqrt {N}}}$، إن التحليل الأولي لـ A معروف، لكن تحليل B ليس معروفًا بالضرورة.

إذا كان لكل عامل أولي p من A يوجد عدد صحيح${\displaystyle a_{p}}$لهذا السبب.

${\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}}$، و

6

${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=1}$،

7

إذن ، N عدد أولي.

تُقدّم ورقة بريلهارت وليمر وسيلفريدج ^{[ 5 ]} المنشورة عام 1975 برهانًا لما هو موضح أعلاه باسم "نظرية بوكلينغتون المعممة" في النظرية 4 في الصفحة 623. كما تُعرض نظريات إضافية تسمح بتحليل أقل، بما في ذلك نظريتهم 3 (وهي تعزيز لنظرية بروث التي نُشرت عام 1878).

يترك${\displaystyle N-1=mp}$حيث p عدد أولي فردي بحيث${\displaystyle 2p+1>{\sqrt {N}}}$إذا وُجدت قيمة a بحيث يكون${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}}$، لكن${\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}}$إذن، N عدد أولي.

إذا كانت قيمة N كبيرة، فغالباً ما يكون من الصعب تحديد عامل كافٍ من${\displaystyle N-1}$لتطبيق النتيجة المذكورة أعلاه. تسمح النظرية 5 من ورقة بريلهارت، ليمر، وسيلفريدج بإثبات أولية العدد عندما يصل الجزء المُحلل إلى 1000 فقط.${\displaystyle (N/2)^{1/3}}$. يتم تقديم العديد من النظريات الإضافية التي تسمح بإثبات أولية العدد N بناءً على التحليل الجزئي لـ${\displaystyle N-1}$،${\displaystyle N+1}$،${\displaystyle N^{2}+1}$، و${\displaystyle N^{2}\pm N+1}$[ ^{5 ] [ 6 ] [ 7 ]​}

• ليونارد يوجين ديكسون، "تاريخ نظرية الأعداد"، المجلد 1، صفحة 370، دار نشر تشيلسي 1952
• هنري بوكلينجتون، "Math. Quest. Educat. Times"، (2)، 25، 1914، ص 43-46 (أسئلة وحلول رياضية استكمالاً للأعمدة الرياضية في "the Educational times".)

• كريس كالدويل، "إثبات البدائية 3.1: اختبارات n-1 واختبارات بيبين لفيرمات" في الصفحات الرئيسية .
• كريس كالدويل، "إثبات الأعداد الأولية 3.2: اختبارات n+1 واختبار لوكاس-ليمر لميرسين" في الصفحات الرئيسية .