ארכיון חודשי: יולי 2009

למה RSA טרם נפרץ? (בגלל החשיבה המתמטית הלא פרקטית)

פורסם בתאריך על ידי
28

הצגתי כאן בעבר את שיטת ההצפנה RSA, שהיא ללא ספק אחת משיטות ההצפנה החשובות ביותר בעולם כיום, וגם אתם משתמשים בה ככל הנראה, לכל הפחות בצורה לא מודעת. הכוח של RSA נסמך על בעיה בסיסית בתורת המספרים שטרם נמצא לה פתרון יעיל – פירוק של מספר לגורמים. בהינתן מספר ששווה למכפלת שני מספרים ראשוניים (מספרים שמתחלקים רק ב-1 ובעצמם), \(n=pq\), יש למצוא את \(p\) ו-\(q\) (למשל, בהינתן המספר \(221\) יש להחזיר \(17,13\)).

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

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

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

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

בהמשך הלמו מפרט את הרעיון, ועושה זאת היטב. בבסיסו, הרעיון הוא כזה – נניח שאנחנו רוצים לחשב פונקציה מסובכת כלשהי, שזמן החישוב שלה ארוך. למה להסתבך? במקום שהמעבד יחשב אותה שוב ושוב ושוב, פשוט נשמור בצד טבלה עם כל הקלטים והפלטים האפשריים שלה. למשל, במקום לחשב את \(f\left(x\right)=x^{2}\) (נניח שזו פונקציה מסובכת), שומרים טבלה שבה ליד 1 כתוב 1, ליד 2 כתוב 4, ליד 3 כתוב 9 וכן הלאה. כך אנחנו מצמצמים את הבעיה של חישוב הפונקציה לבעיה של ביצוע חיפוש בטבלה. יתר על כן, אם אנחנו בונים את הטבלה כשהיא ממויינת על פי הקלטים, החיפוש יהיה מהיר מאוד – נשתמש בחיפוש בינארי (שעליו סיפרתי ממש לא מזמן) כדי למצוא את הפלט בטבלה, בזמן חיפוש שהוא לוגריתמי בגודל הטבלה (ובעברית – קטן משמעותית מגודל הטבלה). עד כאן – הכל אחלה. השיטה שהלמו מתאר היא אכן שימושית בפרקטיקה, במקרים מסויימים. באשר לתיאוריה המתמטית – עוד נגיע לזה.

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

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

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

אם כן, מה באמת קורה בעולם האמיתי? כל אחד יכול לקרוא בעצמו; לדוגמה, הספריה OpenSSL שמממשת פרוטוקולי הצפנה אמיתיים זמינה בקוד פתוח לכל ואפשר להציץ בה (כמובן, זה לא אומר שהקוד קריא במיוחד…). למי שמתעניין, הקובץ הרלוונטי הוא bn_prime.c בתת הספריה crypto/bn. בקצרה, הרעיון הבסיסי הוא כזה: מגרילים מספר גדול, בן מספר הספרות המבוקש (איך מבטיחים שמספר יהיה גדול? למשל, כשמגרילים את הביטים שלו מוודאים שהביט המשמעותי ביותר יהיה 1. מן הסתם יש דרכים נוספות). לאחר מכן בודקים שהוא ראשוני – ראשית בדיקת חלוקה נאיבית על אוסף קטן ונתון מראש של ראשוניים (2048 ראשוניים, שפשוט כתובים בטבלה בקובץ bn_prime.h) – עד כאן מזכיר את השיטה של איציק. אלא שכעת, לאחר הבדיקה הנאיבית הזו (שמסננת מספר עצום של מועמדים אקראיים להיות ראשוניים) מורץ אלגוריתם לבדיקת ראשוניות; לא אלגוריתם AKS המפורסם (והאיטי לצרכים פרקטיים), אלא אלגוריתם מילר-רבין ההסתברותי (והמהיר מאוד), שמורץ עם פרמטר בטיחות טוב דיו כדי להבטיח שההסתברות שיתקבל בטעות מספר שאינו ראשוני הוא אפסי. ארחיב על מילר-רבין ועל שיטות אחרות לבדיקת ראשוניות בפוסט אחר; לעת עתה אסתפק בלהגיד שבדומה לבעית הפירוק לגורמים, כך גם השיטה של מילר רבין היא מחוכמת (אם כי לא מתקרבת לרמת התחכום של אלגוריתמי הפירוק לגורמים) ואינה מתבססת על רעיונות נאיביים כמו "בדוק עבור הרבה מספרים אם הם מחלקים את המספר שאת ראשוניותו בודקים".

חזרה אל איציק והרעיון שלו. אחרי שהוא מסביר מהו חיפוש בינארי ולמה הוא יעיל, איציק אומר:

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

איציק צודק לגמרי. טבלה כזו (שבה כתובים ליד המספר 15 הגורמים שלו, 3 ו-5, ליד 21 כתובים 3 ו-7, וכן הלאה) אכן תהיה שימושית מאוד בפירוק לגורמים. כעת איציק נכנס לפרטים הטכניים:

איציק מסביר שהבעיה כיום היא שאין מחשב חזק דיו כדי לבצע חישובים בפרק זמן סביר, אבל זיכרון יש בשפע, וכיום הוא זול מאוד בהשוואה לשנת 1977, השנה בה המציאו את הצפנת ה-.RSA איציק יודע גם להסביר שאם מפתח ההצפנה N הוא למשל בגודל 1024 ביט (שמתאים למספר עשרוני בן יותר מ-300 ספרות), אז כמות הזיכרון שצריך כדי לאחסן את המפתח הוא בסך הכל 128 בתים (מחלקים 1024 ביטים ב-8 כי בכל בית יש 8 ביטים). בנוסף יש צורך ב-128 בתים נוספים על מנת להחזיק את המספר הראשוני p וכן 128 בתים נוספים כדי להחזיק את המספר הראשוני q, שניהם מרכיבים את מפתח ההצפנה N.

החשבון כמובן נכון, אם כי מפתיע אותי שאיציק הפרקטי חושב שצריך לשמור גם את \(p\) וגם את \(q\); מספיק לשמור את \(p\) ולחשב את \(q\) על ידי חלוקת \(N\) ב-\(p\). זה מצמצם את גודל הטבלה בשליש. אם כן, הסכמנו שכל כניסה בטבלה היא קטנה מאוד – לוקחת 256 בתים. להשוואה – בעת כתיבת שורות אלו, הקובץ שבו הן נכתבות תופס כבר 25 אלף בתים. אם כן, הכל מושלם – אז למה RSA לא נפרצה? לאיציק הפתרונים:

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

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

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

