Loading ...
Sorry, an error occurred while loading the content.
 

Clarification and example

Expand Messages
  • Ron
    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.