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]>>>

Choose x1,y1,x2,y2 such that x1*y1+x2*y2 = z = 47565467

>>> ProbABCD(z8[0])

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]