יתרה מזאת: אם ישנם 10 בחזקת 100 מספרים ראשוניים ידועים, אז ישנם 10 בחזקת 200 מפתחות ציבוריים אפשריים. מספר הצעדים המקסימלי הנדרשים למצוא את הגורמים הראשוניים הוא פחות מ 800 צעדים.

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

וכאן נגמר המאמר.

לא אתווכח עם טענת ה"פחות מ-800 צעדים" – היא נכונה לגמרי. זו המחשה נהדרת לכוח העצום של החיפוש הבינארי. רק שאלה אחת לי אל איציק – איפה בדיוק תהיה שמורה אותה טבלה אגדית של \(10^{200}\) מפתחות ציבוריים אפשריים?

בואו נעשה לרגע את החשבון של איציק. כבר הסכמנו שכניסה בטבלה דורשת בסך הכל 256 בתים, שזה מספר זעום. כמה בתים לוקחת הטבלה כולה? במקרה הראשון, אמרנו שיש מיליון בחזקת 2 מפתחות ציבוריים אפשריים; כל מפתח שכזה מהווה כניסה בטבלה, ולכן דורש 256 בתים, ולכן בסה"כ נדרשים \(256\cdot10^{12}\) בתים. האם זה מספר גדול? ובכן, מדובר בכ-256 טרהבייטים (טרהבייט הוא 1000 ג'יגהבייט; בכל דיסק קשיח סטנדרטי בימינו יש כמה מאות ג'יגהבייטים וכבר מוכרים דיסקים קשיחים של טרהבייט בודד). כלומר, זה מספר קטן ומגוחך עבור סוכנויות הביון.

