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

אם נסמן <math>q=x^2\pmod{n}</math> הוא 'שארית ריבועית' (quadratic residue) מודולו <math>n</math>. משפט רבין אומר שאם אפשר למצוא שורש ריבועי של <math>q</math> עבור 1% מכל השאריות הריבועיות ב-<math>Q_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 \pmod{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> לגורמים ומכאן שאם פירוק לגורמים היא בעיה קשה, הצפנת רבין תהיה קשה גם היא.