מבחן לוקאס-להמר למספרי מרסן
במתמטיקה, מבחן לוקאס להמר הוא מבחן ראשוניות למספרי מרסן. המבחן פותח במקור בידי אדוארד לוקאס ב-1878 ולאחר מכן שופר בידי דריק הנרי להמר בשנות ה-30 של המאה העשרים. על-שם אותם שני מתמטיקאים קרוי גם מבחן ראשוניות כללי, מבחן לוקאס-להמר.
המבחן מחשב בצורה מהירה את האיבר ה- בסדרת לוקאס ובודק האם הוא שקול ל-0 מודולו (כאשר הוא המספר שצריך לבדוק את ראשוניותו).
המבחן
[עריכת קוד מקור | עריכה]נתונים מספר ראשוני , ומספר מרסן המתאים לו, . המשימה היא לבדוק האם M ראשוני. נגדיר סדרה ברקורסיה: , ולכל מוגדר .
משפט. המספר M הוא ראשוני אם ורק אם .
זהו מבחן יעיל ביותר, והוא משמש עד היום לבדיקת ראשוניות של מספרי מרסן. החישוב מבוצע כולו מודולו M, ודורש כ- p פעולות של העלאה בריבוע מודולריות. בייצוג בינארי אלו פעולות מהירות יחסית: הריבוע האמיתי של מספר מתקבל מסיכום ההזזות שלו כלפי מעלה, וחישוב השארית מודולו M מהיר במיוחד מכיוון ש- , כך שתוצאת ההעלאה בריבוע מודולו M היא סכום שתי המחציות בריבוע שהתקבל. בסך הכול מדובר בכ- פעולות בינאריות, מהיר יותר ממבחני הראשוניות האחרים כדוגמת אלגוריתם מילר-רבין הנחשב למהיר ביותר.
תמצית הוכחת המשפט
[עריכת קוד מקור | עריכה]נסתפק כאן בסקירה של ההוכחה לכיוון אחד של המשפט: אם M ראשוני, אז .
מכיוון ש-p אי-זוגי, ולכן M הוא שארית ריבועית מודולו 3. אבל , ולכן משפט ההדדיות הריבועית מבטיח כי 3 איננו שארית ריבועית מודולו M. מכיוון שכך, סיפוח השורש הריבועי x של 3 לשדה יוצר את השדה הסופי מסדר . בשדה הזה, נסמן .
כעת קל להווכח (באינדוקציה) ש- , ובסופו של דבר אם ורק אם . מכיוון שהשדה בעל מאפיין M, מתקיים , כלומר . כדי להשלים חלק זה של ההוכחה, יש להראות שלשורש של אין, בתורו, שורש ריבועי.
הכיוון ההפוך דומה, אלא שבמקום השדה בגודל יש לחשב בשדה בגודל כאשר 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 (באנגלית)