אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות

במקרה של [[עקום קובליץ]] <math>E_a</math> מעל <math>\mathbb{F}_2</math> שהוא עקום פופולרי בתקנים של [[NIST]] ו[[סרטיקום]], [[הומומורפיזם פרובניוס|העתקת פרובניוס]] <math>\tau:E_a(\mathbb{F}_{2^m})\rightarrow E_a(\mathbb{F}_{2^m})</math> המוגדרת על ידי <math>\tau(\mathcal{O})=\mathcal{O}</math> וכן <math>\tau(x,y)=(x^2,y^2)</math> גם היא אוטומורפיזם של חבורה מסדר <math>m</math> והיא קלה לחישוב היות שהעלאה בריבוע היא פעולה קלה בשדה הבינארי (בהצגה פולינומית העלאה בריבוע מודולו 2 שקולה למעשה להכנסת אפסים בין כל הספרות לסירוגין). אם <math>P\in E_a</math> הוא מסדר ראשוני <math>n</math> כך ש-<math>n^2</math> אינו מחלק של סדר העקום המסומן ב-<math>\#E_a</math> אז <math>\tau(P)\in\langle P\rangle</math> ולכן <math>\tau</math> היא אוטומורפית. יהי <math>\mu=(-1)^{1-a}</math> אפשר להוכיח שאחד מהפתרונות <math>\lambda</math> של המשוואה המודולרית <math>\lambda^2-\mu\lambda+2\equiv 0\text{ (mod }n)</math> מקיים <math>\tau(P)=\lambda P</math>. לכן באופן דומה, הגרסה המקבילית של אלגוריתם רו עם <math>M</math> מעבדים המשתמשת במחלקות השקילות תחת העתקת פרובניוסמגיעה לזמן ריצה של