מבחן לוקאס‑להמר בודק את ראשוניותם של מספרי מרסן. מספר מרסן הוא מספר מהצורה 2 בחזקת p פחות 1, כאשר p הוא מספר ראשוני. המבחן הוצע על־ידי אדוארד לוקאס ב‑1878 ושופר בשנות ה‑30 על־ידי דריק להמר.
נגדיר סדרה s_0 = 4, ולכל i>0: s_i = s_{i-1}^2 - 2. נבחן את האיבר s_{p-2}. המספר M=2^p-1 הוא ראשוני אם ורק אם s_{p-2} שווה ל‑0 מודולו M. מודולו משמעותו שארית חלוקה ב‑M.
החישוב מבוצע כולו עם שאריות מודולו M. זה מאפשר לבצע העלאות בריבוע מהירות בבינארי, כי 2^p שווה ל‑1 מודולו M. לכן מספיק כ‑p פעולות של הרבעות מודולריות, ובסך הכל כ‑p^3 ≈ (log M)^3 פעולות בינאריות. מבחן זה יעיל והוא בשימוש לבדיקת מספרי מרסן. לעיתים הוא מהיר יותר ממבחנים אחרים, כגון אלגוריתם מילר‑רבין.
הוכחה קצרה לכיוון אחד: אם M ראשוני, אז s_{p-2} ≡ 0 (מודולו M). כדי להראות זאת בונים שדה סופי המתקבל מסיפוח שורש ריבועי של 3 למעגל השאריות מודולו M. מסמנים α = 2 + x, כאשר x הוא שורש ריבועי של 3.
באינדוקציה מראים ש‑s_i = α^{2^i} + α^{-2^i}. לכן s_{p-2} = 0 בדיוק כש‑α^{2^{p-1}} = -1. בתכונות השדה הסופי מגלים ש‑α^{(M+1)/2} = ±1, ומשם מסיימים את הטיעון על ידי בחינת אפשרויות הכפל והשורש הריבועי המתאימים.
הכיוון ההפוך דומה, אך משתמש בשדה שנבנה מעל גורם ראשוני Q של M.
מבחן לוקאס‑להמר בודק מספרים מיוחדים שנקראים מספרי מרסן. מספר מרסן מקבלים כך: עושים 2 בחזקת p ואז מורידים 1.
מתחילים סדרה שמתחילה ב‑4. כל איבר הבא הוא הריבוע של הקודם פחות 2. בודקים את האיבר במקום p-2.
אם האיבר הזה מתחלק ב‑M (אין שארית), אז M הוא מספר ראשוני. זה אומר שאי אפשר לחלק אותו במספרים אחרים חוץ מ‑1 ובו עצמו.
מבחן זה מהיר יחסית ונהוג להשתמש בו לבדיקת מספרים גדולים. המבחן נקרא על שם לוקאס ולשם להמר.
תגובות גולשים