mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-06-07, 18:42   #1
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

1428 Posts
Default 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?
AntonVrba is offline   Reply With Quote
Old 2006-06-07, 18:44   #2
axn
 
axn's Avatar
 
Jun 2003

134B16 Posts
Default

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.
axn is offline   Reply With Quote
Old 2006-06-07, 19:09   #3
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

6216 Posts
Default

Quote:
Originally Posted by axn1
Probably.
What I forgot to say was that
GCD[a-b,Q]=Q and GCD[c+d,Q]=Q
AntonVrba is offline   Reply With Quote
Old 2006-06-07, 19:11   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2006-06-07, 19:26   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-06-07, 19:33   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-06-07, 19:34   #7
axn
 
axn's Avatar
 
Jun 2003

11×449 Posts
Default

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...
axn is offline   Reply With Quote
Old 2006-08-30, 07:15   #8
mgb
 
"Michael"
Aug 2006
Usually at home

2×41 Posts
Default

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).
mgb is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 factoring question siegert81 Math 3 2014-03-09 12:38
Factoring Question Rde Software 12 2009-06-12 22:38
Question about factoring 24737*2^991+1 VJS Factoring 56 2005-06-15 19:49
factoring question philmoore Factoring 8 2005-06-14 22:13
Trial factoring question 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.