נפלא; ניתן לשער שגם במקרה השני מקבלים מספר קטן ומגוחך, אז אפשר ללכת לישון בשקט, נכון? הו, לא. אם יש \(10^{200}\) מפתחות אפשריים, התמונה משתנה באופן דרסטי; במקרה הזה צריך \(256\cdot10^{200}\) בתים כדי לאחסן את כולם. למי שטרם נתקל בחישובים במספרים כאלו זה עשוי להיראות סביר – \(200\) זה בסך הכל פי \(20\) מ-\(12\) (אפילו פחות), אז צריך רק להכפיל את המקום פי 20. אלא שזה לא נכון; לא צריך להכפיל את המקום פי 20, אלא פי \(10^{188}\). המספר הזה הוא עצום. עצום בצורה בלתי נתפסת. אם נניח שכל גרגר חול בעולם (נהיה לארג'ים ונניח שיש \(10^{100}\) כאלו) היה הופך לפתע פתאום לדיסק קשיח של קווינטיליון פטהבייטים (פטהבייט הוא 1000 טרהבייט), כמות הזיכרון שהיה אפשר לאכסן בכולם לא הייתה מתחילה אפילו לגרד את כמות הזכרון שהטבלה של איציק דורשת. במילים פשוטות – אין, לא הייתה אף פעם ולא תהיה אי פעם טבלה בגודל הזה. אם איציק הוא באמת פרקטי כמו שהוא טוען, היה עליו לדעת את זה.

אבל חמור מכך, אם איציק היה מזלזל קצת פחות בתיאורטיקנים ומקשיב להם, אולי הוא היה מבין שאפילו אם בדרך קסומה יצליחו לבנות את הטבלה העצומה הזו, על ידי רתימת כל הכוח של המין האנושי לפרוייקט הזה, זה עדיין לא היה מדגדג לקריפטוגרפים את קצה הזרת; הם פשוט היו מגדילים את המפתח, מ-1024 ביט ל-2048 ביט. תגידו – מה זה משנה? הרי אם קודם נדרשו 256 בתים בשביל כניסה אחת בטבלה, עכשיו יידרשו 512 בתים – בסך הכל הכפלנו את גודל הטבלה פי 2, לא משהו משמעותי. הבעיה כאן היא שאנחנו מתעלמים מהשאלה הבסיסית – מאיפה הראשוניים מגיעים וכמה כאלו יש?

אמרתי קודם שכדי למצוא מספרים ראשוניים פשוט מגרילים מספר גדול ובודקים אם הוא ראשוני. לא אמרתי מה עושים אם הבדיקה נכשלת – פשוט מגרילים מספר חדש ובודקים שוב (או שמשנים קצת את המספר הישן ובודקים שוב). השיטה הזו נשמעת מוזרה קצת במבט ראשון, כי מי מבטיח לנו שניפול אי פעם על ראשוני? אם כמות הראשוניים קטנה יחסית לכמות כל המספרים, אכלנו אותה – נגריל שוב ושוב מספר ולעולם לא ניפול על ראשוני. למרבה המזל, יש יחסית הרבה ראשוניים – זה בדיוק מה שמראה משפט המספרים הראשוניים שהזכרתי בחטף בפוסט הקודם. המשפט אומר (בערך) שבין \(1\) ל-\(n\) יש בערך \(\frac{n}{\ln n}\) מספרים ראשוניים (וככל ש-\(n\) גדול יותר ה"בערך" הזה מדוייק יותר) – זה אומר שההסתברות להגריל ראשוני בתחום הזה היא \(\frac{1}{\ln n}\). מכיוון ש-\(\ln n\) הוא בערך מספר הספרות שנדרשות כדי לייצג את \(n\), נובע מכך שכדי להגריל מספר ראשוני בן 100 ספרות צריך בערך 100 נסיונות, כדי להגריל מספר בן 200 ספרות צריך בערך 200 נסיונות, וכן הלאה – מספר הנסיונות הזה הוא קטן מאוד יחסית. זה גם מעיד על כך שמספר הראשוניים הוא גדול מאוד יחסית.

המספר הגדול ביותר שניתן לייצג עם \(1024\) ביט הוא \(2^{1024}\); זהו מספר בן 300 ספרות לערך שמן הסתם לא אכתוב פה (מי שרוצה לראותו – שיכתוב 1024**2 בפייתון או רובי). אם כן, כמה ראשוניים בני עד 1024 ביט יש? בערך \(\frac{2^{1024}}{1024}=\frac{2^{1024}}{2^{10}}=2^{1014}\) ראשוניים, וגם \(2^{1014}\) הוא מספר עצום, גם כן בעל בערך 300 ספרות (חדי העין בוודאי שמים לב שאני משתולל כאן עם הבסיס של הלוגריתם על ימין ועל שמאל – לא נורא, מותר לי). בקיצור, כבר ב-1024 ביט יש לנו הרבה יותר ראשוניים ממה שאיציק טוען; הוא מדבר על \(10^{100}\) ראשוניים, ואני אומר שכבר יש \(10^{300}\), מה שמוביל לטבלה בגודל של \(10^{600}\) – מספר בלתי נתפס.

אבל רגע, מה קורה אם אנחנו עוברים ל-2048 ביט? אז יהיו לנו בערך \(2^{2037}\) ראשוניים (למה?) וזה מספר בן 600 ספרות. הכפלה של מספר הביטים פירושה העלאה בריבוע של כמות הראשוניים הזמינים לנו (שבאה לידי ביטוי בהכפלה של מספר הספרות בתיאור הכמות שלהם). עכשיו הטבלה שלנו תצטרך להיות מגודל \(10^{1200}\) – לא "פי 2" יותר גדולה, אלא פי \(10^{600}\) יותר גדולה מקודם. בניסוח אחר – אם קודם היינו צריכים להשקיע את כל משאבי המין האנושי בטבלה אחת כזו, שכל תא בה מאכסן כמות זעומה של נתונים, כעת נצטרך לבנות מספר עצום של טבלאות שכאלו – טבלה לכל תא בטבלה המקורית. ואם המין האנושי ישיג את ההשיג הכביר והבלתי נתפס הזה, אז הקריפטוגרפים פשוט ימשכו בכתפיים ויעברו ל-4096 ביט, ושוב יעלו בריבוע את כמות הזיכרון הנדרשת. לקריפטוגרפים הגדלות כאלו של אורך המפתח אינן בעיה ממשית, כי כל מה שהן עושות הוא להגדיל פי 2 את הקושי של החישובים המעורבים (הגרלת מספרים, הצפנה וכו'). הגדלה פי 2 היא כאין וכאפס לעומת ההגדלה פי \(10^{600}\) שאיציק זקוק לה. כל זה הוא מקרה פרטי של האבחנה הכללית שבבסיס תורת הסיבוכיות התיאורטית – סיבוכיות אקספוננציאלית (שבה כשמגדילים את הקלט בביט אחד, הסיבוכיות מוכפלת פי 2, ולכן כשמכפילים את גודל הקלט, הסיבוכיות מועלה בריבוע) אינה משהו סביר, באופן כללי (כמובן שבעולם הפרקטי האמיתי, יש דוגמאות נגדיות).

אם כן, הטבלה של איציק איננה רעיון פרקטי; היא הרעיון הכי לא פרקטי שאפשר לחשוב עליו. ועוד לא אמרנו כלום על סוגיית הזמן שצריך כדי לבנות את הטבלה הזו מלכתחילה (ולמען האמת, גם לא ממש צריך). מה בעצם הייתה הטעות של איציק, חוץ מההתעלמות הגסה מהצורך לחשב כמה זכרון, בבתים, צריך בשביל הטבלה של ה-\(10^{100}\) ראשוניים שלו? לדעתי, חוסר ההבנה שלו את הגודל העצום של מרחב הראשוניים שעומדים לרשות הקריפטוגרפים הוא שבלבל אותו. הנקודה היא שלא צריך לבנות "רשימה שחושבה מראש של כל המספרים הראשוניים הידועים" כמו שאיציק תיאר, כדי שניתן יהיה להגריל ראשוניים – המרחב העצום של ה-\(10^{300}\) ראשוניים בני 1024 ביט זמין לנו בלי שנצטרך לאחסן אותו בשום מקום, בזכות אותו "אלגוריתם מתמטי" שאיציק התעקש שאיננו צריכים.

טוב, סיימנו עם זה, אבל אני עדיין רוצה להתייחס לטענת "כולם חושבים בצורה מתמטית ולא בצורה פרקטית כמו מתכנתים", בשתי צורות שונות – פרקטית, ומתמטית. מבחינה פרקטית, כדי לשכנע ש"כולם" דווקא כן חושבים בצורה פרקטית לפעמים (כש"כולם" מתייחס כאן לקריפטוגרפים) אני רוצה לתת דוגמה לתחום בקריפטוגרפיה שהוא מאוד "פרקטי" באופיו – התחום שעוסק ב-Side-Channel Attacks. מכיוון שהוא ראוי לפוסט נפרד, רק אגיד באופן כללי מהו – זה התחום שעוסק בתקיפת מערכות הצפנה לא על ידי תקיפת האלגוריתם שבבסיסן באופן תיאורטי, אלא על ידי שימוש במידע נוסף שמופק מכך שהאלגוריתם התיאורטי ממומש במערכת פיזית. דוגמאות לאפיקים שאפשר להפיק מהן מידע הן זמן החישוב שלוקח למעבד לבצע את האלגוריתם, כמות ההספק החשמלי שהוא צורך, החום שהוא פולט ואפילו הרעשים שהוא משמיע (התקפה פרקטית מהסוג האחרון הציע, בין היתר, עדי שמיר, ה-S שב-RSA; באופן כללי שמיר הוא דוגמה טובה למדען מחשב שיכול להיות גם מאוד מתמטי וגם מאוד פרקטי). ההתקפות הללו מזכירות את תעלול "קריאת המחשבות" הבא – אנחנו נותנים למישהו להחזיק מטבע של שקל ביד אחת, ושל חמישה שקלים ביד השניה, ומטרתנו היא לגלות באיזה יד נמצא איזה מטבע. אז אנחנו מבקשים מהמחזיק לכפול את מה שביד ימין ב-14, ואחר כך מבקשים ממנו לכפול את מה שביד שמאל ב-14, ואז אנחנו מבקשים ממנו לחבר את התוצאות ולהגיד לנו. מן הסתם הוא תמיד יגיד 84, אבל לעתים קרובות נוכל לנחש באיזו יד המטבע על ידי כך שנבחין איזה חישוב לקח לו זמן רב יותר (עם זאת, התעלול הזה יכול להיכשל כל כך בקלות שאף פעם לא העזתי לבצע אותו בעצמי).

כעת להתייחסות השניה, והחשובה יותר – גם מדעני מחשב שחושבים "בצורה מתמטית" יכולים לחשוב על השיטה שאיציק הציע, ולמעשה הם עשו את זה עוד הרבה לפני שאיציק הציע זאת. קיימים מודלים מתמטיים של חישוב שמטפלים בשיטה הזו באופן הרבה יותר כללי – כי מה שאיציק עושה הוא רק המקרה הקיצוני, והלא מעניין, של השיטה. באופן כללי אפשר לחשוב על אלגוריתמים שנעזרים במהלך החישוב שלהם ב"טבלה" של מידע שחושב מראש (אולי חישוב שדרש זמן רב; ולמעשה, אולי אפילו מידע שלא ניתן לחשב באופן אלגוריתמי – אבל כדי לפרט על זה, אני זקוק לפוסט נפרד), והמודל הפורמלי מכונה "מכונות שמקבלות 'עצה'" (ה"עצה" היא אותה טבלה). העובדה שכל פונקציה ניתנת לחישוב בקלות בהינתן עצה שהיא בעצם טבלה שבה לכל קלט כתוב הפלט המתאים לו היא אחת מהאבחנות הטריוויאליות הראשונות של חקר המודל הזה, כמו גם האבחנה שטבלה כזו היא אקספוננציאלית באורכה ולכן העסק לא כל כך מעניין. בדרך כלל עוסקים בטבלאות שגודלן הוא סביר – פולינומי – ביחס לגודל הקלט; מחלקת הסיבוכיות המרכזית בהקשר זה נקראת P/poly (ה-P מייצג חישוב בזמן יעיל, פולינומי; ה-poly מייצג עצות שהן פולינומיות בגודלן). פרט למודל הזה, מדעני מחשב עוסקים באופן כללי בשקלול זמן-מול-זיכרון (Space-Time tradeoff), כלומר בשאלה עד כמה ניתן לקצר את זמן הריצה של חישוב פונקציה מסויימת באמצעות שימוש רב יותר בזיכרון, אך גם על זה לא אפרט כרגע.

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

האם המצאנו או גילינו את המפלצת המתמטית שמתחת למיטה?

פורסם בתאריך על ידי
22

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

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

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

דוגמה קלאסית לצורה לניגוד הזה ראה כל סטודנט לחדו"א. המושג המרכזי בחדו"א הוא גבול, ולא אכנס כרגע להגדרה שלו (שתיארתי כאן פעם). הוכחות של גבולות של פונקציות ספציפיות הולכות בערך כך: מתחילים ממספר ממשי כלשהו \(\varepsilon>0\) וצריך לבנות, במהלך ההוכחה, מספר ממשי אחר \(\delta>0\) כך שהפונקציה תקיים איזו שהיא תכונה שתלויה ב-\(\delta\) וב-\(\varepsilon\). כלומר, ה-\(\varepsilon\) הספציפי שנבחר מציג "אתגר" בפני הפותר, והפותר צריך לספק \(\delta\) שמתמודד עם האתגר.

כאשר מרצים מוכיחים גבול מסויים בכיתה, לעתים הם פותחים את ההוכחה שלהם באופן הבא: "יהי \(\varepsilon>0\). נבחר \(\delta=\frac{3}{7}\sqrt{\varepsilon^{5}}\), וכעת…" ואז מראים שהתכונה מתקיימת. הבחירה הספציפית של ה-\(\delta\) שלהם תגרום להוכחה שהתכונה מתקיימת להיות אלגנטית ויפה במיוחד. רק מה, ה-\(\delta\) נראה מזוויע ולסטודנטים אין מושג איך אפשר היה להגיע אליו מלכתחילה. הדרך ה"נכונה" להתמודד עם גבולות היא להתחיל עם \(\delta\) כמעט שרירותי, לשחק איתו ולראות מה קורה במהלך תהליך ההוכחה של התכונה; לרוב התוצאות שמגיעים אליהן מספיקות כדי לזהות מה הערך של \(\delta\) צריך להיות כדי שההוכחה תהיה אלגנטית ויפה ככל האפשר, וזו גם הצורה שבה המרצה הגיע לכך מלכתחילה. עם זאת, את שלב ה"חקירה" הזה חייבים לעבור לפני שאפשר לבצע את ההוכחה במדוייק; העובדה שלא תמיד עושים זאת מקשה מאוד על הסטודנטים, לצערי.

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

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

ובכן, הדרך הפשוטה ביותר במתמטיקה מודרנית לדבר על גדלים של אינסוף היא באמצעות מה שמכונה עוצמות, אלא שהן כלל לא רלוונטיות לדיון הזה שכן עוצמת קבוצת הראשונים שווה לעוצמת קבוצת כל הטבעיים. ממילא, כאשר נענתה השאלה המדוברת תורת העוצמות טרם הומצאה (למעשה, אני משקר כאן חלקית – ההוכחה של משפט המספרים הראשוניים ניתנה ב-1896, אחרי שקנטור כבר פיתח את תורת הקבוצות – אבל המדד שאציג היה קיים הרבה לפני שהוכיחו את נכונותו). הצורה שבה המתמטיקאים ניגשו למושג הגודל הייתה קצת יותר מעודנת – נסמן ב-\(\pi\left(n\right)\) את מספרם של המספרים הראשוניים שקטנים או שווים ל-\(n\); השאלה היא מהו בערך הגודל של \(\pi\left(n\right)\), לכל \(n\). אם תרצו, אפשר לתת גם ניסוח אחר – נניח שאנחנו מגרילים מספר בין 1 ל-\(n\); מה ההסתברות שנקבל מספר ראשוני?

משפט המספרים הראשוניים ראוי לפוסט בפני עצמו. רק אציין שבתחילה כל מה שהיה הוא ניחוש – ניחוש ש-\(\pi\left(n\right)\approx\frac{n}{\ln n}\), כאשר שני הקווים מסמנים כאן "בערך" (יש למושג הזה משמעות מתמטית מדוייקת לחלוטין שלא אציג כרגע). את הניחוש הזה ניחשו – כל אחד בנפרד – גאוס ולז'נדר, וזאת פשוט על ידי הסתכלות על ערכים אמיתיים של \(\pi\left(n\right)\) שחושבו ידנית. ההוכחה הגיעה רק קרוב למאה שנים לאחר מכן, והיא מבוססת על אבחנה מבריקה של ברנרד רימן מאמצע המאה – שההתפלגות הזו של הראשוניים קשורה בצורה הדוקה לפונקציה מסויימת, שמאז נקראת "פונקצית הזטה של רימן" – למעשה, שאפשר לצמצם את המשפט כולו לטענה שלפונקציה אין אפסים בתחום מסויים (פונקצית הזטה של רימן היא מה שנקרא פונקציה מרוכבת מרומורפית; מבלי להיכנס לפרטים, תורת הפונקציות המרוכבות מראה כי ההתנהגות של הפונקציות הללו נקבעת בצורה מאוד חזקה באמצעות האפסים שלהן, כך שאין כאן מקריות). השערת רימן המפורסמת מצמצמת עוד יותר את המקומות שבהם האפסים של פונקצית הזטה עשויים להימצא, מה שמשפר באופן משמעותי את מה שניתן להגיד על התפלגות הראשוניים; כמובן שגם לזה לא אוכל להיכנס כרגע.

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

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

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

"עשיית הסדר" המדוברת נחשבת לאחד מהפרוייקטים המתמטיים הגדולים של המאה ה-20 (טוב, על מי אני עובד – נחשבת לפרוייקט הגדול ביותר של המתמטיקה במאה ה-20, חד וחלק). עשרות אם לא מאות מתמטיקאים עסקו בתרומה לאותו פרוייקט, שנמשך עשרות שנים והסתכם באלפי עמודי מאמרים. התוצאה הסופית? יש כמה משפחות אינסופיות של חבורות פשוטות שניתנות לאפיון פשוט יחסית, ועוד כ-26 חבורות בודדות, "ספורדיות", שאינן עונות על האפיונים הללו. מבין החבורות הספורדיות, הכי מפורסמת היא חבורת פישר-גריס, הידועה גם בשם "המפלצת". הנה הסברנו את ה-Monstrous. החבורה הזו זכתה בצדק לכינוי הזה, בגלל גודלה – היא מכילה בסביבות ה-\(10^{53}\) איברים. להשוואה – מספר הכוכבים ביקום מוערך בכ-\(10^{22}\). מן הסתם יש דרכים פשוטות יותר לאפיין את המפלצת מאשר כתיבת כל איבריה; אחת מהדרכים המקובלות לחקירת חבורות היא באמצעות תורת ההצגות, שבה מסתכלים על הצורות השונות שבהן ניתן לחשוב על אברי חבורה כעל טרנספורמציות לינאריות שפועלות על מרחבים וקטוריים (ובעברית: כעל משהו שפועל בצורה מסויימת על משהו מתמטי אחר). מי שלמד אלגברה לינארית זוכר אולי שלמרחבים לינאריים יש מימד. מי שלמד את תורת ההצגות זוכר אולי שבתורה זו מתעניינים בעיקר בהצגות אי פריקות של חבורות (הנה עוד מושג שלא אגדיר כעת). דוגמה טיפוסית למימד של הצגה אי פריקה של המפלצת היא 196883. עכשיו, משסיימנו את נפנוף הידיים הזה, אפשר לעבור לנפנוף ידיים גדול הרבה יותר.

האובייקט השני שאני רוצה לתאר נקרא "פונקצית ה-\(j\)". כאן אפילו לא אנסה להתחיל ולתאר מאיפה היא הגיעה במדוייק. מדובר בפונקציה מרוכבת, שמקיימת כמה תכונות יפות למדי שמאפיינות משפחה חשובה של פונקציות שנקראות "תבניות מודולריות" (Modular Forms; בתרגום ספרו של סיימון סינג על משפט פרמה המושג הפך, למרבה הבושה, ל"צורות מודולריות"). פונקצית ה-\(j\) היא לא "סתם עוד" תבנית מודולרית – היא אולי התבנית המודולרית החשובה ביותר, והיא מתקשרת לתורת המספרים בצורות יפות מאוד. כאמור, אין לי שום סיכוי לדבר על כך ברצינות כאן וכעת, אך חשוב לי להבהיר שהפונקציה הזו אינה מלאכותית; לא סתם בחרנו לדבר עליה מבין כל אינסוף הפונקציות הקיימות, כשם שהמפלצת אינה מלאכותית.

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

מה בעצם היה הקשר? לפונקצית ה-\(j\) יש הצגות רבות, ואחת מהן היא באמצעות התמרת פורייה (שוב, משהו שלא אכנס אליו). בהצגה הזו אפשר לכתוב את הפונקציה באופן הבא: \(j(\tau)=\frac{1}{{q}}+744+196884{q}+21493760{q}^{2}+864299970{q}^{3}+\cdots\) (מהו \(q\)? מהו \(\tau\)? שוב, לא חשוב). מה שמעניין כאן הם המקדמים של המשוואה, אם מתעלמים מ-744. המקדם השני אולי נראה לכם מוכר, כי אך לפני שנייה הזכרתי את המספר 196883, הקטן ממנו באחד; זה גם מה שמק'קי ראה. מכיוון ש-\(196884=1+196883\). ה-1 מוסבר בקלות בכך שיש למפלצת הצגה אי פריקה ממימד 1. ההצגה האי פריקה הבאה של המפלצת היא מגודל \(21296876\), ולא קשה לראות ש-\(21493760=1+196883+21296876\). בקיצור, יש כאן קשר. בהמשך, הקשר נהיה קצת יותר מורכב, אבל הרעיון הבסיסי נותר זהה – כל אחד מהמקדמים בפיתוח של פונקצית ה-\(j\) חוץ מה-744 הזה ניתן לכתוב באמצעות סכום כלשהו של גדלי ההצגות האי פריקות של המפלצת. כל זה, כמובן, התגלה באופן אמפירי לגמרי, בלי שמץ של מושג לאף אחד מהמעורבים מה לעזאזל הולך כאן.

האבחנה הראשונית הייתה ב-1979; ב-1992 הוכיח המתמטיקאי ריצ'רד בורצ'רדס את הקשר (שכאמור, איני יכול לתאר בצורה פורמלית ומדוייקית). אם כן, אין כאן מקריות; שני האובייקטים אכן קשורים בצורה מסויימת. מהי? אין לי מושג, אבל זה לא העניין. ראשית, העניין הבסיסי הוא היופי שבכל הסיפור הזה – יופי שאני מניח שכל חובב מתמטיקה יכול לראות. הדבר השני הוא מה שהתופעה הזו אומרת לנו על שאלת המתמטיקה-תגלית-או-המצאה. איני יכול להבין כיצד מישהו שמודע לתוצאות הללו יכול להמשיך ולחשוב שהמתמטיקה כולה המצאה; ברור לגמרי שאובייקטים מתמטיים שאנחנו "ממציאים" הם בעלי חיים עשירים ורחבים יותר מאשר אנחנו מסוגלים להעלות בדמיון שלנו. האם אנחנו באמת ממציאים משהו? האם כשהעיוורים נתקלים בפיל, האחד אוחז בזנבו והשני בחדקו, ניתן לומר שהם "ממציאים" את הזנב והחדק בכך שהם נותנים להם שמות? האם בכך שהם ממששים את הזנב והחדק הם יודעים את כל מה שניתן לדעת? לא.

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

איך מוצאים את נוסחת פיבונאצ'י?

פורסם בתאריך על ידי
24

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

אבל ראשית יש להציג את הבעיה. תחילתה באחד מהמתמטיקאים האירופאים הבולטים הבודדים של ימי הביניים, שהיו תקופה חשוכה במיוחד עבור המתמטיקה, בין הפריחה האדירה לה היא זכתה ביוון העתיקה, והפריחה האדירה שלה החל מימי הרנסנס והלאה. בימי הביניים עיקר המתמטיקה השתמר ופותח בידי המוסלמים, וגם ליאונרדו מפיזה המוכר יותר בשם פיבונאצ'י, איטלקי, למד מתמטיקה אצל מורים מוסלמים כשגדל באלג'יר. בשנת 1202 פרסם פיבונאצ'י ספר – "ספר החשבוניה" – שהקיף את הידע המתמטי על אלגברה של אותה תקופה (בתקופת היוונים עסקו בעיקר בגאומטריה, וגם בעיות מספריות, דוגמת מציאת מחלק משותף מקסימלי – "האלגוריתם האוקלידי" – נוסחו באופן גאומטרי; בשלהי תקופת יוון העתיקה ובתקופת המוסלמים עיקר הדגש עבר לאלגברה, והמילה "אלגברה" עצמה הגיעה משם ספר של המתמטיקאי המוסלמי המפורסם ביותר, אל-ח'ואריזמי). הספר הכיל כמה מהחידושים המסעירים בתחום – למשל, השיטה העשרונית ושימוש באפס. הוא גם הכיל חידה חביבה שעסקה בארנבים.

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

ובכן, בחודש הראשון יש 0 זוגות של ארנבים בוגרים – יש זוג אחד של ארנבים צעירים ותו לא. בחודש שלאחר מכן יש זוג אחד של ארנבים בוגרים (הזוג הצעיר שלנו התבגר), ואפס זוגות של ארנבים צעירים. בחודש לאחר מכן יש את אותו הזוג של ארנבים בוגרים, וזוג חדש של ארנבים צעירים שהם הולידו; ובחודש שלאחר מכן הארנבים שהיו צעירים התבגרו, כך שיש לנו שני זוגות של ארנבים בוגרים, ובנוסף יש זוג צעיר אחד חדש. אם תמשיכו את המשחק הזה עוד ועוד, בוודאי תקבלו את סדרת הערכים הבאה, עבור מספר הארנבים הבוגרים בכל חודש: \(0,1,1,2,3,5,8,13,\dots\). מה שפיבונאצ'י רצה לעשות הוא למצוא חוקיות בסדרה הזו.

נסמן את אברי הסדרה בתור \(F_{n}\), כאשר \(n\) הוא מספר החודש המתאים. לצורך נוחות, החודש הראשון יסומן ב-0, ולכן הסדרה היא \(F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2\) וכן הלאה. החוקיות שפיבונאצ'י הצביע עליה היא פשוטה במיוחד: \(F_{n}=F_{n-1}+F_{n-2}\). כלומר, כל איבר בסדרה (לאחר שני האיברים הראשונים) שווה לסכום שני האיברים שקדמו לו. מעט מחשבה מראה מדוע זה כך במקרה של הארנבונים. מהו \(F_{n}\), בעצם? הוא מספר זוגות הארנבונים שהיו בוגרים בחודש שלפני כן, ועוד מספר זוגות הארנבונים שהיו צעירים בחודש שלפני כן, והתבגרו. מספר זוגות הארנבונים שהיו בוגרים בחודש שלפני כן הוא בדיוק \(F_{n-1}\) – זה מה שמספר זה סופר. אבל כמה זוגות ארנבונים צעירים היו? ובכן, הכלל הוא שארנבון צעיר בחודש מסויים הוא ה"תוצר" הישיר של זוג ארנבונים שהיו מבוגרים בחודש שלפני כן. כלומר, אם אנחנו רוצים לספור כמה ארנבונים צעירים היו בחודש \(n-1\), התשובה היא שמספר זה שווה למספר הארנבונים המבוגרים בחודש \(n-2\). כלומר, \(F_{n-2}\) הוא בדיוק מספר הארנבונים שהיו צעירים בחודש \(n-1\), ומכאן נובעת הנוסחה. הנוסחה הזו, שבה איבר בסדרה מתואר באמצעות איברים מוקדמים יותר בסדרה, נקראת נוסחה רקורסיבית (רקורסיה היא הגדרה של דבר מה באמצעות הסתמכות על מופעים יותר פשוטים שלו – במקרה שלנו, איבר בסדרה מוגדר באמצעות איברים קטנים יותר בסדרה, עד לאיברים \(F_{0},F_{1}\) שמוגדרים בצורה ישירה) או בעברית, נוסחת נסיגה.

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

מה הבעיה כרגע? נניח שאני רוצה מסיבה כלשהי לחשב את \(F_{137}\). איך אני עושה זאת? אם כל מה שיש לי הוא הנוסחה הרקורסיבית, עלי לחשב את \(F_{136}\) ואת \(F_{135}\), כלומר הצטצמתי לבעיה יותר פשוטה, ועדיין גם היא דורשת עבודה – כדי לחשב את \(F_{136}\) אני צריך את \(F_{135}\) (שאמנם, אני ממילא צריך) אבל גם את \(F_{134}\) וכן הלאה וכן הלאה – כלומר, כדי לחשב את \(F_{137}\) אצטרך לחשב את כל \(F_{n}\) עבור \(n<137\). חייבים להודות שזה לא נשמע יעיל במיוחד. האם אין דרך לחשב את \(F_{n}\) בלי לחשב את כל האיברים הקודמים בסדרה?

התשובה חיובית, וכדי להבהיל אתכם גם אתן אותה במפורש עכשיו – מתקיים ש-\(F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]\). הנוסחה הזו נראית מבעיתה לגמרי – משום מקום צץ לו שורש 5, שהוא בכלל לא מספר רציונלי, ומעלים דברים בחזקת \(n\) ולך תחשב את זה בכלל והצילו. ובכן, אתם מוזמנים לבדוק עבור ערכים קטנים של \(n\) שהנוסחה עובדת, וכל השורשים של חמש מצטמצמים והכל טוב ויפה; ומחשב מסוגל להשתמש בנוסחה הזו כדי לחשב את \(F_{n}\) בקלות רבה יחסית, הרבה יותר מאשר שימוש בנוסחה הרקורסיבית וחישוב כל הערכים הקודמים בסדרה (למעשה, לא חייבים לחשב את הנוסחה שמוצגת בנוסחה כמות שהיא ואפשר לבצע כל מני שיפורים אך לא אכנס לכך).

