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

how can one factor big integers?

Expand Messages
  • Sudarshan Iyengar
    Hi, I have been wondering how exactly pari(http://pari.math.u- bordeaux.fr/) factors big integers(which are of 60 digit or more in length). I do know
    Message 1 of 2 , Nov 1, 2004
    • 0 Attachment
      Hi,

      I have been wondering how exactly pari(http://pari.math.u-
      bordeaux.fr/) factors big integers(which are of 60 digit or more in
      length).

      I do know elementary number theory, my knowledge of number theoretic
      algorithms is very limited. In the sense that i have tried to
      understand the RSA-encryption and theorems concerning the same. With
      this level of knowledge will i be able to understand the factoring
      and primality checking algorithms?

      I have tried primepages.org, the difficulty i face is that the
      content is so less-crisp that i need to read between the lines a lot,
      I don't mind fighting with the concept except that I feel discouraged
      in the long run when i fail to sort things out.

      I would be happy if any samaritan here can help me out by suggesting
      me a gud reference material to start with. Also, i would be glad if
      the moderator can let me know whether i can post any difficulties
      that i face while studying the primepages.org content? Hope it will
      not be considered spam. :-)

      Thanking you all,
      S. R. Sudarshan Iyengar
      Bangalore
      India
    • jbrennen
      ... For PARI/GP, you can expose a lot of the internal factorization process very easily. Turn on debug level 5, with the command g 5 and then try to factor
      Message 2 of 2 , Nov 1, 2004
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Sudarshan Iyengar wrote:
        >
        > Hi,
        >
        > I have been wondering how exactly pari(http://pari.math.u-
        > bordeaux.fr/) factors big integers(which are of 60 digit or more in
        > length).
        >

        For PARI/GP, you can expose a lot of the internal factorization
        process very easily. Turn on debug level 5, with the command
        "\g 5" and then try to factor a big number:

        ? \g 5
        debug = 5
        ? factorint(10^60+1)

        ... gives fairly detailed running commentary on how it
        factors this number ...


        Also, just ask for help on the factorint() command:

        ? ?factorint
        factorint(x,{flag=0}): factor the integer x. flag is optional,
        whose binary digits mean 1: avoid MPQS, 2: avoid first-stage ECM
        (may fall back on it later), 4: avoid Pollard-Brent Rho and Shanks
        SQUFOF, 8: skip final ECM (huge composites will be declared prime)


        So this shows you right away that PARI uses any of MPQS, ECM,
        Pollard-Brent Rho and Shanks SQUFOF algorithms to factor integers.


        You can look at the PARI source code to learn more about these
        algorithms, but realize that PARI is not primarily intended as
        a factorization program, so the implementations within PARI may
        be somewhat restricted in the size of the numbers, or may have
        other compromises -- such as the fact that PARI will swap MPQS
        information out to disk even if there is sufficient RAM available.
      Your message has been successfully submitted and would be delivered to recipients shortly.