Factoring numbers with boolean algebra: public domain source code

Hi,
I recently finished a program that factors the product of two unequal
prime numbers using boolean algebra.

You can find the source here: http://vm64dec.googlecode.com/files/unmultiply.cpp

It is currently demonstrated factoring a 24-bit number with these
properties:
1. The product (call it C) is known and is 24 bits
2. Each prime number fits in 12 bits (call them A and B)
3. The prime numbers are not equal.
In particular, the low x bits of A and B are equal but A[x] (bit x
of A) is 1 and B[x] is 0.
We have to know x in advance - presently it's hardwired to bit 7
but it can be changed.
It's possible to modify the program to brute force this bit, this
can be done with an extra for loop.
If W is the width of A and B (so that C has width 2W) then this
would require W trials. However, for large
W, each trial will take a long time.
4. If C = A * B then we can recover both A and B using boolean
algebra.

It really works! It factors the product of 3571 and 3187 (two small
primes that fit in 12 bits each).
It has good spatial complexity.
I tried it with the same prime numbers, but using a 32-bit word size
instead of 12 bit word size and it took too long (plus I'm impatient).

Does anyone out there care to factor other numbers or care to
speculate about how this approach compares to the current state-of-
the-
art for factoring? It CAN factor 4096-bit numbers, it would simply
take a LOONGGG time. As for how long, that depends on the complexity.
I think I have an exponential-time algorithm here, but I can't prove
it. I don't think it's faster than brute force, but it is possible to
speed this up with more intelligence, whereas brute force is so dumb
it can't be sped up.

Please see the source code at the above link for full details. It's
hereby released into the public domain.

Basically, here is how it works:
I express multiplication using ANDs and XORs (actually a generalized
logic gate of the form y = c0 ^ c1 x1 ^ c2 x2 ^ c12 x1 x2). Then I
create a system of nonlinear, discrete equations such that for the
correct (A,B) values plugged in, each equation evaluates to 1; if ANY
key bits we guess are wrong, then at least one of these equations will
evaluate to 0. In particular, I might try A[0] = 0. If this is wrong,
then an equation will not only evaluate to 0, but it will be an
identity for 0 leading to 0 = 1 and thus a logical contradiction.

Once a logical contradiction is detected, I know that, since there's
one unique solution (as A and B are different and we know one of their
bits for which A[x] = 1 but B[x] = 0; A[i] = B[i] for i < x), the
trial bit must be the opposite of what we tried.

In theory you can use the distributive property to tell whether or not
an expression that is a function of A and B bits is an identity for 0
(i.e. if we tried A[0] = 0 when in fact A[0] = 1), or if it isn't an
identity for 0. We can't say anything at all if it is NOT an identity
for zero.

Mathematically, each equation has a solution set. The intersection is
the empty set if any equations are 0 = 1 (identity). That tells us
there are no solutions, so we can choose A[0] = 1 if we tried A[0] =
0. Once we know A[0], we move on to deduce B[0]. It's easy and fast.

But when it comes time to deduce A[1], the distributive property has
bad spatial complexity. In principle, for instance, we might be faced
with a graph that expands to more nodes than fits in a 'double' (C
data type). After such a thing is expanded, if you cross off
duplicates, you will either have 0 or 1.

But I discovered some shortcuts to speed it up. You can plug in 0's
for all key bits (A or B) that remain unknown. You can then tell
whether the equation is odd or even (+1 in expanded/simplified form).

If it's odd, it can't be an identity for 0. If it's even, you have to
try e.g. a[1] = 1 and see if there's a logical contradiction or not,
then try a[1] = 0. If there's a logical contradiction for both of
these trials, then the system is inconsistent and has no solutions,
i.e. is in fact an identity for 0.

Is anyone interested in this? I can explain it more if you like....

Willow
P.S. Sorry to post this in several newsgroups, but sci.crypt.research
is apparently moderated.
.