אלגוריתם שור

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

האלגוריתמים הטובים ביותר למחשבים בינאריים קלאסיים, מפרקים מספר גדול \ n,לגורמיו בסיבוכיות זמן של \ O(e^{(\log(n))^{1/3}(\log\log(n))^{2/3}}), שאינה פולינומית ב-\ O(\log(n)). לעומת זאת, אלגוריתם שור פועל בסיבוכיות זמן של \ O(\log^3(n)) שהיא קטנה אקספוננציאלית מפירוק במחשב קלאסי.

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

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

במרץ 2026 פרסמו חוקרים ב-Google Quantum AI התקדמות משמעותית בהערכת המשאבים הנדרשים ליישום אלגוריתם שור (ובפרט וריאציות שלו לפתרון בעיית הלוגריתם הדיסקרטי) על עקומות אליפטיות 256-ביט (ECDLP-256) – הבסיס להצפנת ECDSA המשמשת ברוב המטבעות הקריפטוגרפיים. הם תכננו שני מעגלים קוונטיים: אחד הדורש פחות מ-1,200 קיוביטים לוגיים ו-90 מיליון שערי Toffoli, והשני פחות מ-1,450 קיוביטים לוגיים ו-70 מיליון שערים. לפי ההערכות, ניתן לבצע את ההתקפה על מחשב קוונטי בעל פחות מ-500,000 קיוביטים פיזיים (שיפור של פי 20 בהשוואה להערכות קודמות) תוך דקות ספורות בלבד. 

## תיאור האלגוריתם לפירוק המספר <math>\ N</math>
ניתן לחלק את פעולת האלגוריתם לשני שלבים, הראשון הוא השלב קלאסי, הניתן לביצוע על כל מחשב שהוא, והשני שלב קוונטי, אשר מבוצע על מחשב קוונטי.
### השלב הקלאסי
#בחר מספר כלשהו \ a .
#בדוק האם gcd (a, N) ≠ 1. אם כן - מצאנו גורם, סיים.
#אם לא, בצע את השלב הקוונטי על מנת למצוא את המספר \ r, שהוא המחזור של הפונקציהf(x)=a^x \mod N
#אם המספר r המתקבל אי-זוגי, חזור לסעיף 1.
#אחרת, בדוק האם a^{r/2}\equiv -1 \ (mod\ N).
##אם כן - חזור ל-1.
##אחרת, לa^{r/2}\pm 1 גורם ראשוני משותף עם N. חשב \ gcd(a^{r/2}\pm 1,N) וקבל גורם ראשוני של N.
::(**הסבר**: אם \ r מחזור של \ f(x) אזי \ a^r \equiv 1\ (mod\ N), כלומר, \ a^r-1\equiv 0. נפתח את הביטוי:
\ (a^{r/2}-1)(a^{r/2}+1) = kN = kN_pN_q
::כאשר \ N=N_pN_q, הגורמים של N).

### השלב הקוואנטי
בחר מספר Q כך ש N^2 \le Q \le 2N^2  וכן Q הוא חזקה שלמה של 2, כלומר ניתן לכתיבה \ Q=2^q עבור q מספר טבעי.
1. אתחל שני אוגרים קוונטים, בגודל q קיוביטים כל אחד, למצב Q^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|0\rangle
:שהוא סופרפוזיציה של Q מצבים.
2. הפעל את הפונקציה הקוונטית \ f(x) על האוגרים, לקבלתQ^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|f(x)\rangle
3. בצע התמרת פורייה קוונטית על האוגר הראשון. מהתמרת |x\rangle מקבלים Q^{-1/2} \sum_y \omega^{x y} \left|y\right\rangle, כאשר \ \omega^i=e^{2\pi i/Q}, ועל כן מצב האוגרים לאחר הפעלת השער הוא סופרפוזיציה של הרבה יותר מ \ Q מצבים, אך הרבה פחות מ \ Q^2:
Q^{-1} \sum_x \sum_y \omega^{x y} |y\rangle |f(x)\rangle
4. בצע מדידה. מתקבל ערך \ y_m כלשהו וערך \ f(x_0) כלשהו. ההסתברות למדוד את הזוג \ y_m, f(x_0) נתונה על ידי
\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

:הסתברות זו נובעת מקיומם של ערכים רבים של \ x עבורם \ f(x)=f(x_0), כאשר כל האיברים הללו תורמים להסתברות למדוד את אותו המצב |f(x_0)\rangle. החלק הימני של השוויון נובע מהעובדה שהפונקציה \ f(x) מחזורית, בעלת מחזור r (בהנחה שהאבר \ x_0 הקטן ביותר באותו מחזור, וb מקבל ערכים מ-0 עד \ [Q-x_0-1]/r, אז הביטוי \ x_0+r\cdot b כלל ה-\ xים הקטנים מ-\ Q המקיימים \ f(x)=f(x_0)).

5. מצא מספר \ c ומספר \ r', כך ש \ r'  ו \ c/r' קרוב מאוד ל\ y_m/Q, ובאופן מפורש, \ |y_m/Q-c/r'|.

6. קיים סיכוי גבוה מאוד כי \ r' הוא המחזור המבוקש. בדוק האם \ f(x)=f(x+r'). אם כן, סיים. אם לא - חזור על ביצוע האלגוריתם.

## קישורים חיצוניים
* עופר אוחיון, הצעה ומדריך למידה לקורס "מבוא לחישוב קוונטי", הסבר מפורט בעברית על אלגוריתם שור בפרק 9 עמ' 107 ואילך
* 
* 

## הערות שוליים

שור
שור