defer primality and irreducibility testing in GF constructor until after caching

[yyyyx4]

Example:

sage: p = 2^521-1
sage: F = GF(p)
sage: GF(p) is F  # field is cached
True
sage: %timeit GF(p)
521 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Note that the constructor tests primality each time even though the field is already cached! This was pointed out here:

https://github.com/jack4818/Castryck-Decru-SageMath#speeding-sagemath-up-using-a-cache

In this patch, we move the primality and irreducibility testing from FiniteFieldFactory.create_key_and_extra_args() to FiniteFieldFactory.create_object(), so that it isn't performed again for fields already present in the cache.

The result is a massive speedup for repeated invocations of GF(p):

78.6 µs ± 870 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

CC: @k3w1k0d3r

Component: performance

Author: Lorenz Panny

Branch/Commit: 0b9db49

Reviewer: Julien Grijalva

Issue created by migration from https://trac.sagemath.org/ticket/34281

[sagetrac-git]

Changed commit from 94af055 to b5f2eac

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b5f2eac

update doctest outputs

[k3w1k0d3r]

Reviewer: Julien Grijalva

[k3w1k0d3r]

comment:6

patchbot failed a test, segfaulting when it reached the p, n = order.perfect_power() you added. I'm currently checking if I reproduce this locally.

[yyyyx4]

comment:7

I suspect this is a consequence of the other doctest failures here (which I also see on the unpatched develop branch). I can't reproduce it in isolation.

[k3w1k0d3r]

comment:8

I am able to reproduce this behavior locally. It seems like a bug in the perfect_power method though. I'll investigate.

[sagetrac-git]

Changed commit from b5f2eac to c6772dd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c6772dd

remove incorrect(?) sig_on/sig_off

[yyyyx4]

comment:10

Setting to "needs review" to get the patchbot to run, but I suspect there are still problems.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0b9db49

avoid failing code path by passing tuple to GF constructor

[sagetrac-git]

Changed commit from c6772dd to 0b9db49

[yyyyx4]

comment:12

With the most recent commit, I no longer see any failures on my machine. Still not sure what causes these crashes and why things only go wrong in pbori.pyx, but the workaround seems to, well, work around it.

[yyyyx4]

comment:13

Patchbot is morally green; I've seen the remaining failure in other (totally unrelated) tickets before.

[vbraun]

Changed branch from public/defer_primality_testing_in_cached_GF_constructor to 0b9db49