 |
|
| Science Forum Index » Mathematics Forum » a way of factoring odd composite nonpowers.. how to... |
|
Page 1 of 1 |
|
| Author |
Message |
| Beta What... |
 Posted: Fri Oct 30, 2009 3:13 pm |
|
|
|
Guest
|
n is odd, composite and not a power of an integer. How to show that at
least half the integer pairs x,y in [0,n) with x^2 = y^2 (mod n)
necessarily have gcd(x-y,n) as a proper factor of n? |
|
|
| Back to top |
|
|
|
| Pubkeybreaker... |
| Posted: Fri Oct 30, 2009 4:39 pm |
|
|
|
Guest
|
On Oct 30, 8:13�pm, Beta What <lite.on.b... at (no spam) gmail.com> wrote:
[quote]n is odd, composite and not a power of an integer. How to show that at
least half the integer pairs x,y in [0,n) with x^2 = y^2 (mod n)
necessarily have gcd(x-y,n) as a proper factor of n?
[/quote]
Suppose that N = pq, p,q, prime.
Consider the congruence
x^2 = y^2 mod p
Ask: how many solutions does this have (the answer is easy)
Now consider
x1^2 = y1^2 mod q and ask the same question.
Now take the all pairs (x,y) and (x1, y1) and apply
the Chinese Remainder Theorem. How many of the
resulting solutions mod pq have x = y or x = -y?
How many do not?
Now suppose N = pqr etc. You will find that
if N has k factors, then the fraction of
pairs that yield a solution is (1-1/2^k). i.e.
it gets better as the number of factors increases. |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Mon Nov 02, 2009 12:22 am |
|
|
|
Guest
|
In article
<2ad43fe0-d2cf-4a92-8ca1-faed8e62412c at (no spam) 15g2000yqy.googlegroups.com>,
Beta What <lite.on.beta at (no spam) gmail.com> wrote:
[quote]n is odd, composite and not a power of an integer. How to show that at
least half the integer pairs x,y in [0,n) with x^2 = y^2 (mod n)
necessarily have gcd(x-y,n) as a proper factor of n?
[/quote]
Note that there are several factorization methods that depend
on this, e.g., Dixon's, SQUFOF, CFRAC, quadratic sieve.
--
Gerry Myerson (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 10:11 am
|
|