mpz_probab_prime_p(n, reps) : how long?

[jojo 29]

OK, very interesting! Thanks you for this information.

A last precision : the complexity of GMP's Miller-Rabin implementation is 
"O(n^(2*log(n)))" or "O((n^2)*log(n))"? (you've forgotten a parenthesis in 
your last mail so I'm not sure...)

Thanks a lot.

Jojo.


>From: Torbjorn Granlund <tege at swox.com>
>To: "jojo 29" <jojo29118 at hotmail.com>
>CC: gmp-discuss at swox.com
>Subject: Re: mpz_probab_prime_p(n, reps) : how long?
>Date: 10 Mar 2005 12:43:51 +0100
>MIME-Version: 1.0
>Received: from king.swox.se ([195.17.28.216]) by mc7-f39.hotmail.com with 
>Microsoft SMTPSVC(6.0.3790.211); Thu, 10 Mar 2005 03:44:16 -0800
>Received: by king.swox.se (Postfix, from userid 1001)id AED0041; Thu, 10 
>Mar 2005 12:43:51 +0100 (CET)
>
>"jojo 29" <jojo29118 at hotmail.com> writes:
>
>   My god! many years?! I get a similar result using the bench test of the
>   GIMPS project (http://www.mersenne.org/bench.htm)...
>
>   Is it possible to get probab_prime_p() faster?
>
>The complexity of GMP's Miller-Rabin implementation is
>O(n^2*log(n).  No better algorithm is known (to me).
>
>I don't think here is much hope to cope with a 33 million digit
>number any time soon.  A current high-end machine would need
>about 100 years for your number, if my estimates are right.
>
>--
>Torbjörn