mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-11-19, 19:05   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25·13 Posts
Default 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 ?
bhelmes is offline   Reply With Quote
Old 2021-11-19, 20:47   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24·3·127 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
is the factorisation of Mp-1 an advantage ? bhelmes Combinatorics & Combinatorial Number Theory 9 2021-02-24 02:31
factorisation for p-1, p is prime bhelmes Miscellaneous Math 31 2020-10-09 08:22
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Being coy about a factorisation 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