SF: Quadratic residues

jstevh_at_msn.com
Date: 03/02/05 

Date: 1 Mar 2005 16:49:07 -0800

One fairly easy calculation that I went through a while back, shows
that quadratic residues play a major role in factoring efficiency with
surrogate factoring.

I don't talk about it as much lately as I'm finding results that don't
yet fit with those calculations as they indicated that for every
rational x found, there should be a 50% probability it will give the
factorization, which is way off from what algorithms are getting.

Still some of the behavior is in line with a role being played by
quadratic residues.

For instance, you can make it more likely that the algorithm will
factor by multiplying your target by some large prime--hopefully larger
than any of the target's factors--as the more prime factors you have,
the more likely you'll get a factorization.

The method is like ECM in that it tends to pull out the smallest prime
factors first, so you need to multiply by a larger prime than any of
those factors, and I call that prime a cracking prime, if it works.

The thing is that when you multiply by some other number you're
changing the quadratic residues of what's going into the algorithm, and
whether you get your target or a factor of the target is related to the
quadratic residues, so if from some reason they favor the target so
that you keep getting that back out of the algorithm versus a factor,
then you just multiply by some other number to shift them.

It seems to me that you should be able to multiply by just about
anything, like even small primes like 3 or 5, but it hasn't worked for
me so far, so I've been playing with large cracking primes.

But I'm half playing at it as I'm frustrated by an inability to just
find an algorithm that will just work without any fiddling like tossing
in extra factors to increase the chance of factoring.

Still, it's basic research so I guess I need to look at even
unsatisfying answers if I'm ever going to fully understand what's going
on.

I guess it's kind of odd that making a large number bigger by
multiplying it by some large prime could make it easier to factor, but
it's the new world of surrogate factoring.

James Harris

Relevant Pages

  • SF: Quadratic residues
    ... surrogate factoring. ... quadratic residues. ... you can make it more likely that the algorithm will ... factor by multiplying your target by some large prime--hopefully larger ...
    (sci.math)
  • Re: JSH: Understanding quadratic residues result
    ... on previous occasions you've complained that people have deliberately ... quadratic residues then the algorithm does work since after all the ... answer is plugged into the algorithm. ... As a means of factoring then it ...
    (sci.crypt)
  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
Quantcast