Decreasing Size of Parameter for Computing Greatest Common Divisor to Speed up New Factorization Algorithm Based on Pollard Rho

Pollard Rho is one of integer factorization algorithms for factoring the modulus in order to recover the private key which is the one of two keys of RSA and is kept secret. However, this algorithm cannot finish all values of the modulus. Later, New Factorization algorithm (NF) which is based on Pollard Rho was proposed to solve the problem of Pollard Rho that cannot finish all value of the modulus. Nevertheless, both of Pollard Rho and NF have to take time – consuming to find two large prime factors of the modulus, because they must compute the greatest common divisor for all iterations of the computation. In this paper, the method to speed up NF is presented by reducing the size of the parameter which is used to be one of two parameters to compute the greatest common divisor. The reason is, if the size of one of two parameters is reduced, the computation time for computing the greatest common divisor is also decreased. The experimental results show that the computation time of this method is decreased for all values of the modulus. Moreover, the average computation time of the proposed method for factoring the modulus is faster than NF about 6 percentages.