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