מספר פסאודו-ראשוני
בתורת המספרים, מספר פסאודו-ראשוני הוא מספר פריק החולק תכונה כלשהי עם כל המספרים הראשוניים.
עיסוק מרכזי בתורת המספרים, בעל השלכות רבות לקריפטוגרפיה, הוא חקר מבחני ראשוניות הבודקים האם מספר נתון הוא ראשוני או פריק. מבחני ראשוניות רבים בוחנים תכונה המתקיימת בכל הראשוניים, אך ייתכן גם שהיא מתקיימת במספרים פריקים מסוימים. אם מספר כלשהו לא מקיים תכונה שכזו, הוא בהכרח פריק, אך אם מתגלה שמספר מסוים מקיים את התכונה, אין ודאות אם הוא ראשוני או פסאודו-ראשוני ביחס לתכונה. מבחן ראשוניות יעיל הוא מבחן ששכיחות המספרים הפסאודו-ראשוניים ביחס אליו נמוכה.
ישנם מבחני ראשוניות, כגון מבחן AKS, שמזהים ראשוני בוודאות מוחלטת ואין מספר פסאודו-ראשוניים ביחס אליהם. עם זאת, לצרכים מעשיים מעדיפים את השימוש במבחנים מהירים יותר, כגון אלגוריתם מילר-רבין, שיש סיכוי שיזהו כראשוני מספר שהוא פסאודו-ראשוני, אך ניתן להקטין את הסיכוי הזה באופן בלתי מוגבל.
פסאודו-ראשוני פרמה
[עריכת קוד מקור | עריכה]הסוג המוכר ביותר של מספרים פסאודו-ראשוניים הם המספרים הפריקים המקיימים את המשפט הקטן של פרמה. מספר פריק נקרא פסאודו-ראשוני פרמה בבסיס a אם מתקיים (n מחלק את an-a). מספר שהוא פסאודו-ראשוני פרמה בכל בסיס נקרא פסאודו-ראשוני פרמה מוחלט או מספר קרמייקל. הדוגמה הקטנה ביותר למספר כזה היא 561.
פסאודו-ראשוני פרמה בבסיס 2
[עריכת קוד מקור | עריכה]כבר במאה ה-6 לפנה"ס שיערו מתמטיקאים סינים ש- ראשוני אם ורק אם . ב-1819 נתגלתה הדוגמה הנגדית הקטנה ביותר: , על אף ש- הוא מספר פריק.
אם ראשוני, ומספר מרסן פריק, אז הוא פסאודו-ראשוני בבסיס 2. כמו כן כל מספר פרמה פריק הוא גם כן פסאודו-ראשוני בבסיס 2.
לא קשה לבנות סדרה אינסופית עולה של פסאודו-ראשוניים בבסיס 2. אם מספר פסאודו-ראשוני בבסיס 2, אז גם כזה. כדי לראות זאת נשתמש בתכונה בסיסית של מספרי מרסן, שאם , אז . פריק ולכן קיים לא טריוויאלי. מכאן ש- ו- פריק. כמו כן מכך ש- פסאודו-ראשוני נובע שקיים כך ש-, ולכן . כלומר כנדרש.
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- מספר פסאודו-ראשוני, באתר MathWorld (באנגלית)
- מספר פסאודו-ראשוני, באתר אנציקלופדיה בריטניקה (באנגלית)