אלגוריתם שור – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין מילה כזאת "פיקטור" |
מ ←השלב הקלאסי: תקלדה |
||
שורה 38:
#אחרת, בדוק האם <math>a^{r/2}\equiv -1 \ (mod\ N)</math>.
##אם כן - חזור ל1.
##אחרת, ל<math>a^{r/2}\pm 1</math> גורם ראשוני משותף עם N. חשב <math>\ gcd(a^{r/2}\pm 1,N)</math> וקבל גורם ראשוני של N.
::('''הסבר''': אם <math>\ r</math> מחזור של <math>\ f(x)</math> אזי <math>\ a^r \equiv 1\ (mod\ N)</math>, כלומר, <math>\ a^r-1\equiv 0</math>. נפתח את הביטוי:
<div style="text-align: center;">
| |||