מבחן לוקאס-להמר
מבחן לוקאס-להמר עוזר לבדוק אם מספר גדול הוא ראשוני. ראשוני פירושו שאין לו מחלקים חוץ מ-1 ומהמספר עצמו. הרעיון: בוחרים מספר קטן שנקרא עד (זה מבחן לבדיקה). מבצעים חישובים מיוחדים עם העד והמספר n. אם העד ממלא את הדרישות, אז n הוא בוודאות ראשוני. יש בעיה קטנה: צריך לדעת איך לפרק את n−1 לגורמים. פירוק ...
מבחן לוקאס-להמר למספרי מרסן
מבחן לוקאס‑להמר בודק מספרים מיוחדים שנקראים מספרי מרסן. מספר מרסן מקבלים כך: עושים 2 בחזקת p ואז מורידים 1. מתחילים סדרה שמתחילה ב‑4. כל איבר הבא הוא הריבוע של הקודם פחות 2. בודקים את האיבר במקום p-2. אם האיבר הזה מתחלק ב‑M (אין שארית), אז M הוא מספר ראשוני. זה אומר שאי אפשר לחלק אותו במספרים אחר...