Sorry, an error occurred while loading the content.

## Clarification and example

Expand Messages
• In case I haven t expressed my prior question clearly, here is a very simple example of what I mean by the multiplication of two binary polynomials. In the
Message 1 of 2 , Jan 27, 2006
In case I haven't expressed my prior question clearly, here is a very
simple example of what I mean by the multiplication of two binary
polynomials. In the example below, the multiplication sign (*) means
boolean AND, and the plus sign (+) means boolean XOR.

Let:
a= a2*2^2 + a1*2^1 + a0*2^0
b= b2*2^2 + b1*2^1 + b0*2^0
r= r5*2^5 + r4*2^4 + r3*2^3 + r2*2^2 + r1*2^1 + r0*2^0

Then for: a*b = r

a0*b0 = r0
a1+b1 = r1
a2+a1*b1+b2+c1 = r2
a2*b1+a1*b2+c2 = r3
a2*b2+c3+c4 = r4
c5 = r5

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

The binary (boolean) equations above can be used to multiply any two
3-bit numbers (a2,a1,a0 and b2,b1,b0) together to yield a six bit
result (r5,r4,r3,r2,r1,r0): HOWEVER, if "a" and "b" are prime, then
the multiplication is "isomorphic" (if that's the correct
terminology), because if I'm given an "r" that is the product of two
primes, then I can uniquely determine "a" and "b" (ignoring the
ordering of "a" and "b") from the "r" by factoring "r". For example,
for r=15 (ie; r5=0, r4=0, r3=1, r2=1, r1=1, r0=1) I can determine the
solution to the above equations for "a" and "b" by brute force to be
a2=0,a1=1,a0=1 and b2=1,b1=0,b0=1.

What I would *LIKE* to be able to do is to invert the equations above
symbolically so that I have a system of equations for the a's and b's
in terms of the r's, ie;

a0 = f1(r5,r4,r3,r2,r1,r0)
a1 = f2(r5,r4,r3,r2,r1,r0)
a2 = f3(r5,r4,r3,r2,r1,r0)
b0 = f4(r5,r4,r3,r2,r1,r0)
b1 = f5(r5,r4,r3,r2,r1,r0)
b2 = f6(r5,r4,r3,r2,r1,r0)

I realize such equations would be the "holy grail" of factorization
and therefore do not exist in general for large numbers, but I'm
curious to know whether or not such equations can actually be proven
to exist at all - even if they may be extremely difficult or even
impossible to find for arbitrarily long numbers.

Might it be possible to find the first few terms by brute force?

-- Ron
Your message has been successfully submitted and would be delivered to recipients shortly.