Re: Simple answer, surrogate factoring

jstevh_at_msn.com
Date: 03/05/05 

Date: 4 Mar 2005 16:12:52 -0800

Tim Peters wrote:
> [...]

<deleted>

> >> was intended.
>
> [JSH]
> > Sorry, should be
> >
> > 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
>
> OK.

<deleted>

> Sorry, I can't make it work, no way, no how. Perhaps you could show
how it
> finds a factor of M=221 at j=2.
>
> M = 221 = 13 * 17
> j = 2
> T = M**2 - j**2 = 48837 = 3 * 73 * 223
> T*j**2 = T*4 = 195348 = 2**2 * 3 * 73 * 223

<deleted>

> Two of those are redundant, so it's down to:
>
> gcd((438-446)+8, 221) = 221
> gcd((48837-4)+8, 221) = 221
>

<deleted>

>
> "Dividing off factors of M" out of the denominator instead doesn't
work
> either here (still leaves gcds of 1 or 221 in the end).
>
> How do you get a factor of M=221 at j=2?

Hmmm...I prefer to work the other way.

You have

yx^2 + Ax - 221^2 = 0

yz^2 + Az - 4 = 0

so let x = 13^2, so

169y + A = 17^2, so

y = (289 - A)/169, and substituting into the solution for z, from the
second, gives

z = 169(-A +/- sqrt(A^2 + 4(289 - A)/169)))/2(289 - A)

which is

z = 13(-13A +/- sqrt(169A^2 + 4(289 - A))))/2(289 - A)

and concentrating on the square root gives

169A^2 - 4A + 4(289), and completing the square gives

169A^2 -4A + 4/169 + 4(289) - 4/169

so

(13A - 2/13)^2 + 195356/169

and simplifying then ignoring the denominator

sqrt((169A - 2)^2 + 195356)

and I need 169A to be an integer, so I need the factorization of
195356.

Damn, now I have to pull out my factoring program...

 ( 2^2 )( 7 )( 6977 )

and picking, um, f_1 = 7 and f_2 = 6977, I have

169A = 6977 - 7 + 2 = 6972

Let's do a sanity check. Plugging in 6972, gives

sqrt((6972 - 2)^2 + 195356) = sqrt(48776256) = 6984

so it works.

Factorization of 6972:

 ( 2^2 )( 3 )( 7 )( 83 )

so you screwed up somewhere as 169(6972) is an integer solution for Ax.

If you iterated through all possible integer solutions then that should
have popped out.

Now that's interesting as this is actually a case where the original
algorithm would work.

Check for 169(6972) as a solution to Ax and get back to the group.

James Harris

Relevant Pages

  • Re: Simple answer, surrogate factoring
    ... Tim Peters wrote: ... and I need 169A to be an integer, so I need the factorization of ... Plugging in 6972, gives ... so you screwed up somewhere as 169is an integer solution for Ax. ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... Tim Peters wrote: ... If not then you are running up against mathematical absolutes. ... it MUST be true that every integer solution for Ax is given by ... explanation. ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... Tim Peters wrote: ... If not then you are running up against mathematical absolutes. ... it MUST be true that every integer solution for Ax is given by ... explanation. ...
    (sci.crypt)
  • Re: Basically a sieve method, relation to quantum
    ... Tim Peters wrote: ... >> odd numbers until the square root). ... However, I didn't get 100% factorization which I assumed I would get, ...
    (sci.crypt)
  • Re: Surrogate factoring, surprising result
    ... Tim Peters wrote: ... >> prime factor with j then the factorization is blocked. ... so both are fractions, which explains why that particular solution ... the issue has to do with prime factors of r-1 where r-1 is a factor of ...
    (sci.crypt)