Re: JSH: What is surrogate factoring? Once more.


"marcus_b" <marcus_bruckner@xxxxxxxxx> wrote in message
news:1188926026.332142.159830@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Sep 4, 11:12 am, riderofgiraffes <mathforum.org...@xxxxxxxxxxxxxx>
wrote:
I think you are overlooking what is maybe the
central unavoidable problem with the Harris idea.
As with Fermat's algorithm (and Dixon's, and the
quadratic sieve), he wants

X^2 = Y^2 mod T, i.e.,

(X + Y)*(X - Y) = 0 mod T.

So say T = 77. Let k = 1 and n = 2.

You can't do this. He assumes that k=2x (T)
*THAT'S* the central, unavoidable problem.

I think we may be saying the same thing or closely
related things. He cannot let k = 2X mod T until he
specifies X. What he does in fact is the following.
He FIRST chooses k and n, and lets S = 2k^2 + nT.
Then he factors S as S = F1 * F2, and AFTER THAT,
he chooses X and Y. In the process, he forgets that
he originally wanted X^2 = Y^2 mod T, and in general
the algorithm he specifies does not give him this
crucial equality. So as a rule he does not end up
with a difference of squares which equals a multiple
of T. This largely explains why his method, unlike
that of Dixon or the quadratic sieve method, fails
most of the time.

Marcus.



a product of a weak mind. JSH may talk big, but is weak intellectually, and
a troll.



.

Relevant Pages

  • Re: JSH: What is surrogate factoring? Once more.
    ... central unavoidable problem with the Harris idea. ... As with Fermat's algorithm (and Dixon's, ... that of Dixon or the quadratic sieve method, ...
    (sci.math)
  • Re: JSH: What is surrogate factoring? Once more.
    ... central unavoidable problem with the Harris idea. ... As with Fermat's algorithm (and Dixon's, ... quadratic sieve), he wants ...
    (sci.math)
  • uRe: implementing the quadratic sieve
    ... > I am trying to write a toy implementation of the quadratic sieve. ... requirement is really only required for optimizing the algorithm. ... of the exponents of the primes in the factor base. ... You should be able to figure out q from the factorization ...
    (comp.programming)
  • Re: new factoring algorithm
    ... > Quadratic Sieve Factoring we can show that it works faster than ... > Quadratic Sieve asymptotically .how can we check our algorithm to see ...
    (sci.crypt)
  • Re: new factoring algorithm
    ... > Quadratic Sieve Factoring we can show that it works faster than ... > Quadratic Sieve asymptotically .how can we check our algorithm to see ...
    (sci.crypt)