מספר פסאודו-ראשוני – הבדלי גרסאות

אין שינוי בגודל ,  לפני 9 שנים
מ
הגהה
מ (הגהה)
עיסוק מרכזי בתורת המספרים, בעל השלכות רבות ל[[קריפטוגרפיה]], הוא חקר [[מבחן ראשוניות|מבחני ראשוניות]] הבודקים האם מספר נתון הוא ראשוני או פריק. מבחני ראשוניות רבים בוחנים תכונה המתקיימת בכל הראשוניים, אך ייתכן גם שהיא מתקיימת במספרים פריקים מסוימים. אם מספר כלשהו לא מקיים תכונה שכזו, הוא בהכרח פריק, אך אם מתגלה שמספר מסוים מקיים את התכונה, אין ודאות אם הוא ראשוני או פסאודו-ראשוני ביחס לתכונה. מבחן ראשוניות יעיל הוא מבחן ששכיחות המספרים הפסאודו-ראשוניים ביחס אליו נמוכה.
 
ישנם מבחני ראשוניות, כגון [[מבחן AKS]], שמזהים ראשוני בוודאות מוחלטת ואין מספר פסאודו-ראשוניים ביחס אליהם. אםעם זאת, לצרכים מעשיים מעדיפים את השימוש במבחנים מהירים יותר, כגון [[אלגוריתם מילר-רבין]], שיש סיכוי שיזהו כראשוני מספר שהוא פסאודו-ראשוני, אך ניתן להקטין את הסיכוי הזה באופן בלתי מוגבל.
 
==פסאודו-ראשוני פרמה==
39

עריכות