اختبار لوكاس-ليهمر لأولية عدد ما

هذا المقال يتعلق باختبار لوكاس-ليهمر الذي ينطبق على أعداد ميرسين فقط. من أجل اختبار لوكاس-ليهمر الذي ينطبق على عدد طبيعي ما أيا كان، المرجو النظر إلى اختبار لوكاس لأولية عدد ما. من أجل اختبار لوكاس-ليهمر-غيزل، المرجو النظر إلى اختبار لوكاس-ليهمر-غيزل.

في الرياضيات، اختبار لوكاس ليهمر هو اختبار أولية أعداد ميرسين.[1] اخترع هذا الاختبار من طرف إدوارد لوكاس عام 1856، فطوره لوكاس نفسه عام 1878، كما طوره أيضا ديريك هنري ليهمر في ثلاثينات القرن العشرين.

الاختبار

يعمل اختبار لوكاس-ليهمر كما يلي. ليكن M_p = 2^p − 1 عدد ميرسن حيث p عدد أولي فردي. لنعرف المتتالية $\{s_{i}\}$ كما يلي حيث i عدد طبيعي أكبر من الصفر:

s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}

الحدود الأولى القليلة من هذه المتتالية هن 4، 14، 194، 37634، ...(انظر إلى موسوعة المتتاليات الصحيحة على الإنترنت). يكون العدد M_p أوليا إذا وفقط إذا توفر ما يلي :

s_{p-2}\equiv 0{\pmod {M_{p}}}

يسمى العدد s_p − 2 mod M_p باقي لوكاس-ليهمر للعدد p.

أمثلة

عدد ميرسن M₃ = 2³−1 = 7 أولي. اختبار لوكاس-ليهمر يتحقق من ذلك كما يلي. بدايةً، تُعطى القيمة 4 للمتغير s. وبعد ذلك تُغير قيمته. 3−2 = 1 مرةً:

s ← ((4 × 4) − 2) mod 7 = 0.

بما أن القيمة النهائية ل s هي الصفر، فإن الاستنتاج هو أن M₃ أولي.

من ناحية أخرى، M₁₁ = 2047 = 23 × 89 عدد غير أولي. مجددا، تُعطى القيمة أربعة ل s. ولكن قيمته تُبدل 11−2 = 9 مرةً :

s ← ((4 × 4) − 2) mod 2047 = 14
s ← ((14 × 14) − 2) mod 2047 = 194
s ← ((194 × 194) − 2) mod 2047 = 788
s ← ((788 × 788) − 2) mod 2047 = 701
s ← ((701 × 701) − 2) mod 2047 = 119
s ← ((119 × 119) − 2) mod 2047 = 1877
s ← ((1877 × 1877) − 2) mod 2047 = 240
s ← ((240 × 240) − 2) mod 2047 = 282
s ← ((282 × 282) − 2) mod 2047 = 1736

بما أن القيمة النهائية ل s لا تساوي الصفر، الاستنتاج هو M₁₁ = 2047 عدد ليس بأولي. رغم أن M₁₁ = 2047 لا يملك معاملات بديهية، اختبار لوكاس-ليهمر لا يعطي أي إشارة إلى قيمة هذه العوامل.

البرهان على الصحة

برهان الصحة المقدم هنا أبسط من البرهان الأصلي الذي جاء به ليهمر. تذكر التعريف

s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}

الهدف هو البرهان على أن M_p أولي إذا وفقط إذا توفر $s_{p-2}\equiv 0{\pmod {M_{p}}}.$

المتتالية ${\langle }s_{i}{\rangle }$ معرفة بعلاقة استدعاء ذاتي يمكن تعريفها بتعبير منغلق الشكل. ليكن $\omega =2+{\sqrt {3}}$ و ${\bar {\omega }}=2-{\sqrt {3}}$ . يأتي من ذلك باستعمال البرهان بالترجح ما يلي: أن $s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}$ لجميع قيم i:

s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=\left(2+{\sqrt {3}}\right)+\left(2-{\sqrt {3}}\right)=4

و

{\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}.\end{aligned}}

المرحلة الأخيرة تستعمل $\omega {\bar {\omega }}=\left(2+{\sqrt {3}}\right)\left(2-{\sqrt {3}}\right)=1.$ هذه الصيغة المغلقة مستعملة في كل من البرهان على كونه كافيا وفي البرهان على كونه ضروريا.

كونه كافيا

الهدف هو البرهان على أن $s_{p-2}\equiv 0{\pmod {M_{p}}}$ تؤدي إلى $M_{p}$ أوليا. فيما يلي برهان يستعمل نظرية الزمر الابتدائية، جاء به J. W. Bruce[2] كما شهد بذلك Jason Wojciechowski.[3]

افترض أن $s_{p-2}\equiv 0{\pmod {M_{p}}}.$ إذن،

\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}

حيث k عدد صحيح ما. إذن،

\omega ^{2^{p-2}}=kM_{p}-{\bar {\omega }}^{2^{p-2}}.

ضرب الحدين في $\omega ^{2^{p-2}}$ يعطي :

\left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}.

إذن،

\omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)

من أجل الوصول إلى تناقض، , يفترض أن M_p هو عدد مركب (أي غير أولي), وليكن q أصغر القواسم الأولية ل M_p. أعداد ميرسن فردية , إذن، q > 2. ,[note 1] لتكن $\mathbb {Z} _{q}$ مجموعة الأعداد الصحيحة بتردد q, لتكن $X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.$ الضرب في $X$ معرف كما يلي