אם כן, איך מגיעים לנוסחה הזו? מה ההגיון שבה? מאיפה צץ השורש? והאם הפתרון הוא אד-הוקי ומתאים רק לפיבונאצ'י? אענה על הכל, ואתחיל מהשאלה האחרונה – לגמרי לא. השיטה שאציג עובדת לכל נוסחה רקורסיבית שהיא לינארית במקדמים קבועים והומוגנית – ובמילים המפוצצות הללו אני מתכוון לכך שנוסחת הנסיגה היא באופן כללי מהצורה \(a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots+c_{k}a_{n-k}\), כלומר שהאיבר ה-\(n\) בסדרה הוא סכום של \(k\) האיברים הקודמים בסדרה, כשהם מוכפלים במספרים קבועים \(c_{1},\dots,c_{k}\). למשל, \(a_{n}=3a_{n-1}+5a_{n-4}\) היא דוגמה נוספת לסדרה שמתאימה לנוסחה הזו. השיטה שאציג תקפה לכל המשוואות הללו, אך אציג אותה עבור הדוגמה הספציפית של פיבונאצ'י כדי לא להסתבך יותר מדי עם הסימונים.

לאלו מכם שמכירים משוואות דיפרנציאליות, המילים "משוואה לינארית במקדמים קבועים והומוגנית" עשויה להיות מוכרת מאוד – בעיות דומות יש גם במשוואות דיפרנציאליות. גם "תנאי ההתחלה" של הנוסחה הרקורסיבית (במקרה של פיבונאצ'י, \(F_{0}=0,F_{1}=1\); במקרה של סדרה שבה איבר תלוי ב-\(k\) הקודמים, תנאי ההתחלה צריך להיות \(k\) האיברים הראשונים בסדרה) מזכירים את המושג המקביל ממשוואות דיפרנציאליות, וגם שיטת הפתרון היא דומה – מתחילים מ"ניחוש מוצלח" של איך בערך הפתרון אמור להיראות, מציבים אותו במשוואה, ומקבלים מההצבה הזו את הפתרון המדוייק. זה לא מוכיח מיידית שהפתרון נכון, אלא צריך להוכיח זאת – אלא שההוכחה אינה קשה ומספיק לבצע אותה פעם אחת, עבור נוסחת הנסיגה ה"כללית" (הלינארית-מקדמים קבועים-הומוגנית), ואז מספיק יהיה להשתמש בשיטה כדי למצוא את הפתרון (שהוא הדבר שמעניין אותנו, בסופו של דבר).

כבר אגלה מראש שהניחוש הבסיסי שלנו הוא שפתרון נוסחת נסיגה "כללית" הוא מהצורה \(a_{n}=\lambda^{n}\) עבור מספר ממשי כלשהו \(\lambda\). כלומר, שהאיבר ה-\(n\)-י בסדרה הוא העלאה בחזקה \(n\)-ית של מספר קבוע כלשהו, שתלוי רק בנוסחת הנסיגה הספציפית ולא ב-\(n\). בוודאי תצעקו כעת שהפתרון של פיבונאצ'י אינו בדיוק כזה – אני יודע, ונגיע לכך. לפני כן צריך להבין איך בכלל הגענו לניחוש הזה – למה שזה יהיה משהו בחזקת \(n\)? למה לא \(n^{t}\), למשל? (שימו לב להבדל – כעת \(n\) הוא בסיס החזקה ולא המעריך שלה, כמקודם). התשובה לכך היא שניתן להעריך את קצב הגידול של הפונקציה לא רע. אדגים זאת על פיבונאצ'י. מכיוון ש-\(F_{n}=F_{n-1}+F_{n-2}\) וכל האיברים (פרט ל-\(F_{0}\)) הם חיוביים, אז \(F_{n}>F_{n-1}\) לכל \(n>1\). מכאן בפרט שמתקיים \(F_{n}=F_{n-1}+F_{n-2}<2F_{n-1}\), כלומר \(F_{n}\) לא גדול יותר מאשר פי 2 האיבר שקדם לו, \(F_{n-1}\), ולכן קצב הגידול שלו אינו גדול מדי: מתקיים ש-\(F_{n}<2^{n}\) (כי אם האיבר \(F_{1}\) הוא 1, השני הוא לא יותר מאשר 2, והשלישי לא יותר מאשר 4, והרביעי לא יותר מאשר 8, וכן הלאה).

מצד שני, \(F_{n}=F_{n-1}+F_{n-2}>2F_{n-2}\). כלומר, \(F_{n}\) הוא לפחות גדול פי 2 מאשר \(F_{n-2}\), ולכן קצב הגידול שלו אינו יכול להיות קטן מדי: מתקיים ש-\(F_{n}>2^{\left\lfloor \frac{n}{2}\right\rfloor }\). שוב, לדוגמה – אם \(F_{1}=1\) אז האיבר השלישי בסדרה הוא לפחות 2, והאיבר החמישי הוא לפחות 4, והשביעי הוא לפחות 8 וכן הלאה. כלומר, קיבלנו שקצב הגידול של \(F_{n}\) הוא אקספוננציאלי – הוא חסום הן מלמעלה והן מלמטה על ידי חזקה \(n\)-ית של מספר כלשהו (שימו לב ש-\(2^{\frac{n}{2}}=\left(\sqrt{2}\right)^{n}\) ומכאן שזה ש-\(n\) מופיע במעריך כשהוא מוכפל במשהו לא באמת משנה עבורו, אלא רק עבור הבסיס של החזקה). מכאן שבדיקת מועמד לפתרון שהוא מהצורה \(\lambda^{n}\) היא מתבקשת; הוא מסדר הגודל הנכון. מי שלא עלה בידו לעקוב אחרי כל האסימפטוטיקה הזו – לא נורא. מטרתה לתת מוטיבציה לפתרון ולהמחיש שלא מדובר בניחוש ממוזל בלבד אלא בבחירה מושכלת, אך אין זה הכרחי להמשך הפתרון.

כעת אנו מגיעים לשאלה המרכזית. נניח כי \(F_{n}=\lambda^{n}\) הוא אכן פתרון לנוסחת הנסיגה; מהו \(\lambda\)? לצורך כך ניתן להציב את הפתרון בנוסחה \(F_{n}=F_{n-1}+F_{n-2}\) ולקבל את המשוואה \(\lambda^{n}=\lambda^{n-1}+\lambda^{n-2}\). ברור כי \(\lambda=0\) פותר את נוסחת הנסיגה (פתרון כזה פותר גם את הנוסחה ה"כללית" שלעיל) אבל זה אינו פתרון מעניין, אז נניח כי \(\lambda\ne0\), ולכן אפשר לחלק את המשוואה שקיבלנו ב-\(\lambda^{n-2}\) ולקבל \(\lambda^{2}=\lambda+1\), או, אחרי העברת אגפים, \(\lambda^{2}-\lambda-1=0\). זוהי משוואה ריבועית פשוטה ואנו יודעים לפתור אותה בעזרת הנוסחה הכללית. נקבל \(\lambda=\frac{1\pm\sqrt{1+4}}{2}=\frac{1\pm\sqrt{5}}{2}\). כלומר, קיבלנו שני פתרונות, ובשניהם צץ לו ה-\(\sqrt{5}\) המבהיל. מכאן זה מגיע.

כדי לעשות לעצמי את החיים פשוטים יותר מעתה והלאה, אשתמש בסימון סטנדרטי: \(\phi_{+}=\frac{1+\sqrt{5}}{2}\), ו-\(\phi_{-}=\frac{1-\sqrt{5}}{2}\). המספר \(\phi_{+}\) הוא "יחס הזהב" המפורסם. אם כן, הגענו למסקנה ש-\(F_{n}=\phi_{+}^{n}\) ו-\(F_{n}=\phi_{-}^{n}\) הם פתרונות של נוסחת הנסיגה \(F_{n}=F_{n-1}+F_{n-2}\). מדוע זה לא הפתרון שהצגתי לעיל ומה עוד לא עשינו?

הבעיה בשני הפתרונות שמצאנו היא שהם אינם עונים ל"תנאי ההתחלה". צריך, למשל, שיתקיים \(F_{0}=0\). מיידית ברור שהייתי אידיוט גמור אם חשבתי שפתרון מהצורה \(\lambda^{n}\) יקיים זאת – חזקה של מספר שאינו 0, אינה 0. כמו כן צריך שיתקיים \(F_{1}=1\), ולכן הפתרון העלוב \(\lambda=0\) גם כן לא טוב לנו. בקיצור, האם צריך לזרוק לזבל את כל הרעיון שהפתרון הוא מהצורה \(\lambda^{n}\)? לא, צריך רק להרחיב מעט את אוסף הפתרונות שלנו – משני פתרונות, לאינסוף.

באופן כללי, אם \(f\left(n\right)\) הוא פתרון של נוסחת הנסיגה של פיבונאצ'י (ושוב, מה שאני אומר תקף גם לנוסחה ה"כללית"), כלומר אם \(f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)\) אז גם \(h\left(n\right)=\alpha\cdot f\left(n\right)\), כאשר \(\alpha\) הוא מספר ממשי, הוא פתרון, כי הרי \(h\left(n\right) = \alpha f\left(n\right)=\alpha\left(f\left(n-1\right)+f\left(n-2\right)\right)=\alpha f\left(n-1\right)+\alpha f\left(n-2\right) = h\left(n-1\right)+h\left(n-2\right)\) באופן דומה, אם \(f\left(n\right),g\left(n\right)\) שניהם פתרונות, אז גם \(h\left(n\right)=f\left(n\right)+g\left(n\right)\) הוא פתרון, כי

\(h\left(n\right) = f\left(n\right)+g\left(n\right)=\left(f\left(n-1\right)+f\left(n-2\right)\right)+\left(g\left(n-1\right)+g\left(n-2\right)\right) = \left(f\left(n-1\right)+g\left(n-1\right)\right)+\left(f\left(n-2\right)+g\left(n-2\right)\right)=h\left(n-1\right)+h\left(n-2\right)\)

אם כן, אוסף הפתרונות של המשוואה סגור לפעולות של "כפל בסקלר" (כפל במספר ממשי, במקרה שלנו) ושל חיבור שני פתרונות. אלו מכם שמכירים אלגברה לינארית ודאי רואים כעת כי אוסף הפתרונות של נוסחת הנסיגה (אם לא דורשים את קיום תנאי ההתחלה) מהווה מרחב וקטורי. הבסיס של המרחב הזה הם בדיוק שני הפתרונות שמצאנו בהתחלה – \(\phi_{+}^{n},\phi_{-}^{n}\). מי שאינו מכיר אלגברה לינארית עדיין יכול לראות, משתי התכונות שהדגמתי לעיל, שאם \(f\left(n\right),g\left(n\right)\) הם שני פתרונות לנוסחת הנסיגה, אז גם \(\alpha f\left(n\right)+\beta g\left(n\right)\) הוא פתרון, עבור כל \(\alpha,\beta\) ממשיים שנבחר. לכן הגדלנו בצורה משמעותית את אוסף הפתרונות האפשריים שלנו – אולי אחד מהם כן עונה לתנאי ההתחלה?

אם כן, נכתוב פתרון "כללי" לנוסחת הנסיגה בתור \(F_{n}=\alpha\phi_{+}^{n}+\beta\phi_{-}^{n}\). אנו רוצים לגלות מהם \(\alpha,\beta\) שעבורם יתקיימו תנאי ההתחלה, אז נשתמש בכך שידוע ש-\(F_{0}=0\) ונקבל את הנוסחה \(0=\alpha\phi_{+}^{0}+\beta\phi_{-}^{0}=\alpha+\beta\), כלומר אנחנו כבר יודעים שבהכרח מתקיים \(\alpha=-\beta\). לכן נכתוב את הפתרון בתור \(F_{n}=\alpha\left(\phi_{+}^{n}-\phi_{-}^{n}\right)\). כעת נשתמש במשוואה הנוספת שנותרה לנו – \(F_{1}=1\). נקבל ממנה כי \(1=\alpha\left(\phi_{+}-\phi_{-}\right)\), אבל את \(\phi_{+}-\phi_{-}\) קל לנו לחשב: \(\phi_{+}-\phi_{-}=\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}=\sqrt{5}\). מכאן נקבל ש-\(1=\alpha\sqrt{5}\), ובמילים אחרות – \(\alpha=\frac{1}{\sqrt{5}}\). לכן הפתרון הנכון לנוסחת פיבונאצ'י, זה שמתאים גם לתנאי ההתחלה, הוא \(F_{n}=\frac{1}{\sqrt{5}}\left(\phi_{+}^{n}-\phi_{-}^{n}\right)\) (וזו גם המפלצת שהצגתי לעיל, עם סימונים מעט יותר ידידותיים). ושוב, מה שעשיתי כאן, עם המרחב הלינארי והכל, זהה למה שעושים כאשר פותרים משוואות דיפרנציאליות לינאריות.

