I have been reading about pollard rho factorization, however their is something I don't understand if we don't use a polynomial that is pick two random numbers and see the gcd(a-b,n) > 1 if it is bigger than 1,then we divide n by gcd(a - b,n) and we will get another factor of n d.
However doing this by the kth iteration we will have k - 1 greatest common divisor checks, however if we choose a polynomial(mod n) that will generate our random then we won't have to do k - 1 greatest common divisor checks. I don't understand why is that if someone could explain to me that would be good.
The Pollard rho method is based on two assumptions:
1) We have a deterministic recursive PSEUDO-random sequence mod n where the next value in the sequence is uniquely determined by the previous value (for example, by applying a polynomial and then taking the remainder mod n)
2) The pseudo-random sequence is sufficiently "random" with respect to the problem of factoring n that we can allow analysis assuming true randomness.
Then, instead of computing gcd() for all pairs of numbers generated so far, you only need to compute the gcd of 2 numbers at each iteration, assuming that the first number is obtained by successively iterating the pseudo-random number generator 1 step at a time, and the second number is obtained by successively iterating the pseudo-random number generator 2 steps at a time. To see why this works, and why you don't need to compute more gcd()'s look up the proof of the Pollard rho method. The essence of the proof is that if you have a cycle mod a divisor p of n in the iterated pseudo-random number generator, then the method will find the non-trivial gcd p in linear time in terms of the length of the initial segment of the trajectory and the length of the cycle.