mersenneforum.org factorisation with help of 2*2 matrix
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-19, 19:05 #1 bhelmes     Mar 2016 25·13 Posts factorisation with help of 2*2 matrix 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 ?
2021-11-19, 20:47   #2
Dr Sardonicus

Feb 2017
Nowhere

24·3·127 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Combinatorics & Combinatorial Number Theory 9 2021-02-24 02:31 bhelmes Miscellaneous Math 31 2020-10-09 08:22 devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 fivemack Math 7 2007-11-17 01:27

All times are UTC. The time now is 16:48.

Thu Dec 1 16:48:03 UTC 2022 up 105 days, 14:16, 1 user, load averages: 0.90, 1.39, 1.31