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.
}