20050823, 19:47  #1 
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 forloop in this method runs //exceedingly longfrom k=0 to k=n1. 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 09. 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 09; 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 09; 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. } 
20050823, 20:03  #2 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
The squence of values (mod 4) taken by t1, t2 is
Code:
Iter.: 0 1 2 t1: 1 2 1 t2: 1 1 1 It is quite possible that Pollard rho discovers several small primes factors in the same iteration. If you rerun the same sequence (i.e. x=x^2+c with the same constant c), it will always rediscover the same primes in the same step, so that sequence will never split composite factors it found itself. The probability of finding composite factors is much smaller if the primes factors are larger. Divide out very small prime factors by trial division first. If you find a composite divisor, try splitting it with a Pollard rho routine that uses a different value for c (but not c=0, c=1 or c=2). You could choose c randomly, or pass it as a parameter to your Pollard rho function. Alex Last fiddled with by akruppa on 20050924 at 19:06 Reason: s/third/second/ 
20050823, 21:14  #3  
"Bob Silverman"
Nov 2003
North of Boston
1110100110100_{2} Posts 
Quote:
Indeed. Let N = k! p, where p is a large prime and k! is also large. I have seen Pollard Rho pull out the entire factor k! in just a few iterations. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Multiple Pollard second stage  snme2pm1  Information & Answers  2  20171224 01:52 
Pollard rho with known factor of P1  henryzz  Math  2  20170815 12:13 
Pollard rho questions  Joe O  Factoring  9  20160918 15:42 
Pollard Rho Discrete Log  rogue  Math  6  20120926 11:20 
Parallelizing Pollard's P1 Algorithm  AnoNYStudent  Homework Help  26  20111207 00:18 