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

Re: how can one factor big integers?

Expand Messages
  • 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 1 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.