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