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

בתורת המספרים, מבחן לוקאס-להמר הוא מבחן ראשוניות שעשוי להוכיח במהירות שמספר n הוא ראשוני. המבחן הוצע על ידי אדוארד לוקאס ושופר על ידי ד.ה. להמר. קיימת גם גרסה מיוחדת לבדיקת מספרי מרסן (מספרים מהצורה 2^p−1).

עיקר הרעיון נשען על משפט פרמה הקטן: אם n ראשוני ואינו מחלק את a, אז a^(n-1) ≡ 1 (מודולו n). משמעות משפט זה קשורה ל"סדר" של a בחבורת המכפלה המודולרית של n. סדר של a הוא מספר ההכפלות ב-a שנדרשות כדי לקבל 1; הפונקציה φ(n) (פונקציית אוילר) נותנת את גודל החבורה הזאת.

מבחן לוקאס-להמר ממיר את הכיוון: אם נמצא מספר a שהסדר שלו שווה בדיוק ל-n−1, אז n חייב להיות ראשוני. לכן המבחן בודק עדים (witnesses), ערכי a, ומצריך פירוק לגורמים של n−1. חסרון מרכזי הוא הצורך לדעת את פירוק n−1 מראש. כל עד שבודק את התנאים יכול להוכיח את הראשוניות, אבל כישלון של עד יחיד אינו פסיקה סופית לגבי n.

משפט: אם לכל גורם ראשוני q של n−1 קיים a כך ש-a^(n-1) ≡ 1 (מודולו n) ו-a^{(n-1)/q} ≢ 1 (מודולו n), אז n ראשוני.

הוכחה בקווים כלליים: הדרישה מבטיחה שכל חזקה ראשונית שמחלקת את n−1 גם מחלקת את φ(n). מכיוון שתמיד φ(n) ≤ n−1, זה גורר ש-φ(n)=n−1, ולכן אין שום מחלק קטן של n, ומשמע n ראשוני. הגרסה החלשה מחפשת a אחד שמתאים לכל הגורמים בו-זמנית; היא מספיקה גם היא כדי להסיק ש-ord(a)=n−1.

המשמעות המעשית: אם n באמת ראשוני, יש הרבה עדים מתאימים (כמו היוצרים של החבורה במקרה הציקלית). בשנת 2004 הראו שאפשר להגביל את בדיקת העדים לעד גודל של כ-log(n)^6; מכך נובע שהוכחת ראשוניות של n ניתנת לביצוע בסיבוכיות פולילוגריתמית (גדילה איטית יחסית).

מבחן לוקאס-להמר עוזר לבדוק אם מספר גדול הוא ראשוני. ראשוני פירושו שאין לו מחלקים חוץ מ-1 ומהמספר עצמו.

הרעיון: בוחרים מספר קטן שנקרא עד (זה מבחן לבדיקה). מבצעים חישובים מיוחדים עם העד והמספר n. אם העד ממלא את הדרישות, אז n הוא בוודאות ראשוני.

יש בעיה קטנה: צריך לדעת איך לפרק את n−1 לגורמים. פירוק זה נחוץ כדי לבחור עדים מתאימים. אם לא מוצאים עד, זה לא בהכרח אומר ש-n אינו ראשוני.

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

אם לכל מספר ראשוני q שמחלק את n−1 אפשר למצוא עד שמקיים את התנאים המתאימים, אז n ראשוני.

החלק החשוב הוא למצוא עד שמתאים. אם כן, המבחן נותן הוכחה ברורה ש-n הוא ראשוני.