possible mpz_probab_prime_p speed-up

[Marco Bodrato]

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/