Re: Quadratic residues and factoring

jstevh@msn.com wrote:
> Wouldn't you know I go to factoring, yet again, as, for one thing, just
> about all of my research relates to factoring one way or another, and
> for another, I think that the factoring problem has a big enough
> economic importance that I focus on it as a way to break the impasse.

<deleted>

>
> So what is this thing?
>
> The result is that given odd naturals summed to get a composite:

It has been pointed out to me that they need only be naturals.

>
> n_1 + n_2 = C
>
> it must be true that, if k is an odd difference of factors of 2*C that
>

It also turns out that k just needs to be the difference of factors of
2*C and not necessarily odd.

> 8n_2 + k^2 must be a quadratic residue of p, where p is a prime factor
> of n_1, or
>
> (8n_2 + k^2) mod p, where p is a prime factor of n_1,
>
> must be quadratic residue of n_1, or to state it the way I've been told
> is correct terminology,
>
> 8n_2 + k^2 must be a square modulo p, where p is a prime factor of n_1,
> or
>
> (8n_2 + k^2) mod p must be a square modulo p.
>
> So how can that be used to factor?
>
> Well, if n_1 is a composite with two primes as factors, then maybe you
> can find their individual quadratic residues.
>
> For example, using n_1 = 55, I will let n_2 = 17, so I have 2*C = 144,
> and picking the factorization 16(9), I have k = 7.
>
> Then
>
> 8*17 + 49 = 185
>
> and 185 mod 55 = 20.
>
> And 20 is 0 mod 5 and 9 mod 11, so they are squares, but if you didn't
> know that, what would you know?

The 0 case comes up so much with 5 as it only has 0, 1 and 4 as
squares.

It might be a good idea figuring out how things work to use larger
composites.

Trying out an odd k, I'll use the factorization 4(36), which gives
k=32.

Then

8*17 + 32^2 = 1160, and 1160 mod 55 = 5

and the 0 mod 5 case keeps coming up, as I keep trying to find ones
where it doesn't and either k has 5 as a factor or C does. I should
have used bigger primes.

One thing, if you use a C such that 2*C is a square then, of course,
k=0, is a possible, meaning that 8*n_2 must be a square modulo p, or
8*n_2 mod p must be a square modulo p, where p is a prime factor of
n_1.

So with n_1 = p_1 p_2, where p_1 and p_2 are primes, yes, this will
definitely give you quadratic residues of those primes, but how close
can you get using mod n_1 as I did above?

Is there some clever result from the world of quadratic residues, which
will allow you to pull out the rest of the info, and identify the prime
factors?

James Harris
Received on Mon May 1 02:06:08 2006