factorisation with help of 2*2 matrix

[bhelmes]

A peaceful day,

I am a little bit struggled:

If M is a 2*2 matrix of the form
(a, b)
(b, d)

Let M²=E mod f, then there should be a factorisation possible:

M²=
(a²-b², ab+bd)
(ab+bd, b²-d²)
= E


therefore (a+d)b=0, gcd (a+d, f) or gcd (b, f) should give a factor.

I calculated it for M47
M=
(37822, 2730)
(2730, 197)

M² = E mod f, but I did not get a factor.

Where is the logical error ?

[Dr Sardonicus]

Originally Posted by bhelmes

A peaceful day,

I am a little bit struggled:

If M is a 2*2 matrix of the form
(a, b)
(b, d)

Let M²=E mod f, then there should be a factorisation possible:

M²=
(a²-b², ab+bd)
(ab+bd, b²-d²)
= E


therefore (a+d)b=0, gcd (a+d, f) or gcd (b, f) should give a factor.

I calculated it for M47
M=
(37822, 2730)
(2730, 197)

M² = E mod f, but I did not get a factor.

Where is the logical error ?

I assume "E" means the 2x2 identity matrix matid(2) and M47 means 2^47 - 1.

Unfortunately, M^2 is not congruent to matid(2) modulo 2^47 - 1.

? M=[37822,2730;2730,197];T=M^2
%1 =
[1437956584 103791870]

[103791870 7491709]

Now all entries of M^2 are positive, and the largest entry is < 2^31, so M^2 cannot possibly be congruent to the 2x2 identity modulo 2^47 - 1.

Exercise: Find the largest integer m such that M^2 is congruent to matid(2) modulo m.