פיטר שור (Peter Shor)
הגדרה
פיטר שור הוא מתמטיקאי אמריקאי, פרופסור למתמטיקה שימושית ב-MIT, שפיתח ב-1994 את אלגוריתם שור — אלגוריתם קוונטי לפירוק-מספרים-לגורמים שמהווה את האיום התיאורטי המרכזי על עמידות-ההצפנה ארוכת-הטווח של RSA.
רקע והשכלה
פיטר וויליסטון שור נולד ב-14 באוגוסט 1959 בניו יורק, וגדל בוושינגטון הבירה ובמיל-ואלי שבקליפורניה. עוד בתיכון טמלפייס הצטיין במתמטיקה: ב-1977 סיים במקום השלישי באולימפיאדת-המתמטיקה הארצית האמריקאית (USAMO), וזכה במדליית-כסף באולימפיאדת-המתמטיקה הבינלאומית שנערכה אותה שנה ביוגוסלביה. למד מתמטיקה במכון הטכנולוגי של קליפורניה (קלטק), שם היה גם "עמית-פוטנאם" (Putnam Fellow) ב-1978 בזכות תוצאותיו בתחרות-פוטנאם היוקרתית, וסיים תואר ראשון ב-1981. עבר ל-MIT להשלמת דוקטורט במתמטיקה שימושית, שהשלים ב-1985 בהדרכת פ. תומסון לייטון, על ניתוח הסתברותי של אלגוריתמי אריזת-מכולות (bin packing).
מ-MIT למעבדות בל
אחרי הדוקטורט עבד שור שנת מחקר-בתר-דוקטורט אחת באוניברסיטת קליפורניה בברקלי, ולאחריה עבר למעבדות בל (Bell Labs) בניו-פרובידנס, ניו-ג'רזי — אז אחת ממעבדות-המחקר התיאורטי החזקות בעולם, שהעסיקה מתמטיקאים ופיזיקאים לצד מהנדסי-תקשורת. שם, בתחילת שנות ה-90, פנה שור מתחומי-המחקר המוקדמים שלו — אלגוריתמים, גיאומטריה חישובית וקומבינטוריקה — לתחום החדש-אז של חישוב-קוונטי, שהיה עדיין רעיון תיאורטי כמעט בלי יישומים מעשיים ידועים.
אלגוריתם שור, 1994
ב-1994 הציג שור בכנס ה-IEEE Symposium on Foundations of Computer Science (FOCS) ה-35 מאמר בשם "Algorithms for quantum computation: discrete logarithms and factoring", שהתפרסם בגרסה מורחבת בכתב-העת SIAM Journal on Computing באוקטובר 1997. האלגוריתם, המכונה על-שמו "אלגוריתם שור", מראה שמחשב-קוונטי יכול לפרק מספר שלם גדול לגורמים-ראשוניים, ולפתור את בעיית הלוגריתם-הדיסקרטי, בזמן פולינומי — משימות שלכל האלגוריתמים הקלאסיים הידועים אין דרך יעילה לבצען. משמעות התוצאה היא איום ישיר: אבטחת-הצפנת RSA מבוססת בדיוק על הקושי החישובי בפירוק-מספרים-שלמים לגורמים, כך שמחשב-קוונטי גדול ויציב-מספיק שירוץ את אלגוריתם שור יוכל לשבור מפתחות-RSA בפועל. בדצמבר 2024 הציגה מעבדת בינה מלאכותית קוונטית (Quantum AI) של גוגל את השבב Willow, בעל 105 קיוביטים, שבו שיעור השגיאות ירד בחצי בכל הגדלה של רשת הקיוביטים, צעד בדרך למחשב קוונטי גדול ויציב מהסוג שהאלגוריתם דורש.
קריירה ב-MIT
שור הצטרף לסגל-ההוראה של המחלקה למתמטיקה ב-MIT ב-2003, ומשמש כיום כפרופסור על-שם הנרי אדמס מורס (Henry Adams Morss Professor) למתמטיקה שימושית, וחבר במעבדת מדעי-המחשב ובינה מלאכותית (CSAIL) של המוסד. מחקרו הנוכחי ממשיך לעסוק בתורת-האינפורמציה הקוונטית ובאלגוריתמים קוונטיים נוספים, מעבר לאלגוריתם שנושא את שמו.
פרסים והשפעה
על תרומתו התיאורטית זכה שור בפרס נבנלינה (Nevanlinna Prize) ב-1998, בפרס גדל (Gödel Prize) ב-1999, ובאותה שנה גם במלגת-קרן-מקארתור (MacArthur Fellowship). ב-2017 הוענקה לו מדליית דיראק של המרכז הבינלאומי לפיזיקה תיאורטית (ICTP), וב-2023 זכה בפרס-הפריצה בפיזיקת-היסוד (Breakthrough Prize in Fundamental Physics) על תרומתו לחישוב קוונטי. האיום שהאלגוריתם שלו מציב על RSA ועל שיטות-הצפנה דומות מהווה כיום אחד הגורמים המרכזיים למחקר הפעיל בתחום ה"קריפטוגרפיה הפוסט-קוונטית" — שיטות-הצפנה חדשות שנועדו לעמוד גם מול מחשב-קוונטי עתידי.
📬 הגיליון השבועי של Wiki-AI
פעם בשבוע, ביום ראשון: שלושת הדברים החשובים שקרו בעולם הבינה המלאכותית, בעברית פשוטה, וערכים חדשים באנציקלופדיה. לגיליונות
שאלות נפוצות ❓
מה זה אלגוריתם שור?
אלגוריתם קוונטי שפיתח פיטר שור ב-1994, המאפשר למחשב-קוונטי לפרק מספרים שלמים גדולים לגורמים-ראשוניים בזמן פולינומי — משימה שלאלגוריתמים קלאסיים אין דרך יעילה לבצע.
למה אלגוריתם שור מאיים על RSA?
כי אבטחת RSA מבוססת על הקושי החישובי בפירוק מספרים גדולים לגורמים; מחשב-קוונטי גדול ויציב-מספיק שירוץ את אלגוריתם שור יוכל לפרק מפתחות-RSA ולשבור את ההצפנה.
היכן פיתח שור את האלגוריתם שלו?
במעבדות בל (Bell Labs) בניו-ג'רזי, בתחילת שנות ה-90, אחרי שהשלים דוקטורט ב-MIT ב-1985 ושנת מחקר-בתר-דוקטורט בברקלי.
באילו פרסים זכה שור?
בין השאר בפרס נבנלינה (1998), פרס גדל (1999), מלגת-מקארתור (1999), מדליית דיראק (2017), ופרס-הפריצה בפיזיקת-היסוד (2023).