Pollard rho with known factor of P-1

[henryzz]

Prime Numbers a Computational Perspective by C&P lists as a research problem an extension to pollard rho that finds a factor faster if you know one of the factors of P-1. Would this be helpful for factoring Mersenne numbers as we know a divisor of P-1 or would the cost still be too high?
This is research question 5.24 in http://thales.doa.fmph.uniba.sk/maca...oli/primes.pdf on pages 255 to 256

[xilman]

Originally Posted by henryzz

Prime Numbers a Computational Perspective by C&P lists as a research problem an extension to pollard rho that finds a factor faster if you know one of the factors of P-1. Would this be helpful for factoring Mersenne numbers as we know a divisor of P-1 or would the cost still be too high?
This is research question 5.24 in http://thales.doa.fmph.uniba.sk/maca...oli/primes.pdf on pages 255 to 256

My gut feeling is that rho would still be an exponential algorithm with a relatively high power of ln(N) even with the improvements suggested in 5.24 or 5.25. As such, it would be very unlikely to be competitive with ECM.

Added in edit: to clarify, my gut feeling is that modified rho would be uncompetitive with ECM.

[henryzz]

Originally Posted by xilman

My gut feeling is that rho would still be an exponential algorithm with a relatively high power of ln(N) even with the improvements suggested in 5.24 or 5.25. As such, it would be very unlikely to be competitive with ECM.

Added in edit: to clarify, my gut feeling is that modified rho would be uncompetitive with ECM.

I was more thinking in comparison to P-1 which is also an exponential algorithm. The problem is that there is a load of arithmetic that would need doing modulo N. Each iteration would be equivalent in cost to a few LL iterations.