Prev: JSH: This factoring thing is scary
Next: License Codes Algorithms
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.
First  |  Prev  | 
Pages: 1 2
Prev: JSH: This factoring thing is scary
Next: License Codes Algorithms