מבחן לוקאס-להמר למספרי מרסן
במתמטיקה, מבחן לוקאס להמר הוא מבחן ראשוניות למספרי מרסן. המבחן פותח במקור בידי אדוארד לוקאס ב-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. מסת"ב 0387947779. Section 4.2.1: The Lucas-Lehmer test, pp.167–170.
קישורים חיצוניים
- מבחן לוקאס-להמר למספרי מרסן, באתר MathWorld (באנגלית)
מבחן לוקאס-להמר למספרי מרסן29910806Q1138992