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

ב[[תורת המספרים]] וב[[קריפטוגרפיה]], '''אלגוריתם רו של פולרד ללוגריתמים''' (באנגלית: Pollard’s rho algorithm for logarithms) הוא [[אלגוריתם הסתברותי]] לחישוב [[לוגריתם]] [[מתמטיקה בדידה|בדיד]] ב[[חבורה ציקלית]] סופית מסדר [[מספר ראשוני|ראשוני]] עם [[סיבוכיות זמן|זמן ריצה]] דומה לשיטת [[כוח גס]] גנרית הנקראת [[בעיית הלוגריתם הבדיד#אלגוריתם צעד-קטן צעד-גדול|אלגוריתם צעד-קטן צעד-גדול]] אך עם צריכת זיכרון שולית ביחס אליה. האלגוריתם פותר את [[בעיית הלוגריתם הבדיד]] בהיסתברות גבוהה, בסיבוכיות בסדר גודל של <math>O(\sqrt{n})</math> כאשר <math>n</math> הוא [[סדר (תורת החבורות)|סדר]] החבורה. לצורך אלגוריתם פולרד ההנחה היא שסדר החבורה הוא [[מספר ראשוני]], שאם לא כן, אפשר בשילוב עם [[אלגוריתם פוליג-הלמן]] לפתור את בעיית הלוגריתם הבדיד בזמן ריצה שהוא בסדר גודל <math>O(\sqrt{p})</math> כאשר <math>p</math> הוא [[גורם ראשוני|הגורם הראשוני]] הגדול ביותר של <math>n</math>.