אלגוריתם רו של פולרד ללוגריתם הבדיד
ויקיפדיה האנציקלופדיה encyclopedia
בתורת המספרים ובקריפטוגרפיה, אלגוריתם רו של פולרד ללוגריתם הבדיד (באנגלית: Pollard’s rho algorithm for discrete logarithms) הוא אלגוריתם הסתברותי לחישוב לוגריתם בדיד בחבורה ציקלית סופית מסדר ראשוני עם זמן ריצה דומה לשיטת כוח גס גנרית הנקראת אלגוריתם צעד-קטן צעד-גדול אך עם צריכת זיכרון שולית ביחס אליה. האלגוריתם פותר את בעיית הלוגריתם הבדיד בהסתברות גבוהה, בסיבוכיות בסדר גודל של כאשר הוא סדר החבורה. לצורך אלגוריתם פולרד ההנחה היא שסדר החבורה הוא מספר ראשוני, שאם לא כן, אפשר בשילוב עם אלגוריתם פוליג-הלמן לפתור את בעיית הלוגריתם הבדיד בזמן ריצה שהוא בסדר גודל כאשר הוא הגורם הראשוני הגדול ביותר של .