Re: JSH: Factoring and residues


<jstevh@xxxxxxx> wrote in message
news:1153001392.658166.187490@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Tim Peters wrote:
[Proginoskes]
...
Maybe he pulls T out of his colon.

If some integer in his colon needs factoring, that would be fine ;-)

Stripped of "the proofs", the method works like this, given composite odd
T
to factor:

Pick some integer S coprime to T.

Why coprime? That's what he said, & not worth disputing.

Pick some integer x_res in [1, T) coprime to T.

Compute:
i = (2 * x_res)^-1 modulo T
k = mod(S*i, T)

Note that i isn't used again. Note that the requirements
that T be odd, and that x_res be coprime to T, are used to
guarantee that the modular inverse of 2 * x_res exists.

Pick some factorization of S + k^2 as the product of two integers:

S + k^2 = f_1 * f_2

It's unclear whether a search over all possible such factorizations
is intended, but it doesn't matter (it's easy to find cases
where no non-trivial factor of T is found no matter which way you
pick -- take T = p*q for virtually any "not small" primes p and q).

If f_1 and f_2 don't have the same parity, go back and try other choices
for
something.

At this point we want to find integer y such that y^2 + S + k^2 is a
perfect
square. Formally set:

z^2 - y^2 = (z+y)*(z-y) = S + k^2 = f_1 * f_2

and solve this system of equations for y and z:

z + y = f_1
z - y = f_2

This yields (note that because f_1 and f_2 have the same parity, these
yield
integers):

z = (f_1 + f_2)/2
y = (f_1 - f_2)/2

Compute:
x = z-k

At this point these things are always true:

x, y, and z are integers
y^2 + S + k^2 is a perfect square
z = sqrt(y^2 + S + k^2)
x^2 - y^2 = S - 2*x*k
2*S*k = x_res modulo T

And these things are generally false, although James wishes they were
true:

x = x_res modulo T
x^2 = y^2 modulo T
1 < gcd(x+y, T) < T
1 < gcd(x-y, T) < T


The correct mathematical view is that given S and k, you have an
infinite range of possible x_res's and T's that will satisfy

S = 2x_res*k mod T

and

x^2 - y^2 = 0 mod T

so you can find an S and k that will work with a particular x_res you
choose, your desired residue for x, but there are an infinity of other
x_res's and T's possible for which S and k will also work.

It's as simple as that and there is no reason for anyone to act like
there's a big mathematical mystery here.

That opens the real question of how often when you find S and k for
your x_res, will you get some other answer coming in, instead as the
math shifts to some T other than the one you want, and the good news is
that other T's will tend to be integers of absolute value bigger than
yours, which means there are probably strategies for limiting that
happening.

Now the mathematics here is simple and I think neat, but the politics
are high, so rather than admit that future development is possible, or
even bother giving mathematical reasons for how certain things can
happen Tim Peters is just pushing the position that it can't work well.

Well, maybe, maybe not, but why one way or the other?

That's why I hate how political this damn field has become as you run
into operatives like Peters who are fighting a war--what I call the
math wars--and the mathematics is just a pawn in a game about
convincing people one way or another.


James Harris


There's nothing political about our field; you're just delusional and highly
uneducable. Mathematics highly depends on being able to apply knowledge. If
I read a proof, I use my background to understand the proof. Why haven't you
taken the time to LEARN SOME MATH? I hate to break it to you, but you're not
the genius you seem to think you are. I have a degree in math, yet I don't
claim to be a genius in math. There are still things that I, personally,
don't know, even in my area of specialization.

Dave


.

Relevant Pages

  • Re: JSH: Factoring and residues
    ... I was wrong in thinking that picking x_res and getting k with a chosen ... It's math. ... gcds than the random-gcd factoring method was expected to take. ... using the tools of mathematics. ...
    (sci.math)
  • Re: JSH: Factoring and residues
    ... If some integer in his colon needs factoring, ... Pick some integer S coprime to T. ... Now the mathematics here is simple and I think neat, ... happen Tim Peters is just pushing the position that it can't work well. ...
    (sci.math)
  • JSH: filtered, decompressed quotable version
    ... "...I'm a crackpot and I've been babbling about surrogate factoring ... But they lie about the math to protect themselves. ... It's not like the mathematics changes. ... The human species can rot and die ...
    (sci.crypt)
  • Re: JSH: So what do we do now?
    ... public keys in posts on this newsgroup, ... Are they applicable to factoring? ... Math people have changed the rules, ... one to demonstrate, but with fundamental mathematics, why wouldn't ...
    (sci.physics)
  • JSH: filtered, then compressed for fast read
    ... Because I'm trying to use factoring to bring attention to the full story, ... about the math to protect themselves. ... supposed accomplishment they have in mathematics over their entire careers. ... The human species can rot and die before any of those people ...
    (sci.crypt)