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

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

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

המבחן

נתונים מספר ראשוני $p>2$ ומספר מרסן המתאים לו $M=2^p-1$. המשימה היא לבדוק האם $M$ ראשוני. נגדיר סדרה ברקורסיה: $s_i=\{\begin{array}{l}{s}_0=4\\ s_i=s_{i-1}^2-2\end{array}$

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

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

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

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

מכיוון ש־$p$ אי־זוגי, $2^p-1\equiv 1(\mathrm{mod}3)$ ולכן $M$ הוא שארית ריבועית מודולו 3. אבל $M\equiv -1(\mathrm{mod}4)$, ולכן משפט ההדדיות הריבועית מבטיח כי 3 איננו שארית ריבועית מודולו $M$. מכיוון שכך, סיפוח השורש הריבועי $x$ של 3 לשדה $\mathbb{\mathbb{Z}}/M\mathbb{\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. מסת"ב 0387947779. Section 4.2.1: The Lucas-Lehmer test, pp.167–170.

קישורים חיצוניים

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

• GIMPS (The Great Internet Mersenne Prime Search)
• A proof of Lucas-Lehmer test

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0