מבחן סולוביי-שטרסן

מבחן סולוביי-שטרסן לבדיקת ראשוניות פותח בשנת 1977 על-ידי המתמטיקאי הגרמני וולקר שטראסן והמתמטיקאי האמריקאי רוברט מ. סולוביי. זהו מבחן הסתברותי שקובע אם מספר טבעי הוא פריק או כנראה ראשוני. הרעיון מאחורי מבחן זה התגלה על ידי מ.מ. ארטיחוב בשנת 1967. מבחן זה הוחלף במידה רבה על ידי מבחן הראשוניות של Baillie–PSW ומבחן הראשוניות של מילר–רבין, אך יש לו חשיבות היסטורית רבה בהצגת ההיתכנות המעשית של מערכת ההצפנה RSA. מבחן סולוביי-שטרסן הוא בעצם מבחן קרוב לוודאי ראשוני של אוילר–יעקובי.

מושגים

אוילר הוכיח שלכל מספר ראשוני p אי-זוגי ולכל שלם a מתקיים:

$a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$

כאשר $\left({\tfrac {a}{p}}\right)$ הוא סימן לז'נדר.

סימן יעקובי הוא הכללה של סימן לז'נדר ל- $\left({\tfrac {a}{n}}\right)$, כאשר n יכול להיות כל מספר שלם אי-זוגי.

בהינתן מספר אי-זוגי n, ניתן לחשוב אם המשוואה המודולרית

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

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

לכל n אי-זוגי פריק לפחות חצי מכל הבסיסים

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

הם עדי אוילר. למשל עבור n=65 הקבוצה של עדי אוילר שקרנים היא $\{1,8,14,18,47,51,57,64\}$ ולקבוצה $(\mathbb {Z} /n\mathbb {Z} )^{*}$ יש סדר 48.

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

דוגמה

נניח שאנו רוצים לקבוע אם n=221 הוא ראשוני. נבחר באופן אקראי a=47 שהוא גדול מ-1 וקטן מ־n. נשתמש בשיטה יעילה להעלאת מספר בחזקה (מודולו n), למשל באקספוננציה בינארית. נחשב:

* a^(n−1)/2 mod n  =  47¹¹⁰ mod 221  =  −1 mod 221

* mod n  =  $({\tfrac {47}{221}})$ mod 221  =  −1 mod 221 $({\tfrac {a}{n}})$

מכאן ש- 221 הוא מספר ראשוני או ש- 47 הוא עד אוילר שקרן ל־221. ננסה a אקראי נוסף, הפעם נבחר a=2. נחשב:

* a^(n−1)/2 mod n  =  2¹¹⁰ mod 221  =  30 mod 221

* mod n  =  $({\tfrac {2}{221}})$ mod 221  =  −1 mod 221 $({\tfrac {a}{n}})$

כלומר 2 הוא עד אוילר לפריקות של 221 ו־47 הוא למעשה עד אוילר שקרן. נשים לב שזה לא אומר דבר על הגורמים הראשוניים של 221 שהם בעצם 13 ו־17.

אלגוריתם וזמן ריצה

ניתן לרשום את האלגוריתם בפסוואדו-קוד באופן הבא:

קלטים: n, מספר טבעי לצורך בדיקה אם הוא ראשוני או פריק.
      k, פרמטר שקובע את מידת הדיוק של הבדיקה.
פלטים: פריק אם n פריק, אחרת כנראה ראשוני.

חזור k פעמים:
    בחר a אקראי מבין [2,n − 1]
    $x\gets \left({\tfrac {a}{n}}\right)$
    אם x = 0 או $a^{(n-1)/2}\not \equiv x{\pmod {n}}$ אז 
        החזר פריק
החזר כנראה ראשוני

כשמשתמשים באלגוריתמים מהירים לצורך חישוב חזקות מודולריות, זמן הריצה של האלגוריתם הזה הוא O(k·log³ n), כאשר k הוא מספר הערכים השונים של a שאנו בודקים.

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

• Solovay-Strassen - מימוש של מבחן סולוביי-שטרסן לבדיקת ראשוניות במייפל.