This project is read-only.

FactoringBigNumber Q&A

Apr 16, 2009 at 3:04 PM
What is FactoringBigNumber?
The FactoringBigNumber is an implementation of a big integer number by factoring the original number into its prime factors.

Are you crazy? If you know a fast method of factoring you should break RSA and not write .NET libraries.
No, I did not find a fast method of factoring. In fact, I currently use the slowest method possible just to test the concept.

What is the concept behind the FactoringBigNumber?
The concept is simple. I relies on a mathematical fact and some observations that may or may not be true (the goal of the implementation is to find out :)
  1. Every integer number can be written as a product of prime factors. This is a fact.
  2. Many algorithms make long intermediate calculations that don't make use of all the numeric data all at once.
  3. Usually we don't need numbers infinitely long, just longer than 64bit (maybe 50 - 100 digits).
This leads to the following idea: given a big number we first try to find the small factors using mathematical laws (that take O(1) or O(n) time to check). Clearly, most integer numbers are divisible by 2,3,5,7 or 11, which are easy to check.
We can represent an integer number by stating how many of each prime factor the number contains in the product and the remainder (the part we didn't factor yet).
For example : The number 587820 = 2^2*3^1*5^1*9797 or in our representation ([2,2][3,1][5,1],9797)
Now the number is ready to be factored!
If the number is one of a much larger calculation, it will now be stored in some Array / List / Dictionary / DCEL. This is where the FactoringManager steps in. When a FactoringBigNumber changes its factoring mode to "Full", the FactoringManager tries to assign it a calculation background thread. In the this thread the remainder (in our example 9797) will be factored and added to the factors table. So after not so long you will get the final number which is :
([2,2][3,1][5,1][97,1][101,1],1) which is fully factored.

But what if the remainder is really long and can't be factored so easily?
Thats OK. Absolutely nowhere in the implementation do we assume that you have a full factorization.
Here is an example of the easiest operator * : when you multiply two factoring numbers you simply merge their tables and multiply the remainders lets say we multiply 587820 = ([2,2][3,1][5,1][97,1],[101,1],1) by 780850 = ([2,1][5,2][7,1][23,1],97) {note that 97 is still in the remainder waiting to be factored) , we add the primes and multiply the remainders ([2,3][3,1][5,3][7,1][23,1][97,1],[101,1],97*1). Now we have a newFactoringBigNumber eligible for factoring and in fact we are going to do so, in the background.

So what you are saying is that I am getting a multi-threaded parallel computation without changing my algorithm?
Sort of. There are still many assumptions made here and the implementation is still very primary but the idea could work.

I hope this helped to demystify the FactoringBigNumber
As usual, idea, comments and help programming will be appriciated.