mersenneforum.org > Math Factoring Question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-06-07, 18:42 #1 AntonVrba     Jun 2005 1428 Posts Factoring Question Assume that a,b,c,d are known such that a^2-b^2=0 (mod Q) and c^2-d^2=0 (mod Q) Is there enough information to factorise Q?
2006-06-07, 18:44   #2
axn

Jun 2003

134B16 Posts

Quote:
 Originally Posted by AntonVrba Assume that a,b,c,d are known such that a^2-b^2=0 (mod Q) and c^2-d^2=0 (mod Q) Is there enough information to factorise Q?
Probably.

2006-06-07, 19:09   #3
AntonVrba

Jun 2005

6216 Posts

Quote:
 Originally Posted by axn1 Probably.
What I forgot to say was that
GCD[a-b,Q]=Q and GCD[c+d,Q]=Q

2006-06-07, 19:11   #4
alpertron

Aug 2002
Buenos Aires, Argentina

22·337 Posts

Quote:
 Originally Posted by AntonVrba Assume that a,b,c,d are known such that a^2-b^2=0 (mod Q) and c^2-d^2=0 (mod Q) Is there enough information to factorise Q?
It depends if there are other conditions. If no other conditions are added I can set a = b + mQ, c = d + nQ. From that we cannot find any factor of Q.

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(a-b,Q).

Quote:
 Originally Posted by AntonVrba What I forgot to say was that GCD[a-b,Q]=Q and GCD[c+d,Q]=Q
That's the first case I cited above (you can replace d by Q-d').

Last fiddled with by alpertron on 2006-06-07 at 19:16

2006-06-07, 19:26   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by alpertron It depends if there are other conditions. If no other conditions are added I can set a = b + mQ, c = d + nQ. From that we cannot find any factor of Q. 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(a-b,Q). That's the first case I cited above (you can replace d by Q-d').
You also need one other piece of information.

I will leave it as an elementary exercize.

 2006-06-07, 19:33 #6 akruppa     "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 2006-06-07 at 21:00
 2006-06-07, 19:34 #7 axn     Jun 2003 11×449 Posts gcd(a+/-b,Q) = Q implies a^2-b^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 non-trivial factorisation [say gcd(a+b,Q) or gcd(c-d,Q)]. But...
 2006-08-30, 07:15 #8 mgb   "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^2-d^2) (mod Q).

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 Math 3 2014-03-09 12:38 Rde Software 12 2009-06-12 22:38 VJS Factoring 56 2005-06-15 19:49 philmoore Factoring 8 2005-06-14 22:13 ThomRuley Math 1 2004-02-26 21:43

All times are UTC. The time now is 10:39.

Fri Apr 23 10:39:34 UTC 2021 up 15 days, 5:20, 0 users, load averages: 0.99, 1.54, 1.62