מבחן לוקאס-להמר למספרי מרסן

במתמטיקה, מבחן לוקאס להמר הוא מבחן ראשוניות למספרי מרסן. המבחן פותח במקור בידי אדוארד לוקאס ב-1878 ולאחר מכן שופר בידי דריק הנרי להמר בשנות ה-30 של המאה העשרים. על-שם אותם שני מתמטיקאים קרוי גם מבחן ראשוניות כללי, מבחן לוקאס-להמר.

המבחן מחשב בצורה מהירה את האיבר ה- $2^{p-2}$ בסדרת לוקאס $V(4,1)$ ובודק האם הוא שקול ל-0 מודולו $M$ (כאשר $M=2^{p}-1$ הוא המספר שצריך לבדוק את ראשוניותו).

המבחן עריכה

נתונים מספר ראשוני $2<p$ , ומספר מרסן המתאים לו, $\ M=2^{p}-1$ . המשימה היא לבדוק האם M ראשוני. נגדיר סדרה $\ s_{i}$ ברקורסיה: $\ s_{0}=4$ , ולכל $\ i>0$ מוגדר $\ s_{i}=s_{i-1}^{2}-2$ .

משפט. המספר M הוא ראשוני אם ורק אם $\ s_{p-2}\equiv 0{\pmod {M}}$ .

זהו מבחן יעיל ביותר, והוא משמש עד היום לבדיקת ראשוניות של מספרי מרסן. החישוב מבוצע כולו מודולו M, ודורש כ- p פעולות של העלאה בריבוע מודולריות. בייצוג בינארי אלו פעולות מהירות יחסית: הריבוע האמיתי של מספר מתקבל מסיכום ההזזות שלו כלפי מעלה, וחישוב השארית מודולו M מהיר במיוחד מכיוון ש- $\ 2^{p}\equiv 1{\pmod {M}}$ , כך שתוצאת ההעלאה בריבוע מודולו M היא סכום שתי המחציות בריבוע שהתקבל. בסך הכול מדובר בכ- $\ p^{3}\approx (\log(M))^{3}$ פעולות בינאריות, מהיר יותר ממבחני הראשוניות האחרים כדוגמת אלגוריתם מילר-רבין הנחשב למהיר ביותר.

תמצית הוכחת המשפט עריכה

נסתפק כאן בסקירה של ההוכחה לכיוון אחד של המשפט: אם M ראשוני, אז $\ s_{p-2}\equiv 0{\pmod {M}}$ .

מכיוון ש-p אי-זוגי, $\ 2^{p}-1\equiv 1{\pmod {3}}$ ולכן M הוא שארית ריבועית מודולו 3. אבל $\ M\equiv -1{\pmod {4}}$ , ולכן משפט ההדדיות הריבועית מבטיח כי 3 איננו שארית ריבועית מודולו M. מכיוון שכך, סיפוח השורש הריבועי x של 3 לשדה $\ \mathbb {Z} /M\mathbb {Z}$ יוצר את השדה הסופי מסדר $\ M^{2}$ . בשדה הזה, נסמן $\ \alpha =2+x$ .

כעת קל להווכח (באינדוקציה) ש- $\ s_{i}=\alpha ^{2^{i}}+\alpha ^{-2^{i}}$ , ובסופו של דבר $\ s_{p-2}=0$ אם ורק אם $\ \alpha ^{2^{p-1}}=\alpha ^{\frac {M+1}{2}}=-1$ . מכיוון שהשדה בעל מאפיין M, מתקיים $\ \alpha ^{M}=2^{M}+x^{M}=2+3^{\frac {M-1}{2}}x=2-x=\alpha ^{-1}$ , כלומר $\ \alpha ^{\frac {M+1}{2}}=\pm 1$ . כדי להשלים חלק זה של ההוכחה, יש להראות שלשורש $\ 2^{-{\frac {3M-1}{4}}}(1+x)$ של $\ \alpha$ אין, בתורו, שורש ריבועי.

הכיוון ההפוך דומה, אלא שבמקום השדה בגודל $\ M^{2}$ יש לחשב בשדה בגודל $\ Q^{2}$ כאשר Q הוא גורם ראשוני של M שעבורו 3 איננו שארית ריבועית.

ראו גם עריכה

מבחן לוקאס-להמר הכללי

לקריאה נוספת עריכה

Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0387947779. Section 4.2.1: The Lucas-Lehmer test, pp.167–170.

קישורים חיצוניים עריכה

מבחן לוקאס-להמר למספרי מרסן, באתר MathWorld (באנגלית)