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

מתוך קבוצת ה-(Q(x אנחנו מחפשים תת-קבוצה של מספרים, שמכפלתם היא ריבוע ידוע: <math>Q \left(x_{i_1}\right) \cdot Q \left(x_{i_2}\right) \cdot Q \left(x_{i_3}\right) \cdot ... \cdot Q \left(x_{i_r}\right) = y^2 </math>. ברגע שמטרה זו הושגה, מתקיים <math>\overset{\sim}{x}^2 \left(mod\ n\right) \equiv Q \left( x \right)</math>, ולכן גם <math>

Q \left(x_{i_1} \right) \cdot Q \left( x_{i_2} \right) \cdot Q \left( x_{i_3} \right) \cdot \ldots \cdot Q \left(x_{i_r}\right)

</math>; כך מצאנו x ו-y מתאימים לדרישות. אם המספר n הוא מכפלה של שני מספרים ראשוניים גדולים, אז מתקיים בהסתברות ½ <math>x \equiv \pm y \left(mod\ n\right)</math>, ואז תוצאת ה-GCD תהיה n או 1; במקרה כזה יש להמשיך את תהליך הייצור, ולמצוא זוג אחר של מספרים כמתואר לעיל.