איך לבנות מספר ראשוני גדול | מגזין קוונטה

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

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

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

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

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

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

הגישה השנייה היא ללכת עם אלגוריתם דטרמיניסטי. אתה יכול לבחור נקודת התחלה ולהתחיל לבדוק מספרים, ברצף, עבור ראשוניות. בסופו של דבר נגזר עליך למצוא אחד, והאלגוריתם שלך יוציא באופן עקבי את הראשון שתמצא. אבל זה יכול לקחת זמן מה: אם אתה מחפש מספר ראשוני עם 1,000 ספרות, אפילו חישוב עם 2⁵⁰⁰ צעדים - שייקחו הרבה יותר מגיל היקום - אינם מספיקים כדי להבטיח הצלחה.

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

מגבלת זמן זו ידועה כזמן פולינומי. אלגוריתם פותר בעיה בזמן פולינום אם מספר הצעדים שהוא לוקח הוא לא יותר מפונקציה פולינומית של n, גודל הקלט. (פונקציה פולינומית כוללת מונחים בעלי משתנים המועלים לחזקות שלמים חיוביים, כמו n² או 4n³.) בהקשר של בניית מספרים ראשוניים, n מתייחס למספר הספרות בראש הרצוי. מבחינה חישובית, זה לא עולה הרבה: מדעני מחשב מתארים בעיות שניתן לפתור על ידי אלגוריתמים בזמן פולינום כקלות. בעיה קשה, לעומת זאת, לוקחת זמן אקספוננציאלי, מה שאומר שהיא דורשת מספר שלבים בקירוב על ידי פונקציה מעריכית (הכוללת מונחים כמו 2ⁿ).

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

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

חוקרים חוקרים מאז אלגוריתמים פסאודו-דטרמיניסטים. בשנת 2017, סנטהנם ואיגור אוליביירה מאוניברסיטת וורוויק (שגם תרמו לעבודה החדשה) מְתוּאָר גישה פסאודו-דטרמיניסטית לבניית ראשוניים שהשתמשו באקראיות ונראתה דטרמיניסטית משכנעת, אבל היא עבדה בזמן "תת-מעריכי" - מהר יותר מהאקספוננציאלי, אבל איטי יותר מהזמן הפולינומי. ואז בשנת 2021, Tell and ליג'י צ'ן, מדען מחשבים באוניברסיטת קליפורניה, ברקלי, נחקרו כיצד להשתמש בבעיה קשה כדי לבנות מחולל מספרים פסאודו אקראיים (אלגוריתם שיוצר מחרוזת מספרים שאי אפשר להבחין בה מפלט אקראי). "[מצאנו] קשר חדש בין קשיחות לפסאודו-אקראיות", אמר צ'ן.

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

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

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

"זה יהיה מגניב להיפטר מהאזהרה הקטנה הזו", אמר גרוסמן.

המטרה הסופית, אמר סנת'נאם, היא למצוא אלגוריתם שאינו דורש אקראיות כלל. אבל החיפוש הזה נשאר פתוח. "דטרמיניזם הוא מה שהיינו רוצים להשתמש בו", אמר.

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

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