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

2·33·107 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.  Thread Tools Show Printable Version Email this Page 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 13:30.

Mon May 23 13:30:41 UTC 2022 up 39 days, 11:32, 2 users, load averages: 1.94, 1.62, 1.52