Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Status of factorization

Expand Messages
  • Jud McCranie
    At 10:46 PM 10/4/2003, Décio Luiz Gazzoni Filho wrote: I m not trying to downplay the contributions of these methods -- far from it, ... Yes, it wasn t too
    Message 1 of 11 , Oct 4, 2003
      At 10:46 PM 10/4/2003, Décio Luiz Gazzoni Filho wrote:
      I'm not trying to downplay the contributions of these methods -- far from it,
      >and experimental evidence shows that these heuristics are on track, but it
      >appears to me that researchers were treading on far more solid ground when it
      >came to primality tests.

      Yes, it wasn't too much of a surprise for there to be good algorithms for
      testing primality, since Fermat's theorem and pseudoprimality tests got close.
    • Paul Leyland
      ... Good point. There are at least two proven L(1/2) algorithms: Dixon s algorithm for general numbers as you note and Lenstra s hyperelliptic curve algorithm
      Message 2 of 11 , Oct 5, 2003
        > Isn't it a hinderance that most of these results you
        > mentioned are merely
        > conjectured, as opposed to proved? Yes, the heuristics are
        > well accepted, but
        > that brings them no closer to theorem-status. As far as I
        > know, only the
        > random squares method was shown to be L(1/2)-time, and ECM's
        > running time is
        > very close to being proved.

        Good point.

        There are at least two proven L(1/2) algorithms: Dixon's algorithm for general numbers as you note and Lenstra's hyperelliptic curve algorithm for finding small factors. The L(1/3) algorithms are only heuristic, though no-one doubts the heuristics are good, not least because of the support from a goodly number of experimental results.


        Paul
      • Nathan Russell
        --On Sunday, October 05, 2003 3:08 AM -0700 Paul Leyland ... Is that the reason for your recent personal experience, where you have had to check several
        Message 3 of 11 , Oct 5, 2003
          --On Sunday, October 05, 2003 3:08 AM -0700 Paul Leyland
          <pleyland@...> wrote:

          > Good point.
          >
          > There are at least two proven L(1/2) algorithms: Dixon's
          > algorithm for general numbers as you note and Lenstra's
          > hyperelliptic curve algorithm for finding small factors. The
          > L(1/3) algorithms are only heuristic, though no-one doubts the
          > heuristics are good, not least because of the support from a
          > goodly number of experimental results.

          Is that the reason for your recent personal experience, where
          you have had to check several dependencies before one gives a
          non-trivial factorization?

          Nathan
        • Décio Luiz Gazzoni Filho
          ... Hash: SHA1 ... That s got nothing to do with it. Any congruent squares method, when applied to a number with 2 factors, has a 50% chance of returning the
          Message 4 of 11 , Oct 5, 2003
            -----BEGIN PGP SIGNED MESSAGE-----
            Hash: SHA1

            > Is that the reason for your recent personal experience, where
            > you have had to check several dependencies before one gives a
            > non-trivial factorization?

            That's got nothing to do with it. Any congruent squares method, when applied
            to a number with 2 factors, has a 50% chance of returning the trivial
            factorization and 50% chance of returning a non-trivial factorization. Long
            runs of non-trivial factorizations are possible, much as you could toss a
            coin and get straight runs of heads, though it's not very likely.

            Disclaimer: that's assuming that the squares were generated at random.
            However, there's no evidence at all that they stray from this random
            behavior, at least as far as this 50%-50% split of probabilities is
            concerned.

            Décio
            -----BEGIN PGP SIGNATURE-----
            Version: GnuPG v1.2.3 (GNU/Linux)

            iD8DBQE/gFoace3VljctsGsRAuxPAJ9NL4SWCXNuxSEX5Uz9470b8jn1AACgqsmc
            WhWZeV4pmQfNRYc79fzFDBg=
            =0UCu
            -----END PGP SIGNATURE-----
          • Paul Leyland
            ... No, that s an entirely different source of variability in run time. Each dependency is a relation of the form x^2 equiv y^2 mod N, so each has a 0.5
            Message 5 of 11 , Oct 6, 2003
              > Is that the reason for your recent personal experience, where
              > you have had to check several dependencies before one gives a
              > non-trivial factorization?


              No, that's an entirely different source of variability in run time. Each dependency is a relation of the form x^2 \equiv y^2 mod N, so each has a 0.5 probability of splitting N. Sometimes you get unlucky and have to use several dependencies. On average, though, you only need two.


              Paul
            • pakaran42
              ... time. Each dependency is a relation of the form x^2 equiv y^2 mod N, so each has a 0.5 probability of splitting N. Sometimes you get unlucky and have
              Message 6 of 11 , Oct 7, 2003
                --- In primenumbers@yahoogroups.com, "Paul Leyland" <pleyland@m...>
                wrote:
                >
                > > Is that the reason for your recent personal experience, where
                > > you have had to check several dependencies before one gives a
                > > non-trivial factorization?
                >
                >
                > No, that's an entirely different source of variability in run
                time. Each dependency is a relation of the form x^2 \equiv y^2 mod
                N, so each has a 0.5 probability of splitting N. Sometimes you get
                unlucky and have to use several dependencies. On average, though,
                you only need two.

                I see. So "running out" of dependencies is not the reason for the
                worst-case time required by NFS?
              • Décio Luiz Gazzoni Filho
                ... No. If not for anything else, getting an epsilon of extra dependencies costs nothing. If you re processing a 4,000,010 by 4,000,000 matrix, it doesn t cost
                Message 7 of 11 , Oct 7, 2003
                  > I see. So "running out" of dependencies is not the reason for the
                  > worst-case time required by NFS?

                  No. If not for anything else, getting an epsilon of extra dependencies costs
                  nothing. If you're processing a 4,000,010 by 4,000,000 matrix, it doesn't
                  cost much more to process a 4,000,100 by 4,000,000 matrix -- but the
                  probability of finding a solutions increases exponentially with each
                  dependency. (That's not how it works in practice, just trying to argue from a
                  complexity standpoint.)

                  The real bottleneck of NFS is the rate at which one can produce relations
                  (which in turn depends on the yield of the polynomials, which in turn are
                  mostly related to the size of the number being factored, whether it has
                  special form, and how much computational power has been thrown at its
                  selection). Also, since the sieving step is usually done in a
                  massively-parallel fashion, whereas LA is performed in a vector computer or
                  cluster, LA ends up being a bottleneck too, which can be reduced by two
                  means: better filtering strategies (involving more complex algorithms and
                  requiring many extra relations before creating the matrix), which may improve
                  the matrix's sparseness and possibly chop off some columns from it, and of
                  course a smaller matrix to boot -- but that means a smaller factor base,
                  which places a higher burden on the sieving stage. Of course there's an
                  optimal factor base size which balances sieving and LA work, and any shifts
                  away from this optimal point will increase computational requirements
                  subexponentially (read: faster than polynomially). Then there's other
                  improvements, like large prime variations, which facilitiate sieving while
                  requiring more complex filtering strategies and more computational resources
                  for filtering, while increasing the matrix density in the process. So there's
                  a very delicate balance to be reached by the NFS practitioner.

                  Décio
                • Décio Luiz Gazzoni Filho
                  ... Hash: SHA1 Sorry, sent past message without signature... Décio - ---- ... No. If not for anything else, getting an epsilon of extra dependencies costs
                  Message 8 of 11 , Oct 7, 2003
                    -----BEGIN PGP SIGNED MESSAGE-----
                    Hash: SHA1

                    Sorry, sent past message without signature...

                    Décio

                    - ----

                    > I see. So "running out" of dependencies is not the reason for the
                    > worst-case time required by NFS?

                    No. If not for anything else, getting an epsilon of extra dependencies costs
                    nothing. If you're processing a 4,000,010 by 4,000,000 matrix, it doesn't
                    cost much more to process a 4,000,100 by 4,000,000 matrix -- but the
                    probability of finding a solutions increases exponentially with each
                    dependency. (That's not how it works in practice, just trying to argue from a
                    complexity standpoint.)

                    The real bottleneck of NFS is the rate at which one can produce relations
                    (which in turn depends on the yield of the polynomials, which in turn are
                    mostly related to the size of the number being factored, whether it has
                    special form, and how much computational power has been thrown at its
                    selection). Also, since the sieving step is usually done in a
                    massively-parallel fashion, whereas LA is performed in a vector computer or
                    cluster, LA ends up being a bottleneck too, which can be reduced by two
                    means: better filtering strategies (involving more complex algorithms and
                    requiring many extra relations before creating the matrix), which may improve
                    the matrix's sparseness and possibly chop off some columns from it, and of
                    course a smaller matrix to boot -- but that means a smaller factor base,
                    which places a higher burden on the sieving stage. Of course there's an
                    optimal factor base size which balances sieving and LA work, and any shifts
                    away from this optimal point will increase computational requirements
                    subexponentially (read: faster than polynomially). Then there's other
                    improvements, like large prime variations, which facilitiate sieving while
                    requiring more complex filtering strategies and more computational resources
                    for filtering, while increasing the matrix density in the process. So there's
                    a very delicate balance to be reached by the NFS practitioner.

                    Décio
                    -----BEGIN PGP SIGNATURE-----
                    Version: GnuPG v1.2.3 (GNU/Linux)

                    iD8DBQE/gtcWce3VljctsGsRAnqyAJ9F42j2G9eDqbr8jFZ1EbtCf8BsdQCfarim
                    E2mTXz9aihmeak3IKBuelsA=
                    =W4uV
                    -----END PGP SIGNATURE-----
                  Your message has been successfully submitted and would be delivered to recipients shortly.