Miller-Rabin prime test

[marco.bodrato at tutanota.com]

Ciao,

20 feb 2026, 13:14 da brederlo at q-leap.de:

> would it be possible to get the Miller-Rabin prime test function used for mpz_probab_prime_p() added to the public functions?
>

I'd answer no.
Even if the name is mpz_millerrabin, the current function actually does not simply perform a Miller-Rabin test, it implements (my "fault") the BPSW test.


> I want to use this to write a Miller test, meaning running the Miller-Rabin function for all numbers between [2, min(/n/ − 2, ⌊2(ln /n/)^2 ⌋)] for a deterministic prime test.
>

Moreover, also the previous implementation of the function did not allow to choose the bases, so that it never fitted to your needs.

In the file mpz/millerrabin.c there is a static millerrabin function that would fit. By the way, it's quite a simple one, that anyone can rewrite. The only "smart" idea is to implement an "ad-hoc" function to compare the numbers to the value "-1".
Moreover that function, to be efficient for repeated tests, needs too many "obscure" parameters to be made public.
But the licence of the source allows you to take the code and reuse it in any GPL project, don't it?


> Further would there be interest in adding the Adleman–Pomerance–Rumely primality test or elliptic curve primality proving function in case I implement them?
>
There are already some programs available on the net for that.
I did not check them, but:
 - mpz_aprcl is an implementation of the APR-CL test, using GMP;
 - gmp-ecpp is an implementation of the ECPP test, using GMP.

Ĝis,
mb