- On Mon, 2004-05-31 at 12:49, Ron wrote:

> Ha - that would be really neat Décio, if I had actually

Unfortunately, people have been trying this approach, unsuccessfully so

> discovered a new or novel method of doing something, but

> considering my lack of background in math, the technique is

> probably as old as the hills and I just don't know the correct

> name for it.

far, for quite a few years. If you make progress, it will be *very*

interesting!

> I guess what I've done is to transform the factoring problem into

You've shown that factoring is no harder than SAT, something that is

> a boolean satisfiability problem (SAT), but I thought factoring

> was already known (or at least widely believed to be) a very

> difficult problem - I guess "NP-Hard" is the way to describe it(?)

> Since it should be trivial to transform the SAT equations (if

> that's what they are) back into the product of two binary

> polynomials, I would assume the transformation of these particular

> equations is "isomorphic," if I understand the meaning of that

> term correctly.

moderately well-known.

Factoring is clearly in NP. If you guess the factors of an integer, a

polynomial time algorithm (multiplication takes (log n)^2 or better)

will verify the guess. SAT is also in NP.

What is not yet known is what complexity class factoring belongs to.

It's possible it may be NP-complete or NP-hard. It's possible that it's

in P. Until very recently primality testing wasn't known to be in P.

Paul - Hi Ron,

R> Justin asked me for a real life example of how this technique

R> can be used to find factors, so at the risk of boring everyone

R> else, I thought I'd post it here on the forum. Here is a sample

R> Maple code snippet ('#' begins a comment) that illustrates the

R> problem:

Thanks Ron. I think I've finally understood the idea of the technique. I

also understand long-hand multiplication at long last ;)

R> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

R> eqn := {a1+b1 = 1,

R> a2+a1*b1+b2+c1 = 1,

R> a2*b1+a1*b2+c2 = 1,

R> a2*b2+c3+c4 = 0,

R> c5 = 0};

As you know, these equations in the Z(2) field are equivalent to boolean

expressions. So they can be transformed the following way to eliminate the

equality:

lhs == 1 -> lhs

lhs == 0 -> NOT(lhs) -> lhs+1 (equivalent to NOT using only xor)

now all the ex-equations can be combined to one with AND (ie multiplication

in Z(2)) to form one expression:

(a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

This can be reduced algebraically and transformed to boolean:

(a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

Which in effect is indeed your solution:

R> # But the solution is:

R> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal

R> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

R> # Where a=3 and b=5 are the factors of 15.

I use Mathematica, and am not familiar with Maple, but I suppose it is

just as capable of these transformations.

I'm not sure about the practicability though. It already took a few seconds

to reduce your example expressions (albeit with somewhat straightforward

and probably not really efficient reduction algorithm).

But then, what do I know? ;P

--

Justin

ICQ 37456745

AIM jasticle