- initial29118 wrote:
> I study primes and particularly, generation of very big primes with

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

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

>

Unfortunately, your sample size is too small (and too far away)

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

>

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. - --- In primenumbers@yahoogroups.com, "julienbenney" <jpbenney@...>

wrote:>

multiplies. Even

> Re: "A PRP test of a 2M digit number consists of several million

> testing 100 multiplies is sufficient to work out how long 2M will

take. The variation

> between runs is normally minimal."

prime to 1000

>

> I have had this problem: I have been trying to find the previous

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

the job, I wonder

>

> Whilst I am well aware that there is much better software for doing

> 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