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

תחילה מחלקים את <math>G</math> לשלוש קבוצות בגודל זהה בקירוב <math>S_1,S_2,S_3</math>, בחלוקה לוגית בהתבסס על כלל מנחה קל לבדיקה. אפשר למשל לחלק לפי משקלו של כל אלמנט באופן הבא הקבוצה <math>S_1</math> תכיל את כל האלמנטים: <math>\textstyle 0<x_i<\frac{1}{3}n</math>, הקבוצה <math>S_2</math> את האלמנטים <math>\textstyle\frac{1}{3}n<x_i<\frac{2}{3}n</math> והשלישית <math>\textstyle\frac{2}{3}n<x_i<n</math>. דרך אחרת יותר יעילה היא לחלק לפי הערך של <math>t</math> הסיביות הכי פחות משמעותיות של כל <math>x_i</math> כאשר <math>t</math> תלוי במספר החלוקות (במקרה זה מספיק לבחון את שתי הסיביות האחרונות). מספר החלוקות שרירותי וניתן לשינוי, אך יש צורך לשים לב לכמה היבטים חשובים בנוגע לחלוקה למשל <math>1\notin S_2</math>.

 

:<math>x_{i+1}=f(x_i)\overset{\underset{\mathrm{def}}{}}{=}\begin{cases}

\beta\cdot x_i, & \mbox{ if }x_i\in S_1 \\