Pollard Rho factorization method implementation

Question

Every time I factor a number using Pollard Rho factorization method is it necessary to check for its primality before Pollard Rho factorization ? If yes then I have to implement Miller Rabin's primality test or any primality test each time I want to factor any number and stil I have to take care of strong pseudoprimes , isn't it complex ? Is there any simpleand still faster way to handle this ? (I am using these tests on numbers upto 10 digits)

Answer 1

Yes, you must check before you apply Pollard Rho that the number you are factoring is composite. If it is prime, the gcd step will always return 1, because a prime number is always co-prime to every other number, and Pollard Rho will run forever without result.

For numbers up to ten digits, Pollard Rho is not necessary. Simple trial division will be quick enough, since you only need the primes less than 100000, and there are only 9592 of them.