מספר פסאודו-ראשוני

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

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

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

פסאודו-ראשוני פרמה

הסוג המוכר ביותר של מספרים פסאודו-ראשוניים הם המספרים הפריקים המקיימים את המשפט הקטן של פרמה. מספר פריק ${\displaystyle n}$ נקרא פסאודו-ראשוני פרמה בבסיס a אם מתקיים ${\displaystyle n\mid a^{n}-a}$ (n מחלק את aⁿ-a). מספר שהוא פסאודו-ראשוני פרמה בכל בסיס נקרא פסאודו-ראשוני פרמה מוחלט או מספר קרמייקל. הדוגמה הקטנה ביותר למספר כזה היא 561.

פסאודו-ראשוני פרמה בבסיס 2

כבר במאה ה-6 לפנה"ס שיערו מתמטיקאים סינים ש-${\displaystyle n}$ ראשוני אם ורק אם ${\displaystyle n\mid 2^{n}-2}$. ב-1819 נתגלתה הדוגמה הנגדית הקטנה ביותר: ${\displaystyle 341\mid 2^{341}-2}$, על אף ש-${\displaystyle 11\cdot 31=341}$ הוא מספר פריק.

אם ${\displaystyle p}$ ראשוני, ומספר מרסן ${\displaystyle M_{p}=2^{p}-1}$ פריק, אז ${\displaystyle M_{p}}$ הוא פסאודו-ראשוני בבסיס 2. כמו כן כל מספר פרמה פריק הוא גם כן פסאודו-ראשוני בבסיס 2.

לא קשה לבנות סדרה אינסופית עולה של פסאודו-ראשוניים בבסיס 2. אם ${\displaystyle n}$ מספר פסאודו-ראשוני בבסיס 2, אז גם ${\displaystyle M_{n}}$ כזה. כדי לראות זאת נשתמש בתכונה בסיסית של מספרי מרסן, שאם ${\displaystyle k\mid n}$, אז ${\displaystyle M_{k}\mid M_{n}}$. ${\displaystyle n}$ פריק ולכן קיים ${\displaystyle k\mid n}$ לא טריוויאלי. מכאן ש-${\displaystyle M_{k}\mid M_{n}}$ ו-${\displaystyle M_{n}}$ פריק. כמו כן מכך ש-${\displaystyle n}$ פסאודו-ראשוני נובע שקיים ${\displaystyle r}$ כך ש-${\displaystyle rn=2^{n}-2}$, ולכן ${\displaystyle 2^{M_{n}}-2=2^{rn+1}-2=2M_{rn}}$. כלומר ${\displaystyle M_{n}\mid 2M_{rn}=2^{M_{n}}-2}$ כנדרש.

קישורים חיצוניים

• מספר פסאודו-ראשוני, באתר MathWorld (באנגלית)
• מספר פסאודו-ראשוני, באתר אנציקלופדיה בריטניקה (באנגלית)

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.