Re: Simple answer, surrogate factoring
jstevh_at_msn.com
Date: 03/05/05
- Next message: Peter Webb: "Re: Please help with Excel formula problem!"
- Previous message: David C. Ullrich: "Re: Sobolev spaces on periodic domains"
- In reply to: jstevh_at_msn.com: "Simple answer, surrogate factoring"
- Next in thread: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: C. Bond: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Date: 5 Mar 2005 04:50:37 -0800
jstevh@msn.com wrote:
> The main issue for me in showing that surrogate factoring is
practical
> is in finding a perfect algorithm which will factor a target M for
any
> non-zero j coprime to M.
Well I was VERY confident that I had the answer which turned out to be
wrong, but in talking it out, I figured out something.
I'll follow along with my previous for a while.
> I think the answer is a simple one.
Oh, um, yes it is, and I'll get to that while in my earlier post I was
still reaching.
> Starting as usual with
>
> yx^2 + Ax - M^2 = 0
>
> and
>
> yz^2 + Az - j^2 = 0
>
> where M is the target to be factored, j is some non-zero natural
> usually chosen to be less than M, and
>
> T = M^2 - j^2.
>
> Then
>
> y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2
>
> and you can substitute out y to get
>
> x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)
>
> and
>
> z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)
However, the first equation shows that if Az has M as a factor, then x
must have M as a factor, which screws up what I thought was a proof.
A poster last name Peters tried my idea and noticed it didn't work, so
I figured he was wrong, and endeavored to show that by doing a back
calculation.
What I found was a result where Ax was coprime to M, when x has a
single prime factor of M.
I also proved that such a result must occur.
So, I need to solve for x.
It's easy.
I have a set of integer Ax's from
z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)
and for each of those I get z as a ratio of x, so let
r = (-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)
so z = xr, and now importantly I can use
y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2
to solve out y, and simplifying a bit, I have
(M^2 - Ax)z^2 = (j^2 - Az) x^2
and I can solve for A, so multiplying out
M^2 z^2 - j^2 x^2 = A(xz^2 - x^2 z),
so
A = (M^2 z^2 - j^2 x^2)/xz(z-x)
and multiplying both sides by x, I have
A = (M^2 z^2 - j^2 x^2)/xz(z-x)
and using z = rx, I have
A = (M^2 r^2 - j^2 )/xr(r-1)
which doesn't help me much, so instead solve for x, so
x = (M^2 r^2 - j^2 )/Ar(r-1)
and now I can substitute out x in
yx^2 + Ax - M^2 = 0, and get
y(M^2 r^2 - j^2)^2/A^2 r^2 (r-1)^2 + (M^2 r^2 - j^2)/r(r-1) - M^2 = 0
so
y(M^2 r^2 - j^2)^2 + A^2 (M^2 r^2 - j^2)r(r-1) - M^2 A^2 r^2 (r-1)^2 =
0
but there are two solutions for x and z for any given y and A, as I
have quadratics, so,
x = (-A +/- sqrt(A^2 - 4M^2y))/2y
gives two solutons, so two values for Ax, and I can get two values from
z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)
as
Ax = +/-(f_1 - f_2) + 2j^2, where f_1 f_2 = Tj^2,
so I properly have r and r', giving me two equations:
y(M^2 r^2 - j^2)^2 + A^2 (M^2 r^2 - j^2)r(r-1) - M^2 A^2 r^2 (r-1)^2 =
0
and
y(M^2 r'^2 - j^2)^2 + A^2 (M^2 r'^2 - j^2)r'(r'-1) - M^2 A^2 r'^2
(r'-1)^2 = 0
and I can now solve as linear equations for y or A^2.
Notice that y and A being the same for two solutions is what's
important, and necessarily now you should be able to solve for either
and get a factorization of M, guaranteed, unless I screwed something
else up.
James Harris
- Next message: Peter Webb: "Re: Please help with Excel formula problem!"
- Previous message: David C. Ullrich: "Re: Sobolev spaces on periodic domains"
- In reply to: jstevh_at_msn.com: "Simple answer, surrogate factoring"
- Next in thread: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: C. Bond: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
