mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-08-23, 19:47   #1
theta
 
Aug 2005

2 Posts
Default 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;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.

	

}
theta is offline   Reply With Quote
Old 2005-08-23, 20:03   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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/
akruppa is offline   Reply With Quote
Old 2005-08-23, 21:14   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiple Pollard second stage snme2pm1 Information & Answers 2 2017-12-24 01:52
Pollard rho with known factor of P-1 henryzz Math 2 2017-08-15 12:13
Pollard rho questions Joe O Factoring 9 2016-09-18 15:42
Pollard Rho Discrete Log rogue Math 6 2012-09-26 11:20
Parallelizing Pollard's P-1 Algorithm AnoNYStudent Homework Help 26 2011-12-07 00:18

All times are UTC. The time now is 17:12.

Sat Feb 27 17:12:21 UTC 2021 up 86 days, 13:23, 0 users, load averages: 3.08, 2.81, 2.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.