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

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

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.
• 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
>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,
>
>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/
>
>
>
>
>
>
>
>
• ... 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,
>
> 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.

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
• 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?!
• ... 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?!

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
• 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

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

Kermit < kermit@... >
• ... 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
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.