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

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

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

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

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

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

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

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

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

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

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

• מספר פסאודו-ראשוני, באתר MathWorld (באנגלית)   
• 
  שגיאות פרמטריות בתבנית:בריטניקה
  פרמטרי חובה [ 1 ] חסרים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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