Skip to content

fmpz_mod_ctx always checks primality even if not needed #333

@remyoudompheng

Description

@remyoudompheng

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions