Prime Factorization of Large Numbers

The prime factorization of large numbers is a topic that has been in the back of my mind for some time now. A few years back, a colleague of mine introduced me to the domain via the RSA Challenges that were available at the time. At that point, I got to the point of understanding the basic shape of the problem, but wasn’t able to make any progress. (Just like the rest of the world.)

Even though it doesn’t count as progress in the world-wide point-of-view, I have recently gained additional insight into the problem, and though it interesting enough to add to my site…

To me, the whole concept of composite numbers is represented in the following graph (blue line).

Any natural number (N) can be described with the graph of ‘Y=N/X, so that X*Y = N. The only trick is to figure out as to which integer combinations of X and Y equal N.

With this as a starting point, the idea would be to find a way to identify the integer values of X and Y that produce N. In this attempt, I started looking at how close the curve gets to an integer value of Y as is passes through its X values. To do this, I created the following simple program, with test values inserted into the code.

import java.io.BufferedWriter;

import java.io.FileWriter;

import java.io.IOException;

import java.io.PrintWriter;

public class RemainderUtil {

/**

* @param args

* @throws IOException

public static void main(String[] args) throws IOException {

FileWriter fstream = new FileWriter("C:/sandbox/primefactorizarion/out.txt");

PrintWriter out = new PrintWriter(fstream);

Integer compositeNumber = 3; // 91=13*7, 221=13*17 35=7*5

double squareRoot = Math.sqrt(compositeNumber);

out.println("Starting point is " + squareRoot + ".");

out.println("Ending point is " + compositeNumber + ".");

double x = 1;

double xEnd = squareRoot;

out.println(" x yDecm");

out.println("--------------------------");

while(x<xEnd) {

double y = compositeNumber/x;

long yRound = Math.round(y);

double yDecm = Math.abs(y - yRound);

out.println(" " + x + " " + yDecm);

x = x + .001;

}

// Close the output stream

out.close();

}

I then took the graph results and used MS Excel to graph them out. For N=35, I got the following result.

The interesting bit that this saw tooth graph shows is that the ‘period’ of the wave is increasing. The rate at which it is proportional to the Y=N/X curve. This should allow the position of the valleys of the curve to be predictable. By looking at this graph, you can easily tell that ‘5’ might be a factor for this value of N, but that 2,3,4, and 6 are not candidates. An approach of mapping out the formula for this curve might result in being able to predict the intersection of the curve with integer results. (Or maybe just eliminating large groups of results in a sieve-like approach.)

This is a slow-moving work in progress…

Comments