## Probability measure of difficulty of factoring by formula.

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