הצפנת רבין – הבדלי גרסאות

: <math>\ \left(\frac{b^2-4a}{p} \right)=-1</math>,

: כמחצית האלמנטים ב-<math>\ \mathbb{Z}_p</math> עונים על דרישה זו, כך שנדרשים בממוצע כשני ניסיונות כדי למצוא <math>\ b</math> מתאים.

* מגדירים את ה[[פולינום]] <math>\ f(x)=x^2-bx+a</math> ב[[שדה (מבנה אלגברי)|שדה]] <math>\ \mathbb{Z}_p[x]</math>.

* מחשבים את <math>\ r = x^{(p+1)/2} \mbox{ mod }f</math>.

:מצא שלם <math>\ x</math> המקיים: <math>\ x^2 \equiv q \ (\mbox{mod }n)</math>.

 

 

אם נסמן <math>q=x^2</math> (מודולו <math>n</math>) הוא 'שארית ריבועית'. משפט רבין אומר שאם אפשר למצוא שורש ריבועי של <math>q</math> עבור 1% מכל השאריות הריבועיות ב-<math>\mathbb{Z}_n</math> אזי אפשר לפרק לגורמים את <math>n</math> בזמן פולינומי. ההוכחה היא, נניח שנתונה קופסה שחורה <math>B</math> כך כאשר מזינים קלט <math>q</math> מחזירה את השורש הריבועי שלו באחוז אחד מהמקרים, אזי אפשר לבצע את הניסוי הבא: בוחרים <math>i</math> אקראי כלשהו ב-<math>Z_n</math> ומזינים ל-<math>B</math> את <math>q=i^2</math> (מודולו <math>n</math>) אם התוצאה אינה <math>i</math> או <math>-i</math> אזי אפשר לפרק את <math>n</math> בגלל העובדה שאם נתונים <math>x,y\in Z_n</math> כך שמתקיים <math>x^2\equiv y^2</math> אך <math>x\ne \pm y</math> (מודולו <math>n</math>) אזי <math>\mbox{Gcd}(n, x\pm y)</math> הוא גורם ראשוני לא טריוויאלי של <math>n</math>. Gcd היא [[מחלק משותף מקסימלי]]. מספר הניסיונות הממוצע הוא 2, היות שכמחצית מהאלמנטים ב-<math>Z_n</math> הם שורשים ריבועיים, מכאן שהסיכויים לפרק את <math>n</math> הם 50%. לכן מספיק יהיה להוכיח שאפשר לפרוץ את הצפנת רבין רק ב-1% סיכויי הצלחה כדי לפרק את <math>n</math> לגורמים ומכאן שאם פירוק לגורמים היא בעיה קשה, הצפנת רבין תהיה קשה גם היא.