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

Re: [PrimeNumbers] Estimate the time for the Miller-Rabin test on big prime numbers

Expand Messages
  • Jack Brennen
    ... I can t answer that right away, but probably somebody here can. ... Unfortunately, your sample size is too small (and too far away) to give useful
    Message 1 of 8 , Jul 16, 2006
    • 0 Attachment
      initial29118 wrote:
      > I study primes and particularly, generation of very big primes with
      > computer. I'm looking for new algorithms, which are different from
      > mersenne primes' one. I have a technical problem : I don't have any
      > idea of how could I find the biggest time necessary for 3 iterations of
      > the Miller-Rabin test (with a Pentium III 1,8 GHz, C/C++ and GMP
      > library) with a number of x millions of digits. I don't need an exact
      > result but just an approximative one (+/- a week). Can you help me,
      > advise me?

      I can't answer that right away, but probably somebody here can.


      >
      > I've started some tests, with prime numbers of 1000 digits, then 2000,
      > 3000, 5000, 10.000 and 20.000 digits. I've recorded the used time. So,
      > I have 6 points of the blend but I need to foresee the continuation of
      > the bend in order to guess the time I need for numbers of about
      > 2.000.000 digits. Does someone know a software which can do that?
      >


      Unfortunately, your sample size is too small (and too far away)
      to give useful extrapolation for numbers with millions of digits.

      The run-time of such algorithms on real-world computers tends to
      exhibit "step discontinuities" when cache sizes are exceeded or
      when other resource limitations intrude on the ideal behavior.


      If you try to fit a curve to the run time, you will find that you
      need different curves for different numbers of digits. To be
      truly certain of the time to test a number of 2 million digits,
      test such a number. If that takes too long, run 1% of such a
      test, time that, and multiply by 100. It's not perfect, but it's
      better than trying to extrapolate from much smaller numbers.
    • miltbrown@earthlink.net
      If you are looking at PRP s of the form 10^x+y See my message 981 to this group, April 25, 2001 Milton L. Brown
      Message 2 of 8 , Jul 16, 2006
      • 0 Attachment
        If you are looking at PRP's of the form 10^x+y

        See my message 981 to this group,
        April 25, 2001

        Milton L. Brown

        -----Original Message-----
        >From: initial29118 <ben.umi@...>
        >Sent: Jul 16, 2006 5:07 AM
        >To: primenumbers@yahoogroups.com
        >Subject: [PrimeNumbers] Estimate the time for the Miller-Rabin test on big prime numbers
        >
        >I study primes and particularly, generation of very big primes with
        >computer. I'm looking for new algorithms, which are different from
        >mersenne primes' one. I have a technical problem : I don't have any
        >idea of how could I find the biggest time necessary for 3 iterations of
        >the Miller-Rabin test (with a Pentium III 1,8 GHz, C/C++ and GMP
        >library) with a number of x millions of digits. I don't need an exact
        >result but just an approximative one (+/- a week). Can you help me,
        >advise me?
        >
        >I've started some tests, with prime numbers of 1000 digits, then 2000,
        >3000, 5000, 10.000 and 20.000 digits. I've recorded the used time. So,
        >I have 6 points of the blend but I need to foresee the continuation of
        >the bend in order to guess the time I need for numbers of about
        >2.000.000 digits. Does someone know a software which can do that?
        >
        >Initial29118
        >
        >
        >
        >
        >
        >
        >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        >The Prime Pages : http://www.primepages.org/
        >
        >
        >Yahoo! Groups Links
        >
        >
        >
        >
        >
        >
      • Phil Carmody
        ... The OP can. However, using GMP is horribly foolish. PFGW is the best thing for the job. ... Do you need it enough to try with 30000, 50000, 100000
        Message 3 of 8 , Jul 16, 2006
        • 0 Attachment
          --- Jack Brennen <jb@...> wrote:
          > initial29118 wrote:
          > > I study primes and particularly, generation of very big primes with
          > > computer. I'm looking for new algorithms, which are different from
          > > mersenne primes' one. I have a technical problem : I don't have any
          > > idea of how could I find the biggest time necessary for 3 iterations of
          > > the Miller-Rabin test (with a Pentium III 1,8 GHz, C/C++ and GMP
          > > library) with a number of x millions of digits. I don't need an exact
          > > result but just an approximative one (+/- a week). Can you help me,
          > > advise me?
          >
          > I can't answer that right away, but probably somebody here can.

          The OP can.

          However, using GMP is horribly foolish. PFGW is the best thing for the job.

          > > I've started some tests, with prime numbers of 1000 digits, then 2000,
          > > 3000, 5000, 10.000 and 20.000 digits. I've recorded the used time. So,
          > > I have 6 points of the blend but I need to foresee the continuation of
          > > the bend in order to guess the time I need for numbers of about
          > > 2.000.000 digits. Does someone know a software which can do that?

          Do you "need" it enough to try with 30000, 50000, 100000 digits?

          > Unfortunately, your sample size is too small (and too far away)
          > to give useful extrapolation for numbers with millions of digits.

          In some ways yes you're right. However, just to be contrary I
          will have to say you're wrong too. The extrapolation almost
          certainly points in a direction such that at 2M digits will take
          more time than his patience, and no such endeavour will be even
          begun. 1 year, 100 years, what's the difference?

          > The run-time of such algorithms on real-world computers tends to
          > exhibit "step discontinuities" when cache sizes are exceeded or
          > when other resource limitations intrude on the ideal behavior.

          Only with bad algorithms. Well-written algorithms degrade gracefully,
          as they are written with cache issues in mind. I suspect GMP has not
          taken things into account, but I _know_ that George Woltman has taken
          them into account in his FFTs.

          > If you try to fit a curve to the run time, you will find that you
          > need different curves for different numbers of digits. To be
          > truly certain of the time to test a number of 2 million digits,
          > test such a number. If that takes too long, run 1% of such a
          > test, time that, and multiply by 100. It's not perfect, but it's
          > better than trying to extrapolate from much smaller numbers.

          A PRP test of a 2M digit number consists of several million multiplies.
          Even testing 100 multiplies is sufficient to work out how long 2M
          will take. The variation between runs is normally minimal.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        • julienbenney
          Re: A PRP test of a 2M digit number consists of several million multiplies. Even testing 100 multiplies is sufficient to work out how long 2M will take. The
          Message 4 of 8 , Jul 16, 2006
          • 0 Attachment
            Re: "A PRP test of a 2M digit number consists of several million multiplies. Even
            testing 100 multiplies is sufficient to work out how long 2M will take. The variation
            between runs is normally minimal."

            I have had this problem: I have been trying to find the previous prime to 1000
            factorial - which as you would probably know is a number of 2568 digits - using
            Dario Alpern's site "http://www.alpertron.com.ar/ECM.HTM". Whilst I was aware that
            site would take some time to find the number, it gave so few clues as to how long the
            number would take to find that after about forty minutes with no hint as to when the
            number would be found I just stopped and gave up.

            Whilst I am well aware that there is much better software for doing the job, I wonder
            if any of you have done that or a very closely related experiment and what you
            findings are?!
          • Phil Carmody
            ... A completely different problem from the one the OP asked. His was I don t know how long a predetermined number of operations will take . Yours is I don t
            Message 5 of 8 , Jul 16, 2006
            • 0 Attachment
              --- julienbenney <jpbenney@...> wrote:
              > Re: "A PRP test of a 2M digit number consists of several million multiplies.
              > Even
              > testing 100 multiplies is sufficient to work out how long 2M will take. The
              > variation
              > between runs is normally minimal."
              >
              > I have had this problem: I have been trying to find the previous prime to
              > 1000
              > factorial - which as you would probably know is a number of 2568 digits -
              > using
              > Dario Alpern's site "http://www.alpertron.com.ar/ECM.HTM". Whilst I was aware
              > that
              > site would take some time to find the number, it gave so few clues as to how
              > long the
              > number would take to find that after about forty minutes with no hint as to
              > when the
              > number would be found I just stopped and gave up.

              A completely different problem from the one the OP asked.
              His was "I don't know how long a predetermined number of operations will take".
              Yours is "I don't know how long an unknown number of operations will take".

              > Whilst I am well aware that there is much better software for doing the job,
              > I wonder
              > if any of you have done that or a very closely related experiment and what
              > you
              > findings are?!

              1 - sieve (even GP/Pari can do this task adequately)
              2 - pfgw

              Phil

              () ASCII ribbon campaign () Hopeless ribbon campaign
              /\ against HTML mail /\ against gratuitous bloodshed

              [stolen with permission from Daniel B. Cristofani]

              __________________________________________________
              Do You Yahoo!?
              Tired of spam? Yahoo! Mail has the best spam protection around
              http://mail.yahoo.com
            • Kermit Rose
              Time for finding a prime number in practice Posted by: julienbenney jpbenney@ftml.net julienbenney Date: Sun Jul 16, 2006 6:48 pm (PDT) Re: A PRP test of a
              Message 6 of 8 , Jul 17, 2006
              • 0 Attachment
                Time for finding a prime number in practice
                Posted by: "julienbenney" jpbenney@... julienbenney
                Date: Sun Jul 16, 2006 6:48 pm (PDT)

                Re: "A PRP test of a 2M digit number consists of several million multiplies.
                Even
                testing 100 multiplies is sufficient to work out how long 2M will take. The
                variation
                between runs is normally minimal."

                I have had this problem: I have been trying to find the previous prime to
                1000
                factorial - which as you would probably know is a number of 2568 digits -
                using


                ************

                Suggestion.

                Find 1000 factorial mod p for primes p < 1 000 000.

                Then use sieve technique to eliminate all the multiples of primes < 1 000
                000

                within your range of search.

                You may then find that you will find a prime fairly quickly among the
                remaining candidates.


                Kermit < kermit@... >
              • Dario Alpern
                ... multiplies. Even ... take. The variation ... prime to 1000 ... digits - using ... was aware that ... as to how long the ... hint as to when the ... the
                Message 7 of 8 , Jul 24, 2006
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "julienbenney" <jpbenney@...>
                  wrote:
                  >
                  > Re: "A PRP test of a 2M digit number consists of several million
                  multiplies. Even
                  > testing 100 multiplies is sufficient to work out how long 2M will
                  take. The variation
                  > between runs is normally minimal."
                  >
                  > I have had this problem: I have been trying to find the previous
                  prime to 1000
                  > factorial - which as you would probably know is a number of 2568
                  digits - using
                  > Dario Alpern's site "http://www.alpertron.com.ar/ECM.HTM". Whilst I
                  was aware that
                  > site would take some time to find the number, it gave so few clues
                  as to how long the
                  > number would take to find that after about forty minutes with no
                  hint as to when the
                  > number would be found I just stopped and gave up.
                  >
                  > Whilst I am well aware that there is much better software for doing
                  the job, I wonder
                  > if any of you have done that or a very closely related experiment
                  and what you
                  > findings are?!
                  >
                  Julien,

                  The expression evaluator I programmed for the applet is not very
                  smart and it computes SPRPs for all odd numbers before or after the
                  argument. If sieving is added to the process, it could be about 10
                  times faster.

                  Best regards,

                  Dario Alpern
                  http://www.alpertron.com.ar/ENGLISH.HTM
                Your message has been successfully submitted and would be delivered to recipients shortly.