20060607, 18:42  #1 
Jun 2005
142_{8} Posts 
Factoring Question
Assume that a,b,c,d are known such that
a^2b^2=0 (mod Q) and c^2d^2=0 (mod Q) Is there enough information to factorise Q? 
20060607, 18:44  #2  
Jun 2003
134B_{16} Posts 
Quote:


20060607, 19:09  #3  
Jun 2005
62_{16} Posts 
Quote:
GCD[ab,Q]=Q and GCD[c+d,Q]=Q 

20060607, 19:11  #4  
Aug 2002
Buenos Aires, Argentina
2^{2}·337 Posts 
Quote:
In the other hand, if a is not congruent to b or its negative, we can find a proper factor of Q by computing gcd(ab,Q). Quote:
Last fiddled with by alpertron on 20060607 at 19:16 

20060607, 19:26  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
I will leave it as an elementary exercize. 

20060607, 19:33  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
You get a trivial factorisation from x^2 ≡ y^2 (mod N) iff x ≡ ±y (mod N). If a,b,c,d are pairwise not congruent, it should work, as at least one of a,b and c,d will not be negatives of each other.
Alex Edit: Oops  missed Anton's second posting. Last fiddled with by akruppa on 20060607 at 21:00 
20060607, 19:34  #7 
Jun 2003
11×449 Posts 
gcd(a+/b,Q) = Q implies a^2b^2 = 0 (mod Q)
IOW, the condition in your second post means that there is absolutely no new information to be gained from the conditions in your first post. You might still be very lucky and get a nontrivial factorisation [say gcd(a+b,Q) or gcd(cd,Q)]. But... 
20060830, 07:15  #8 
"Michael"
Aug 2006
Usually at home
2×41 Posts 
If both pairs of squares are simply multimles of Q you will not get the factors.
You could look at (a^2 c^2) = (b^2d^2) (mod Q). 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring question  siegert81  Math  3  20140309 12:38 
Factoring Question  Rde  Software  12  20090612 22:38 
Question about factoring 24737*2^991+1  VJS  Factoring  56  20050615 19:49 
factoring question  philmoore  Factoring  8  20050614 22:13 
Trial factoring question  ThomRuley  Math  1  20040226 21:43 