שני דברים מתפלגים אחיד: ראשוניים וטעויות בעיתונים (ואני לא בטוח בקשר לראשוניים)

 

לא מזמן עלתה לכותרות בעיתונות תוצאה מתמטית חדשה שעוסקת במספרים ראשוניים. זה די הפתיע אותי כי התוצאה היא אמנם מעניינת, אבל למה שתעניין במיוחד אנשים שאינם מתעניינים במתמטיקה? אולי בגלל האופי שלה, שנראה על פניו “אמפירי” משהו; אולי בגלל שיש איזו הילה קסומה למספרים ראשוניים; ואולי פשוט בגלל שמישהו במחלקת יחסי הציבור הרלוונטית עשה את עבודתו ממש, ממש טוב. לא תכננתי לכתוב פוסט על התגלית הזו כי אני לא ממש חזק בתחום ולא יכול להסביר ברצינות מה הולך שם, אבל עכשיו שזה התחיל לחלחל גם אלינו לארץ. וכשאני אומר “לארץ” אני מתכוון לעיתון “הארץ” שפרסם כתבה בנושא. וכרגיל, מעניין אותי להתייחס לשגיאות המזעזעות שיש שם (שגיאות שמזכירות לי את המאמר השגוי לגמרי ההוא על אלגוריתם AKS לבדיקת ראשוניות שפורסם ב”הארץ” לפני שנים רבות וכבר קטלתי בבלוג) ובכלל לאופן המוזר שבו מסקרים תגלית כזו.

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

עדיין, כשמתמטיקאים אומרים שהראשוניים “נראים אקראיים” הם מתכוונים למשהו. רק שה”משהו” הזה הוא די טכני. הם אומרים - נניח שנגריל מספרים בין 1 ל-\( n \), בהתפלגות דומה לזו שאנחנו יודעים שהמספרים הראשוניים מופיעים בה - התכונות של הסדרה האקראיית שנגריל כך יהיו דומות לתכונות של סדרת הראשוניים. ההסתייגויות פה הן קריטיות - לא כל התכונות יעבדו (למשל, בסדרה אקראית נצפה שבערך חצי מהמספרים יסתיימו בספרה זוגית, ובסדרת הראשוניים כמובן שלא) וה”דמיון” שמדובר עליו לא אומר שתהיה זהות מוחלטת בתכונות שכן עובדות. אבל הדמיון הזה מספיק מועיל עבור תכונות מסויימות כדי שנוכל להשתמש בו. רוצים דוגמאות? זה יאלץ לחכות לזמן אחר, שבו אכיר טוב יותר את התחום הזה בעצמי ואזכור את הפרטים הטכניים של הדברים שאני מדבר עליהם כרגע במעורפל.

מה שהמאמר מדבר עליו מתעסק בדיוק עם תכונת “הספרה האחרונה” שהזכרתי כרגע, אז בואו נחדד את זה: אם מספר טבעי מסתיים בספרה זוגית, הוא מתחלק ב-2, ולכן אם הוא לא 2, הוא לא ראשוני. אם הוא מסתיים ב-5 הוא מתחלק ב-5 וזה אותו סיפור. לכן הספרות היחידות שבהן מספר ראשוני גדול מ-5 יכול להסתיים בהן הן 1,3,7,9. עכשיו, אם הראשוניים הם “כאילו-אקראיים” ביחס לתכונה הזו, היינו מצפים שאם ניקח, למשל, את 100,000 הראשוניים הראשונים, כמות הראשוניים שמסתיימת בכל אחת מהספרות הללו תהיה כמעט 25,000, כלומר הראשוניים מתפלגים בצורה אחידה בין ארבע המחלקות הללו. באופן דומה המתמטיקאים מתעסקים לא רק בבסיס 10 אלא בכל בסיס ספירה: למשל, בבסיס 4 הספרות היחידות שבהן המספר הראשוני יכול להסתיים רק ב-1 וב-3, ואז אנחנו מצפים להתפלגות של חצי-חצי בין האפשרויות הללו.

וכאן הסיפור קצת מסתבך. כי קיים משפט יפהפה של דיריכלה שכתבתי עליו פוסט בשעתו שאומר שבמובן מסויים, ההתפלגות בין המחלקות האפשריות היא אחידה (עבור כל בסיס ספירה, לא רק 10 או 4), אבל המובן המסויים הזה אינו אקראי לגמרי. למשל, יש תופעה שצ’בישב הצביע עליה לפיה בבסיס 4 לאחת המחלקות יש “יתרון” על פני השניה - אם עוצרים וסופרים כמה ראשוניים יש בכל מחלקה, נגלה ברוב המוחץ של המקרים שיש יותר ראשוניים שמסתיימים ב-3 מאשר ב-1. אם הראשוניים היו אקראיים לגמרי לא היינו מצפים לראות תופעה כזו.

המאמר החדש מדבר על תופעה דומה מאוד לזו של צ’בישב, רק עבור זוגות סמוכים של ראשוניים (או סדרות ארוכות יותר של ראשוניים רצופים, אבל קל להבין את זה עבור זוגות). למשל, בבסיס 3, הספרות האחרונות האפשריות הן 1 ו-2; אם עוברים על מיליון הראשוניים הראשונים ומנסים לספור את מספר הראשוניים שהספרה האחרונה שלהם היא 1 וגם הספרה האחרונה של הראשוני הבא בתור אחריהם היא 1, מקבלים שהמספר הזה הוא 215,873; ואפשר בדומה לערוך חישוב גם עבור שלוש האפשרויות הנותרות של “הספרה האחרונה שלי היא 1 ושל הבא אחרי היא 2” ושל “שלי 2, של הבא בתור 1” ושל “שלי 2, של הבא בתור 2”. מקבלים שהמקרים שבהם הספרה של הבא בתור שונה מזו של הנוכחית הם רבים בצורה משמעותית יותר מאשר מקרים שבהם היא שווה.

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

האם המאמר עושה את זה? מתיישב ומסביר ומוכיח באופן מסודר? ובכן, כן, וזה הקטע שבו אני לא יכול לסייע לכם (ובגללו לא רציתי לכתוב פוסט על הנושא מלכתחילה) - הם נכנסים לתורת המספרים האנליטית ברמה גבוהה מזו שאני מסוגל להיכנס אליה כרגע. התוצאה שלהם היא סדרה של השערות לגבי האופי המדוייק של התפלגות הראשוניים במחלקות מהצורה שתוארה לעיל (אבל הרבה יותר כללית: לא רק בסיס 4 אלא כל בסיס; ולא רק זוגות של ראשוניים אלא כל סדרה) והסבר שהם קוראים לו “היוריסטי” לגבי התוצאה שלהם במקרה שבו מדובר על זוגות של ראשוניים, שמתבסס על השערות קיימות בתורת המספרים (השערות הארדי-ליטלווד). כמה ממה שהם עושים הוא ממש הוכחה מתמטית פורמלית וכמה הוא רק נפנוף ידיים? אני לא יודע. המאמר עדיין לא פורסם בכתב עת מתמטי שעבר ביקורת עמיתים ואני לא באמת יודע מה הערך של תוכנו מעבר לאבחנה האמפירית שלו; הסיבה שהוא מעניין אותי היא שהוא עלה לכותרות (וכאמור, אני לא ממש מבין למה הוא מעניין את הכותרות).

ועכשיו בואו נדבר על המאמר ב”הארץ”.

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

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

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

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

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

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

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

הוא אומר:

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

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

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

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

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

[caption id=”attachment_3327” align=”aligncenter” width=”740”] https://xkcd.com/451[/caption]