ראשי » מדע ומחשבים » מדע » חלל ופיזיקה

סיבוכיות החישוב – בעיות מסוימות קשות לחישוב אך רלוונטיות להצפנה

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

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

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

אז אם Q*K=703, מהם Q ו-K? האם זו בעיה קלה לפתרון?

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

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

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

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

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

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

>>> בחזרה לידיעת הראשית על המחשבים הקוונטיים
היכנסו לעמוד הפייסבוק החדש של nrg

נא להמתין לטעינת התגובות

מעדכן תגובות...