From: Dann Corbit on 6 Nov 2009 19:03 [snip] > I will describe the theory here. Basically, we have 3 numbers: A, B, > C. We know C; in particular C = A * B and we want to recover A and B. > Now A and B each have w bits and are unsigned numbers; C has 2w bits. > Let 0 <= x < w be a number such that A[i] = B[i] for i < x and such > that A[x] = 1 but B[x] = 0. Since there are only w possible values for > x, we can brute force x. Does your idea work if C has 2W bits, A has 2W-K bits, and C has K bits? (The above description seems to assume that A and C have the same number of bits). [snip]
From: ttw6687 on 6 Nov 2009 19:05 Does this not reduce to trial division in binary? It looks like order Sqrt (N). (Or maybe not; I didn't look in detail.)
From: Willow on 6 Nov 2009 19:41 On Nov 6, 4:05 pm, "ttw6...(a)att.net" <ttw6...(a)att.net> wrote: > Does this not reduce to trial division in binary? It looks like order > Sqrt (N). (Or maybe not; I didn't look in detail.) Well it's different from trial division in binary. By improving the heuristic it is theoretically possible to improve performance beyond brute force. If N = 2^W then sqrt(N) = 2^(w-1) which is close to the observed complexity. So yes, it has order Sqrt(N) as you say -- in it's present implementation. Factoring the product of two 16-bit numbers, I counted 74,067 nodes that were encountered vs. 65536 nodes needed for brute force. Factoring the original product of two 12-bit numbers, I count 6,174 nodes vs. the 4096 needed for brute force. So, indeed, brute force will be faster. But thanks for asking, you're absolutely right, it is O(Sqrt(N)); however it's quite different in the approach from trial division. (I said in an early post that I believe it has exponential time complexity; I haven't proven it's impossible to do better, but I suspect it is. Exponential time complexity is no faster than brute force.) Willow
From: ttw6687 on 7 Nov 2009 09:52
If you do this in several bases at once, I think it is similar to Fermat's method. He was looking at differences of squares and their remainders in various bases. (It's in Knuth, volume 2 or 3, I think.) Of course, using anything other than base 2 means less hardware support. |