Thread: Pollard Rho Help? View Single Post
 2005-08-23, 19:47 #1 theta   Aug 2005 2 Posts 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;kcharvalue) 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. }