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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

פסאודו-ראשוני פרמה[עריכת קוד מקור | עריכה]

הסוג המוכר ביותר של מספרים פסאודו-ראשוניים הם המספרים הפריקים המקיימים את המשפט הקטן של פרמה. מספר פריק n נקרא פסאודו-ראשוני פרמה בבסיס a אם מתקיים n \mid a^n - a (n מחלק את an-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 כנדרש.

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