- --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
> What is not yet known is what complexity class factoring

-----BEGIN PGP SIGNED MESSAGE-----

> belongs to.

Hash: SHA1

I see. Thank you Paul, as well as Décio for saving me countless

hours of unnecessarily wasted effort. As I understand it then, the

real problem in this particular case would be to "reverse" the

equations I mentioned so that the a's and b's are solved for in

terms of the bits of the composite number to be factored rather

than the way I show them? In other words, what I need (for

example) is to convert equations like these:

n1 = a1 ^ 1

n2 = a1 ^ b1

(Where n1 and n2 are binary bits of the composite number to be

factored)

Into something like this:

a1 = n1 ^ 1

b1 = n1 ^ n2 ^ 1

I realize this is probably impossible in general, but if it *were*

possible it would show that factoring is in P, right?

Thanks,

Ron

-----BEGIN PGP SIGNATURE-----

Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQL1FbhpqFjUCnHWBEQJV7ACg4+muUEwxKT/Mwx60WWW2w81Md1IAoO4S

cL/ybm7yzzuaSm/X6gHDco6P

=+2jM

-----END PGP SIGNATURE----- - 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