mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Pollard Rho Help? (https://www.mersenneforum.org/showthread.php?t=4546)

 theta 2005-08-23 19:47

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]
[SIZE=1]
import java.math.BigInteger;
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++)

{

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;

do

{

do

{

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

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

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

}

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

}
[/SIZE]
[/CODE]

 akruppa 2005-08-23 20:03

The squence of values (mod 4) taken by t1, t2 is

[CODE]
Iter.: 0 1 2
t1: 1 2 1
t2: 1 1 1
[/CODE]

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

 R.D. Silverman 2005-08-23 21:14

[QUOTE=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
[/CODE]

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[/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.

 All times are UTC. The time now is 05:05.