mersenneforum.org Pollard Rho Help?
 Register FAQ Search Today's Posts Mark Forums Read

 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. } 
 2005-08-23, 20:03 #2 akruppa     "Nancy" Aug 2002 Alexandria 246710 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 At the second iteration, you get a difference of 0 (mod 4), thus a gcd with N discovers the divisor 4. It is quite possible that Pollard rho discovers several small primes factors in the same iteration. If you re-run 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 2005-09-24 at 19:06 Reason: s/third/second/
2005-08-23, 21:14   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001101002 Posts

Quote:
 Originally Posted by akruppa The squence of values (mod 4) taken by t1, t2 is Code: Iter.: 0 1 2 t1: 1 2 1 t2: 1 1 1 At the third iteration, you get a difference of 0 (mod 4), thus a gcd with N discovers the divisor 4. It is quite possible that Pollard rho discovers several small primes factors in the same iteration. If you re-run 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 tho function. Alex

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post snme2pm1 Information & Answers 2 2017-12-24 01:52 henryzz Math 2 2017-08-15 12:13 Joe O Factoring 9 2016-09-18 15:42 rogue Math 6 2012-09-26 11:20 AnoNYStudent Homework Help 26 2011-12-07 00:18

All times are UTC. The time now is 01:40.

Thu Sep 29 01:40:13 UTC 2022 up 41 days, 23:08, 0 users, load averages: 0.57, 0.93, 1.07