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

What are the limits to GMP-ECM?

Expand Messages
  • sleephound
    I m trying P-1 factoring using the P2 variation of the GMP-ECM5 programs from the files section. I haven t found any information on the size of numbers it can
    Message 1 of 2 , Jun 4, 2003
    • 0 Attachment
      I'm trying P-1 factoring using the P2 variation of the GMP-ECM5
      programs from the files section. I haven't found any information on
      the size of numbers it can handle. 90,000 digit numbers seem to work,
      but million digit numbers generate error conditions and end the
      program. Using the -save and -resume switches for a 100 digit number
      I have generated a 40e8 save file, but trying to do Stage 2 to 1e13
      generates a message "Error, overflow in fin_diff_coeffs." Does anyone
      know the limits on the size of numbers and B2 sizes that can be
      handled?
    • Paul Leyland
      ... It s best to ask questions such as these to the authors, whom I ve added to the Cc: line so they get to see them in this instance. I think there may be two
      Message 2 of 2 , Jun 5, 2003
      • 0 Attachment
        > I'm trying P-1 factoring using the P2 variation of the GMP-ECM5
        > programs from the files section. I haven't found any information on
        > the size of numbers it can handle. 90,000 digit numbers seem to work,
        > but million digit numbers generate error conditions and end the
        > program. Using the -save and -resume switches for a 100 digit number
        > I have generated a 40e8 save file, but trying to do Stage 2 to 1e13
        > generates a message "Error, overflow in fin_diff_coeffs." Does anyone
        > know the limits on the size of numbers and B2 sizes that can be
        > handled?

        It's best to ask questions such as these to the authors, whom I've
        added to the Cc: line so they get to see them in this instance.

        I think there may be two distinct problems that you've run into. The
        second one is properly a matter for Paul and Alex.

        The first, however, suggests to me that you have run into GMP's
        notorious stack overflow problems. GMP by default puts all its data
        on the stack (it uses alloca() to allocate memory) for speed and many
        systems have a maximum size for stack usage that is *much* less than
        the amount of memory available in the heap. A few megabytes is not
        uncommon. Given that a million-digit integer is going to need around
        100Kb, it won't take many of these before a program runs out of stack
        space.

        There are 3 ways of getting around the stack space limits. Which, if
        any, is applicable in your case is hard to tell because you don't say
        what system you are running on and whether you can recompile the code.
        They are:

        a) Tell your OS to allow a program a bigger stack.

        b) Recompile GMP not to use alloca(). The documentation will explain
        how to do this. Then recompile and link GMP-ECM5 with the new GMP
        library.

        c) Accept the limitations and don't use such big integers. This to
        me is the least satisfactory "solution" but it may be all you can do
        if you can't use either of the other techniques.


        Paul
      Your message has been successfully submitted and would be delivered to recipients shortly.