Home‎ > ‎Random Thoughts‎ > ‎

### 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