View Single Post
Old 2005-08-23, 19:47   #1
Aug 2005

2 Posts
Default Pollard Rho Help?

Greetings all,

My apologies to all. I posted this same thread in the 'Programming' section. In retrospect, I would have been better off initially posting it here. My sincerest apologies to the moderators.

I wrote the following implementation of Pollard's Rho algorithm for my Number Theory class last semester.
Although I think the algorithm is correct, something does not seem right. The program will factor some
numbers completely, while it does not for others. For example, it will factor 2444141 as 7*17*19*23*47;
however, it will factor 20 as 4*5. In some instances, the factors themselves do not factor. I feel as
though this should not happen because I have used recursion in the program to test each factor once they
are found.

I am really hoping one of the many fresh, bright minds on this messageboard will be able to give me a new
perspective and some much needed insight. Despite the fact that the assignment is over, I have been
dwelling on this for months now. I am very eager and curious as to how to resolve the issue. I am
beginning to believe I am missing something trivial, if not for an actual error in the algorithm. Am I missing
something silly like a return statement? All questions and comments are welcome. Below is the Java source
code. Thank you in advance for your time, help, and advice.

import java.math.BigInteger;

public class Rho



	//pre condition:  factor(n) accepts a BigInteger from the main.  After the variables are initialized, the 
	//function then generates two values, t1 and t2, using the polynomial function f(x)=x^2 + 1.
	//Once these values are calucated, their gcd is found using the built in gcd function in the BigInteger
	//class.  NOTE:  I had made a gcd function in an earlier assignment, but neglected to implement it here.
	//Because I had issues with taking the square root of a BigInteger, the for-loop in this method runs
	//exceedingly long--from k=0 to k=n-1.  If the gcd is greater than 1 and less than n, the function prints
	//out the factor and then recursively calls itself to find the (n/g) factor.  This repeats until all of the 
	//factors are found.

	public static BigInteger factor(BigInteger n)

		BigInteger g= BigInteger.valueOf(0);
		BigInteger t1=BigInteger.valueOf(1);
		BigInteger t2=t1;

		for(int k=0;(BigInteger.valueOf(k)).compareTo(n)<0;k++)

			t1 = ((t1.multiply(t1)).add(BigInteger.ONE)).mod(n);
			t2 = ((t2.multiply(t2)).add(BigInteger.ONE)).mod(n);
			t2 = ((t2.multiply(t2)).add(BigInteger.ONE)).mod(n);

			if(g.compareTo(BigInteger.ONE)>0 && g.compareTo(n)<0)

				return factor(n.divide(g));




		return n;


	//post condition: The function returns a BigInteger back to the main


	//pre condition:  verifyInput(x) accepts a string x, which is sent from the main.  This function
	//checks to see if each character of the input is a digit from 0-9. By converting the character
	//into its ASCII value, the function then checks to see if it falls between the range (47,57]; these
	//are the ASCII values from the digits 0-9;

	public static boolean verifyInput(String x)

		int charvalue;
		boolean flag=true;

		for(int k=0;k<x.length() && true==flag;k++)		


			if(47<charvalue && 58>charvalue)
				flag = true;	

				flag = false;


		return flag;


	//post condition:  The function returns a boolean value to the main.  True indicates that
	//the input is valid; false indicates that there is an error.


	//pre condition: The program is initialized here.  The user is asked to input a number with no
	//spaces or characters.  Once the user inputs the number, the function verifyInput tests to see
	//if the input is valid.  If it is, the program continues; if not, the user is asked to enter the 
	//number again.  The main then calls the function factor(n) and sends the number n that the user
	//entered.  Upon factoring,the main asks the user whether or not to terminate the program.

	public static void main(String []args) throws IOException

		BigInteger n,f;
		String response,x;
		boolean valid;

		BufferedReader infile = new BufferedReader(new InputStreamReader(;





				System.out.println("Enter a postive integer you wish to factor ");
				x = infile.readLine();

				valid = verifyInput(x);

					System.out.println("Invalid input.  Possible digits are 0-9; no spaces or 


		n=new BigInteger(x);

		if(n==f)System.out.println(n+" is a prime.");

		else System.out.println(f);

		System.out.println("Would you like to try again? Y/N");





	//post condition:  This function is void and returns nothing.


theta is offline   Reply With Quote