|
==Richard Brent's variant==
In 1980, [[Richard Brent (scientist)|Richard Brent]] published a faster variant of the rho algorithm. He used the same core ideas as Pollard, but he used a different method of cycle detection, thatreplacing was[[Floyd's fastercycle thanfinding Floydalgorithm]] with the related [[Cycle_detection#Brent.27s_algorithm|Brent's originalcycle algorithmfinding method]].
Brent's algorithm is as follows:
'''Input''': ''n'', the integer to be factored; ''x''<sub>0</sub>, such that 0 ≤ ''x''<sub>0</sub> ≤ n; ''m'' such that ''m'' > 0; and ''f''(''x''), a pseudo-random function modulo ''n''.
'''Output''': a non-trivial factor of ''n'', or failure.
# ''y'' ← ''x''<sub>0</sub>, ''r'' ← 1, ''q'' ← 1.
# Do:
## ''x'' ← ''y''
## For ''i'' = 1 To ''r'':
### ''y'' ← ''f''(''y'')
##''k'' ← 0
## Do:
### ''ys'' ← ''y''
### For ''i'' = 1 To min(''m'', ''r'' − ''k''):
#### ''y'' ← ''f''(''y'')
#### ''q'' ← (''q'' × |''x'' − ''y''|) mod ''n''
### ''g'' ← GCD(''q'', ''n'')
### ''k'' ← ''k'' + ''m''
## Until (''k'' ≥ ''r'' or ''g'' > 1)
## ''r'' ← 2''r''
# Until ''g'' > 1
# If ''g'' = ''n'' then
## Do:
### ''ys'' ← ''f''(''ys'')
### ''g'' ← GCD(|''x'' − ''ys''|, ''n'')
## Until ''g'' > 1
# If ''g'' = ''n'' then return failure, else return ''g''
==In practice==
| 