מה שעשיתי נראה אולי מעט אד-הוקי בשל הצורה שבה מצאתי את \(\alpha,\beta\), אבל זה רק כי נמנעתי מלהשתמש בשיטת הפתרון הכללית למשוואות לינאריות, שהייתה נותנת את אותה התוצאה. באופן כללי, כשיש לנו משוואה מהצורה \(a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots+c_{k}a_{n-k}\), הצבה של \(\lambda^{n}\) מניבה את המשוואה \(\lambda^{k}-c_{1}\lambda^{k-1}-\dots c_{k-1}\lambda-c_{k}=0\). עבור \(k\ge5\) כבר אין נוסחה סגורה פשוטה עבור פתרונות המשוואה (ניתן להראות זאת באמצעות תורת גלואה, וזה עניין לסדרת פוסטים בפני עצמה), ויכולות להיות בעיות נוספות עם הפתרונות (הם יהיו מרוכבים, או שאותו פתרון יופיע מספר פעמים, בדומה לכך שהפתרון היחיד של \(x^{2}-2x+1\) הוא \(x=1\)) אבל למרות כל הבעיות הללו ניתן לבנות \(k\) פתרונות שונים למשוואה שיהוו בסיס למרחב הפתרונות שלה, וניתן להראות שלכל בחירה של תנאי ההתחלה נקבל פתרון יחיד. כל זה דורש אלגברה לינארית שלא אוכל להיכנס אליה כעת, אבל בעתיד אולי ארחיב על כך (בפוסט שיהיה בהכרח טכני יותר מזה הנוכחי). ושוב – גם במשוואות דיפרנציאליות כל הסיפור הזה מתרחש באופן זהה.

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