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

השלם <math>l</math> נקרא '''הלוגריתם הבדידי''' של הנקודה <math>Q</math> בבסיס הנקודה <math>P</math> או בקיצור <math>l=\log_PQ</math>. במידה שהפרמטרים של העקום <math>E</math> נבחרו בזהירות כדי להבטיח שלא יהיו קיצורי דרך לפתרון הבעיה בעקום זה, הדרך הטובה ביותר לפתרונה היא באמצעות אלגוריתם רו של פולרד בסיבוכיות של <math>\sqrt{n}</math>. הסימון <math>\langle P\rangle</math> מייצג את כל הנקודות שהן כפולות של <math>P</math>. (כגון <math>P,2P,3P,4P,...</math> וכן הלאה עד <math>n</math>). במילים אחרות, הנקודה <math>Q</math> היא תוצאה של חיבור הנקודה <math>P</math> בעצמה (הנקראת בקיצור POINT_DBL) בדיוק <math>l</math> פעמים והבעיה היא לגלות כמה פעמים בוצע החיבור, קרי לגלות את ערכו של <math>l</math>. לא קיימת דרך פשוטה לבצע זאת כי המסלול של הנקודות נראה אקראי. שיטת כוח גס אינה מעשית משום שבמקרה הממוצע יש צורך לבדוק לפחות מחצית מהנקודות עד שנמצא <math>lP</math>. אם <math>n\ge 2^{128}</math> כוח גס אינו מעשי. כמובן שיש לשים לב של-<math>n</math> יש לפחות גורם ראשוני אחד גדול דיו. שאם לא כן אפשר לנצל את אלגוריתם פוליג-הלמן בזמן שהוא ביחס ישיר לגודל הגורמים הראשוניים שלו. למעשה ככל שהגורם הראשוני שלו (לפחות אחד מהם), גדול יותר סיבוכיות ההתקפה תהיה גבוהה יותר.