Tuesday, January 22, 2008
JSH: Factoring problem solution, simple explanation
The problem with having a math field that doesn't do its job is that things that should be easy are harder because people in that field, well, seem kind of out of it, especially when you consider the importance of the factoring problem, and as reality does a nice gut check for some of you as you see stock markets around the world swoon to give you some sense of what is at stake.
What I found is a very easy algebraic solution to what is called the factoring problem:
Given a target composite T and integer factors f_1 and f_2, such that f_1*f_2 = nT, and any prime p, the following will be true 75% of the time:
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
where
k^2 = (a^2+1)^{-1}(nT) mod p.
That last equation defines the key variable k, used above, by another variable 'a', where ANY VALUE for it is correct as long as k exists.
That may sound tricky but k^2 means you must have what is called a quadratic residue modulo p on the right side i.e. (a^2+1)^{-1}(nT).
For instance, 4 is a quadratic residue modulo 7 because 2*2 = 4 modulo 7. But so is 2, because
3*3 = 2 mod 7
That is 3*3 = 9 - 7 = 2, so 2 is a quadratic residue modulo 7, but 3 is not because no two residues of 7 can multiply to give 3, and you have an easy finite set as the residues of 7, are just 1, 2, 3, 4, 5, and 6, while 0 is not typically considered a residue. Think of it as there being nothing left with 0, so no residue.
Now the equations I've given count the number of factorizations for nT to give the count of a's that will work to give you a k, where you get either the total number of combinations or twice that number, and of that count 75% of them will give you a factorization of nT, while that may be a trivial factorization.
A trivial factorization is like 15 = 15(1). While the non-trivial factorization is 15 = 3(5).
Of the count of a's you will have either one or two cases for EACH unique factorization.
Those equations solve the factoring problem by giving you multiple ways to factor a given target T, where you can, for instance, let n=1, and then use a lot of small primes p_1, p_2, p_2,..., p_j and something called the Chinese Remainder theorem to solve for the factors, where the size of j is less than m where T/m! < 1.
Or you can change n, to give a lot of combinations of factors, and choose a prime p>sqrt(T).
Either of those approaches could be optimized to be very fast.
If this research is correct, it could mean that an RSA public key could be factored using algorithms based on these equations FASTER than it can be generated and implemented, regardless of its size.
The algebraic derivation of the relations is very, very, very easy, so there is no doubt about their correctness and no doubt about the value of the research. However, there is now serious doubt about the vitality of the mathematical discipline itself as mathematicians seem content for now to not let the world in on the massive discovery.
Though maybe the financial markets figured it out…
What I found is a very easy algebraic solution to what is called the factoring problem:
Given a target composite T and integer factors f_1 and f_2, such that f_1*f_2 = nT, and any prime p, the following will be true 75% of the time:
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
where
k^2 = (a^2+1)^{-1}(nT) mod p.
That last equation defines the key variable k, used above, by another variable 'a', where ANY VALUE for it is correct as long as k exists.
That may sound tricky but k^2 means you must have what is called a quadratic residue modulo p on the right side i.e. (a^2+1)^{-1}(nT).
For instance, 4 is a quadratic residue modulo 7 because 2*2 = 4 modulo 7. But so is 2, because
3*3 = 2 mod 7
That is 3*3 = 9 - 7 = 2, so 2 is a quadratic residue modulo 7, but 3 is not because no two residues of 7 can multiply to give 3, and you have an easy finite set as the residues of 7, are just 1, 2, 3, 4, 5, and 6, while 0 is not typically considered a residue. Think of it as there being nothing left with 0, so no residue.
Now the equations I've given count the number of factorizations for nT to give the count of a's that will work to give you a k, where you get either the total number of combinations or twice that number, and of that count 75% of them will give you a factorization of nT, while that may be a trivial factorization.
A trivial factorization is like 15 = 15(1). While the non-trivial factorization is 15 = 3(5).
Of the count of a's you will have either one or two cases for EACH unique factorization.
Those equations solve the factoring problem by giving you multiple ways to factor a given target T, where you can, for instance, let n=1, and then use a lot of small primes p_1, p_2, p_2,..., p_j and something called the Chinese Remainder theorem to solve for the factors, where the size of j is less than m where T/m! < 1.
Or you can change n, to give a lot of combinations of factors, and choose a prime p>sqrt(T).
Either of those approaches could be optimized to be very fast.
If this research is correct, it could mean that an RSA public key could be factored using algorithms based on these equations FASTER than it can be generated and implemented, regardless of its size.
The algebraic derivation of the relations is very, very, very easy, so there is no doubt about their correctness and no doubt about the value of the research. However, there is now serious doubt about the vitality of the mathematical discipline itself as mathematicians seem content for now to not let the world in on the massive discovery.
Though maybe the financial markets figured it out…
# posted by James Harris @ 23:09 
