possible mpz_probab_prime_p speed-up
Marco Bodrato
bodrato at mail.dm.unipi.it
Sun Oct 30 18:59:55 CET 2022
Ciao Paul,
Il 2022-10-27 12:27 Paul Underwood ha scritto:
> please see:-
>
> 1) my paper:
> https://mersenneforum.org/showpost.php?p=592064&postcount=1
I'm sorry, but I didn't have the time to read your paper...
> 2) the GMP code:
> https://mersenneforum.org/showpost.php?p=616574&postcount=21
...but I quickly tested your code.
On the number (2^44497+1)/3, mpz_probab_prime_p uses 25% more time to
say that the number is composite.
On the number (1234567891^1473), mpz_probab_prime_p uses half the time.
One may say that, on average (based on two tests only!) the current code
is faster.
Of course, the first question should be if both codes are correct.
For this function, the second question should be about the probability
for a composite to pass undetected as a probable prime.
The question about speed makes sense after the two above:
How do their speed compare on average on random numbers?
Let's say random numbers that pass the trial-division step.
> Is there any interest in making this code native to GMP's
> mpz_probab_prime_p function?
GMP is a general library, it's not the best place for a collection of
composite/prime tests. Can you give some more arguments explaining why
and how do you propose to improve the current code?
Ĝis,
m
--
http://bodrato.it/papers/
More information about the gmp-discuss
mailing list