\left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=[(ac+3bd)\,{\bmod {\,}}q]+{\sqrt {3}}[(ad+bc)\,{\bmod {\,}}q].

يبدو بشكل واضح أن عملية الضرب مغلقة، أي أن جداء عددين ينتميان إلى المجموعة X هو بذاته ينتمي إلى X. يرمز إلى عدد عناصر المجموعة X ب $|X|.$

بما أن q > 2, فإن $\omega$ و ${\bar {\omega }}$ هي في X.[note 2] المجموعة الجزئية من X المكونة من العناصر التي تملك عنصرا معاكسا، تكون زمرة، يرمز إليها ب X*، ويرمز إلى عدد عناصرها ب $|X^{*}|$ .

عنصر من X والذي لا يملك عنصرا معاكسا هو 0, إذن، $|X^{*}|\leq |X|-1=q^{2}-1.$

حاليا $M_{p}\equiv 0{\pmod {q}}$ and $\omega \in X$ , إذن،

kM_{p}\omega ^{2^{p-2}}=0

in X. إذن، من خلال المعادلة (1),

\omega ^{2^{p-1}}=-1

في X, رفع كلا الحدين إلى المربع يعطي ما يلي:

\omega ^{2^{p}}=1.

إذن، $\omega$ هو موجود في X* وله عنصر معاكس $\omega ^{2^{p}-1}.$ أضف إلى ذلك, the رتبة of $\omega$ يقسم $2^{p}.$ ولكن $\omega ^{2^{p-1}}\neq 1$ , إذن، الرتبة لا تقسم $2^{p-1}.$ إذن، الرتبة هي بالتحديد $2^{p}.$

رتبة عنصر في زمرة تساوي على الأكثر عدد عانصر تلك الزمرة. إذن،

2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.

ولكن q هو أصغر عامل أولي من بين الأعداد الأولية اللائي يشكلن تفكيك $M_{p}$ إلى جداء عوامل أولية. إذن،

q^{2}\leq M_{p}=2^{p}-1.

هذا يؤدي إلى التناقض $2^{p}<2^{p}-1$ . إذن, $M_{p}$ أولي.

تطبيقات

يستعمل اختبار لوكاس-ليهمر لأولية عدد ما البحث الكبير عن أعداد ميرسين الأولية في الإنترنت من أجل البحث عن الأعداد الأولية الكبيرة. انظر إلى أعداد فيرما.

انظر أيضا

البحث الكبير عن أعداد ميرسين الأولية في الإنترنت.

ملاحظات

Formally, لتكن $\mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z}$ and $X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle$ .
Formally, $\omega +\langle T^{2}-3\rangle$ and ${\bar {\omega }}+\langle T^{2}-3\rangle$ are in X. By abuse of language $\omega$ and ${\bar {\omega }}$ are identified with their images in X under the natural ring homomorphism from $\mathbb {Z} [{\sqrt {3}}]$ to X which sends ${\sqrt {3}}$ to T.

مراجع

"معلومات عن اختبار لوكاس-ليهمر لأولية عدد ما على موقع mathworld.wolfram.com"، mathworld.wolfram.com، مؤرشف من الأصل في 16 يوليو 2019.
Bruce, J. W. (1993)، "A Really Trivial Proof of the Lucas–Lehmer Test"، The American Mathematical Monthly، 100 (4): 370–371، doi:10.2307/2324959.
Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.

وصلات خارجية

بوابة رياضيات
بوابة نظرية الأعداد

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[4] Formally, لتكن $\mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z}$ and $X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle$ .

[5] Formally, $\omega +\langle T^{2}-3\rangle$ and ${\bar {\omega }}+\langle T^{2}-3\rangle$ are in X. By abuse of language $\omega$ and ${\bar {\omega }}$ are identified with their images in X under the natural ring homomorphism from $\mathbb {Z} [{\sqrt {3}}]$ to X which sends ${\sqrt {3}}$ to T.

[1] "معلومات عن اختبار لوكاس-ليهمر لأولية عدد ما على موقع mathworld.wolfram.com"، mathworld.wolfram.com، مؤرشف من الأصل في 16 يوليو 2019.

[2] Bruce, J. W. (1993)، "A Really Trivial Proof of the Lucas–Lehmer Test"، The American Mathematical Monthly، 100 (4): 370–371، doi:10.2307/2324959.

[3] Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.

خوارزميات نظرية الأعداد
اختبارا ت أولية عدد ما	اختبار أ.ك.أس APR test Baillie–PSW ECPP test المنحنيات الإهليلجية بوكلينغتن فيرما لوكاس لوكاس-ليهمر Lucas–Lehmer–Riesel مبرهنة بروث Pépin's اختبار فروبنيوس التربيعي Solovay–Strassen ميلر-رابن
توليد الأعداد الأولية	غربال أتكين غربال إراتوستينس غربال صوندارام Wheel factorization
تحليل عدد صحيح إلى عوامل	Continued fraction (CFRAC) Dixon's منحنى لنسترا الإهليلجي أويلر Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) غربال جذري عدد أولي Shanks' square forms قسمة متكررة شوور
حساب الجداء	الطريقة المصرية القديمة Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
خوارزمية متقطعة	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
قاسم مشترك أكبر	Binary أقليدس إقليدس الممددة ليهمر
Modular square root	Cipolla Pocklington's Tonelli–Shanks
خوارزميات أخرى	Chakravala Cornacchia Integer relation جذر تربيعي صحيح Modular exponentiation Schoof's
الخط المائل يدل على أن الخوارزمية قابلة للاستعمال عند أعداد تأخذ أشكال خاصة. Smallcaps يدل على خوارزمية قطعية