[math-fun] "Reverse factoring" complexity of addition
I used to wonder why no one ever stated explicitly just *how* a number is respresented when a factoring algorithm is applied to it, in terms of saying how fast the algorithm is. But it's pretty clear that the input could be in base 10, or 2, or what have you, and at least for a long range of bases -- a factoring algorithm's complexity would vary very little. ---------------------------------------------------------------------------------------------------- Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: K = (d_1, d_2, . . . , d_r) (= 2^d_1 * 3^d_2 * . . . * p_r^d_r) and L = (e_1, e_2, . . . , e_s) (likewise). Now: What's the fastest way to compute the prime factorization of K + L ? Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?) An obvious first step would be to exploit distributivity by factoring out G=gcd(K,L) and working with K' = K/G and L' = L/G. So WLOG assume (K,L) = 1. (And maybe assume further that K and L are squarefree.) --Dan
I have considered this problem at various times. I've never been able to come with anything better than taking out the GCD (as you describe) and then converting to an appropriate base (decimal for pencil and paper, binary for computer). If I want the result as a factorization, the last step is to factor the sum and merge with the GCD; otherwise, multiply out the GCD and multiply by the sum. Franklin T. Adams-Watters -----Original Message----- From: dasimov@earthlink.net To: math-fun <math-fun@mailman.xmission.com> Sent: Mon, 10 Apr 2006 19:22:32 -0400 (EDT) Subject: [math-fun] "Reverse factoring" complexity of addition I used to wonder why no one ever stated explicitly just *how* a number is respresented when a factoring algorithm is applied to it, in terms of saying how fast the algorithm is. But it's pretty clear that the input could be in base 10, or 2, or what have you, and at least for a long range of bases -- a factoring algorithm's complexity would vary very little. ---------------------------------------------------------------------------------------------------- Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: K = (d_1, d_2, . . . , d_r) (= 2^d_1 * 3^d_2 * . . . * p_r^d_r) and L = (e_1, e_2, . . . , e_s) (likewise). Now: What's the fastest way to compute the prime factorization of K + L ? Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?) An obvious first step would be to exploit distributivity by factoring out G=gcd(K,L) and working with K' = K/G and L' = L/G. So WLOG assume (K,L) = 1. (And maybe assume further that K and L are squarefree.) --Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
On Tuesday 11 April 2006 00:22, dasimov@earthlink.net wrote:
Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: ... Now: What's the fastest way to compute the prime factorization of K + L ?
Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?)
Suppose there is; then, given a Mysterious Large Number, we can try to factor it by finding two easily factored numbers whose sum it (or some multiple of it) is. For instance, we could try to write 2N as a sum of two primes. We famously don't know whether that's always possible, but naively and handwavily you can pick candidates at random and find one after about log N attempts. So, if you can find a way to factor K+L efficiently whenever the factorizations of K,L are known, then you have *either* an efficient way of factoring any number *or* a promising line of attack on Goldbach's conjecture. :-) If the restriction to K,L squarefree was intended as a concession rather than a limitation, then the fact that n=a^2+b^2+c^2+d^2 suffices. (Write n thus, for which I believe there are efficient algorithms; factor a,b,c,d; then factor successively a^2+b^2, a^2+b^2+c^2, n.) I suspect that someone more awake than me could find a more clear-cut demonstration that the thing can't be done, perhaps using a quantitative form of the various theorems that exist in the vicinity of Goldbach's conjecture. (For instance, it's well known that all large enough even numbers are p+q or p+qr; I think it's in fact known that they have many such representations, but I don't know how many. If there are enough, then we're probably done.) -- g
Trying to express MLN (Mysterious Large Number) as the sum of just two easily factorable numbers is making it harder on ourselves than necessary. Simply express MLN in some small base b (such as ten). Then MLN = d_0 + d_1*b + ... + d_k*b^k, and each of these terms is easily factorable. If we had a fast (polynomial) way to generate the factorization of the sum of two factorizations, then we would have a fast way to factor the sum of k+1 factorizations; and this would let us factor MLN. Franklin T. Adams-Watters -----Original Message----- From: Gareth McCaughan <gareth.mccaughan@pobox.com> On Tuesday 11 April 2006 00:22, dasimov@earthlink.net wrote:
Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: ... Now: What's the fastest way to compute the prime factorization of K + L ?
Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?)
Suppose there is; then, given a Mysterious Large Number, we can try to factor it by finding two easily factored numbers whose sum it (or some multiple of it) is. For instance, we could try to write 2N as a sum of two primes. We famously don't know whether that's always possible, but naively and handwavily you can pick candidates at random and find one after about log N attempts. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
(restating the obvious) Since factoring is so much harder than radix conversion, the choice of representation doesn't matter much. With one curious exception: If the representation of a number ends in 0, the radix is a divisor. A composite number PQ will have two special bases where the factorization is obvious. Unfortunately, finding these bases is just as hard as the original factoring problem. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of dasimov@earthlink.net Sent: Mon 4/10/2006 5:22 PM To: math-fun Subject: [math-fun] "Reverse factoring" complexity of addition I used to wonder why no one ever stated explicitly just *how* a number is respresented when a factoring algorithm is applied to it, in terms of saying how fast the algorithm is. But it's pretty clear that the input could be in base 10, or 2, or what have you, and at least for a long range of bases -- a factoring algorithm's complexity would vary very little. ---------------------------------------------------------------------------------------------------- Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: K = (d_1, d_2, . . . , d_r) (= 2^d_1 * 3^d_2 * . . . * p_r^d_r) and L = (e_1, e_2, . . . , e_s) (likewise). Now: What's the fastest way to compute the prime factorization of K + L ? Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?) An obvious first step would be to exploit distributivity by factoring out G=gcd(K,L) and working with K' = K/G and L' = L/G. So WLOG assume (K,L) = 1. (And maybe assume further that K and L are squarefree.) --Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
dasimov@earthlink.net -
franktaw@netscape.net -
Gareth McCaughan -
Schroeppel, Richard