View Single Post
Old 2005-08-23, 19:47   #1
theta
 
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.

Code:
 
import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.*;

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);

			g=((t2).subtract(t1)).gcd(n);
   
			if(g.compareTo(BigInteger.ONE)>0 && g.compareTo(n)<0)

         		{
				System.out.println(factor(g));
				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++)		

		{
			charvalue=((int)(x.charAt(k)));

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

			else
				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.in));

		do

		{

			do

			{	

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

				valid = verifyInput(x);

				if(false==valid)
					System.out.println("Invalid input.  Possible digits are 0-9; no spaces or 
characters.");

			}while(false==valid);

		n=new BigInteger(x);
		f=factor(n);

		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");

		response=infile.readLine();

		}while(response.equalsIgnoreCase("Y"));

		

	}

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

	

}
theta is offline   Reply With Quote