אלגוריתם שור

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

אלגוריתם שוֹר (Shor - על שם פיטר שור, ממציאו), הוא אלגוריתם קוונטי המשמש לפירוק לגורמים של מספר גדול, כלומר מציאת הגורמים הראשוניים של המספר. האלגוריתם פורסם לראשונה על ידי פיטר שור[1] בשנת 1994, ויחד עם אלגוריתם גרובר נחשב לאחד משני האלגוריתמים החשובים ביותר בתחום החישוב הקוונטי.[2] פיתוח האלגוריתם זיכה את ממציאו בפרס גדל (1999). אלגוריתם שור מבוסס על הרעיונות הקוונטיים שהודגמו באלגוריתם סימון למציאת מחזור של פונקציה. האלגוריתם משתמש בהתמרת פורייה קוונטית (QFT), על מנת לקבל מחזור שהוא כפולה של אחד מהגורמים הראשוניים של המספר אותו רוצים לפרק.

האלגוריתמים הטובים ביותר הידועים, מפרקים מספר גדול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ,לגורמיו בסיבוכיות זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(e^{(\log(n))^{1/3}(\log\log(n))^{2/3}})} , שאינה פולינומית ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\log(n))} . לעומת זאת, אלגוריתם שור פועל בסיבוכיות זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\log^3(n))} . אלגוריתם זה מהווה דוגמה ליתרון אקספוננציאלי בסיבוכיות הזמן של אלגוריתמים קוונטיים לעומת אלגוריתם קלאסי.

השלכות ומשמעויות

שימוש באלגוריתם זה על מנת לפרק מספרים גדולים מהווה איום על אלגוריתמים מתחום ההצפנה האסימטרית, אשר מושתתים על פעולות מתמטיות עם מספרים גדולים, כגון RSA‏ ו-DSA. שיטות אלו מסתמכות על מספר גדול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ N} בן 512–8192 סיביות (מספר בעל מאות ספרות), אשר ידוע לכלל. הגורמים הראשוניים של מספר זה מהווים את המפתח הסודי. שימוש באלגוריתם שור מאפשר מציאת המפתח באופן יעיל, כלומר, במספר "קטן" יחסית של פעולות. מסיבה זו נעשים מאמצים למצוא חלופות פוסט קוונטיות לאלגוריתמים הקיימים, כדי לתת מענה הולם כאשר המחשבים הקוונטיים יהיו מעשיים בקנה מידה המהווה איום מוחשי.

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

תיאור האלגוריתם לפירוק המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ N}

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

השלב הקלאסי

  1. בחר מספר כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a < N} .
  2. בדוק האם ‎gcd (a, N) ≠ 1‏. אם כן - מצאנו גורם, סיים.
  3. אם לא, בצע את השלב הקוונטי על מנת למצוא את המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} , שהוא המחזור של הפונקציההפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=a^x \mod N}
  4. אם המספר r המתקבל אי-זוגי, חזור לסעיף 1.
  5. אחרת, בדוק האם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{r/2}\equiv -1 \ (mod\ N)} .
    1. אם כן - חזור ל-1.
    2. אחרת, להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{r/2}\pm 1} גורם ראשוני משותף עם N. חשב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ gcd(a^{r/2}\pm 1,N)} וקבל גורם ראשוני של N.
(הסבר: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} מחזור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)} אזי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a^r \equiv 1\ (mod\ N)} , כלומר, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a^r-1\equiv 0} . נפתח את הביטוי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (a^{r/2}-1)(a^{r/2}+1) = kN = kN_pN_q}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ N=N_pN_q} , הגורמים של N).

השלב הקוואנטי

בחר מספר Q כך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N^2 \le Q \le 2N^2 } וכן Q הוא חזקה שלמה של 2, כלומר ניתן לכתיבה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Q=2^q} עבור q מספר טבעי. 1. אתחל שני אוגרים קוונטים, בגודל q קיוביטים כל אחד, למצב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|0\rangle}

שהוא סופרפוזיציה של Q מצבים.

2. הפעל את הפונקציה הקוונטית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)} על האוגרים, לקבלתהפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|f(x)\rangle} 3. בצע התמרת פורייה קוונטית על האוגר הראשון. מהתמרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x\rangle} מקבלים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q^{-1/2} \sum_y \omega^{x y} \left|y\right\rangle} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \omega^i=e^{2\pi i/Q}} , ועל כן מצב האוגרים לאחר הפעלת השער הוא סופרפוזיציה של הרבה יותר מ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Q} מצבים, אך הרבה פחות מ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Q^2} : הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q^{-1} \sum_x \sum_y \omega^{x y} |y\rangle |f(x)\rangle}

4. בצע מדידה. מתקבל ערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y_m} כלשהו וערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x_0)} כלשהו. ההסתברות למדוד את הזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y_m, f(x_0)} נתונה על ידי

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| Q^{-1} \sum_{x:\, f(x)=f(x_0)} \omega^{x y} \right|^2 = Q^{-2} \left| \sum_{b} \omega^{(x_0 + r b) y} \right|^2}

הסתברות זו נובעת מקיומם של ערכים רבים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} עבורם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)=f(x_0)} , כאשר כל האיברים הללו תורמים להסתברות למדוד את אותו המצב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |f(x_0)\rangle} . החלק הימני של השוויון נובע מהעובדה שהפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)} מחזורית, בעלת מחזור r (בהנחה שהאבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0} הקטן ביותר באותו מחזור, וb מקבל ערכים מ-0 עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [Q-x_0-1]/r} , אז הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0+r\cdot b} כלל ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} ים הקטנים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ Q} המקיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)=f(x_0)} ).

5. מצא מספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c} ומספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r'} , כך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r' < N} ו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c/r'} קרוב מאד להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y/Q} , ובאופן מפורש, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |y/Q-c/r'|<1/2Q} .

6. קיים סיכוי גבוה מאד כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r'} הוא המחזור המבוקש. בדוק האם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)=f(x+r')} . אם כן, סיים. אם לא - חזור על ביצוע האלגוריתם.

קישורים חיצוניים

הערות שוליים

  1. ^ גרסה מתוקנת ומשופרת של המאמר של פיטר שור פירוק לראשוניים של מספרים בזמן פולינומי על ידי מחשב קוונטי (באנגלית)
  2. ^ שחר דולב, מהו מחשב קוונטי, באתר גלילאו 77, ‏01/2005
  3. ^ [1]
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=אלגוריתם_שור&oldid=449337"