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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

במתמטיקה, מבחן לוקאס להמר הוא מבחן ראשוניות למספרי מרסן. המבחן פותח במקור בידי אדוארד לוקאס ב-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.

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

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

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