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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] המבחן

נתונים מספר ראשוני $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.