python-flint icon indicating copy to clipboard operation
python-flint copied to clipboard

fmpz_mod_ctx always checks primality even if not needed

Open remyoudompheng opened this issue 1 month ago • 1 comments

Currently fmpz_mod_ctx always runs a pseudo-primality test on the modulus, even if it is never used. When the modulus is huge, this can be inacceptable especially if the user purpose was to perform simple modular arithmetic.

In [7]: p = 2**64-59

In [9]: %time c = flint.fmpz_mod_ctx(p**100)
CPU times: user 3.27 ms, sys: 0 ns, total: 3.27 ms
Wall time: 3.28 ms

In [10]: %time c = flint.fmpz_mod_ctx(p**1000)
CPU times: user 205 ms, sys: 877 μs, total: 206 ms
Wall time: 206 ms

In [11]: %time c = flint.fmpz_mod_ctx(p**10000)
CPU times: user 20.1 s, sys: 39.5 ms, total: 20.2 s
Wall time: 20.2 s

A possible fix is to only initialize the _is_prime upon the first call to .is_prime() method which seems to be the only user.

remyoudompheng avatar Oct 05 '25 19:10 remyoudompheng

I thought it was used in more places like __truediv__ but it seems not.

Only initialising at first use seems reasonable.

oscarbenjamin avatar Oct 05 '25 20:10 oscarbenjamin