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

Probability measure of difficulty of factoring by formula.

Expand Messages
  • Kermit Rose
    Hello. I made use of algebraic identity from matrix algebra to construct a factoring algorithm. The algebraic identity ensured that from 4 random integer
    Message 1 of 1 , Oct 14, 2009
    • 0 Attachment
      Hello.

      I made use of algebraic identity from matrix algebra to
      construct a factoring algorithm.


      The algebraic identity ensured that from 4 random integer values,
      and 4 integers x1,y1,x2,y2 such that

      x1*y1 + x2*y2 = z, the integer to be factored,

      I can calculate x3, y3 such that it is certain that
      x3 * y3 = 0 mod z.

      However, this fails to factor z because almost all the time,

      one of y3 or x3 is in fact equal to zero mod z.


      >>> ProbABCD(1000009)
      Choose x1,y1,x2,y2 such that x1*y1+x2*y2 = z = 1000009
      x1 = 1024 y1 = 976 x2 = 65 y2 = 9
      For 10000 times,
      Choose at random four positive integers, a1,a2,b1,b2.
      If b1 is invertible, mod z,
      Calculate d2 = ((y2 - a1 * b2) /b1)%z.
      If b2 is invertible, mod z,
      Calculate c2 = ((a2 * d2 - x1) /b2)%z.
      Calculate y3 = (a1*a2 + b1*c2)%z.
      If y3 is invertible mod z,
      Calculate d1 = (( b1 * x2 + a2 * y1) /y3 )%z
      Calculate c1 = (( a1 * d1 - y1) /b1 )%z
      Calculate x3 = (d2 * d1 + b2 * c1)%z
      Out of 10000 choices of random a1,a2,b1,b2,
      b1 = 0 mod z 0 times.
      b1 had no factors in common with z 9971 times.
      b1 had a non-zero factor in common with z 30 times.

      b2 = 0 mod z 0 times.
      b2 had no factors in common with z 9940 times.
      b2 had a non-zero factor in common with z 31 times.

      y3 * x3 is ensured by algebraic identity to be multiple of z.

      y3 = 0 mod z 0 times.
      y3 had no factors in common with z 9897 times.
      y3 had a non-zero factor in common with z 43 times.

      x3 = 0 mod z 9897 times.
      x3 had no factors in common with z 0 times.
      x3 had a non-zero factor in common with z 0 times.
      [0, 9971, 30, 0, 9940, 31, 0, 9897, 43, 9897, 0, 0]
      >>>

      >>> ProbABCD(z8[0])
      Choose x1,y1,x2,y2 such that x1*y1+x2*y2 = z = 47565467
      x1 = 8192 y1 = 5798 x2 = 521 y2 = 131
      For 10000 times,
      Choose at random four positive integers, a1,a2,b1,b2.
      If b1 is invertible, mod z,
      Calculate d2 = ((y2 - a1 * b2) /b1)%z.
      If b2 is invertible, mod z,
      Calculate c2 = ((a2 * d2 - x1) /b2)%z.
      Calculate y3 = (a1*a2 + b1*c2)%z.
      If y3 is invertible mod z,
      Calculate d1 = (( b1 * x2 + a2 * y1) /y3 )%z
      Calculate c1 = (( a1 * d1 - y1) /b1 )%z
      Calculate x3 = (d2 * d1 + b2 * c1)%z
      Out of 10000 choices of random a1,a2,b1,b2,
      b1 = 0 mod z 0 times.
      b1 had no factors in common with z 10000 times.
      b1 had a non-zero factor in common with z 1 times.

      b2 = 0 mod z 0 times.
      b2 had no factors in common with z 10000 times.
      b2 had a non-zero factor in common with z 0 times.

      y3 * x3 is ensured by algebraic identity to be multiple of z.

      y3 = 0 mod z 0 times.
      y3 had no factors in common with z 9997 times.
      y3 had a non-zero factor in common with z 3 times.

      x3 = 0 mod z 9997 times.
      x3 had no factors in common with z 0 times.
      x3 had a non-zero factor in common with z 0 times.
      [0, 10000, 1, 0, 10000, 0, 0, 9997, 3, 9997, 0, 0]
    Your message has been successfully submitted and would be delivered to recipients shortly.