Let Sage use finite fields without primality proving

[jpflori]

It would be nice to be able to create finite fields without checking that the characteristic is actually prime.

You can more or less do that for prime fields using directly the FiniteField_prime_modn constructor with check=False arguments. Unfortunately some constructions on top of this will still check that the characteristic is actually prime, e.g. univariate polynomial rings on top of it.

Note that it already is possible to create an IntegerModRing(n, categogry=Fields()). This will create a quotient ring of ZZ that believes that it is a field. However, it will still be an integer mod ring that does not use any of the fancy finite field implementations in sage (and you'll have problems similar to those with the FiniteField_prime_modn anyway).

CC: @simon-king-jena @burcin

Component: categories

Keywords: finite fields, primality proving, sd53

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

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -3,3 +3,4 @@
 You can more or less do that for prime fields using directly the FiniteField_prime_modn constructor with check=False arguments.
 Unfortunately some constructions on top of this will still check that the characteristic is actually prime, e.g. univariate polynomial rings on top of it.

+Note that it already is possible to create an `IntegerModRing(n, categogry=Fields())`. This will create a quotient ring of ZZ that believes that it is a field. However, it will still be an integer mod ring that does not use any of the fancy finite *field* implementations in sage.

[jpflori]

Description changed:

--- 
+++ 
@@ -3,4 +3,4 @@
 You can more or less do that for prime fields using directly the FiniteField_prime_modn constructor with check=False arguments.
 Unfortunately some constructions on top of this will still check that the characteristic is actually prime, e.g. univariate polynomial rings on top of it.

-Note that it already is possible to create an `IntegerModRing(n, categogry=Fields())`. This will create a quotient ring of ZZ that believes that it is a field. However, it will still be an integer mod ring that does not use any of the fancy finite *field* implementations in sage.
+Note that it already is possible to create an `IntegerModRing(n, categogry=Fields())`. This will create a quotient ring of ZZ that believes that it is a field. However, it will still be an integer mod ring that does not use any of the fancy finite *field* implementations in sage (and you'll have problems similar to those with the FiniteField_prime_modn anyway).

[jpflori]

comment:2

I think this ticket might also be a good place to think about the use of methods like x.is_field(), x.is_prime_field(), x.is_finite_field(), x.is_integral_domain() and the constructions provided by the category framework like x in Fields(), x in FiniteFields(), x in IntegralDomains(), and so on.

Is there a real speed penalty when using the second construction (especially when x is actually not in Fields(), FiniteFields and so on as Simon suggested)? Does this speed penalty actually make some code awfully slow (maybe in elliptic curves computations as Simon suggested)? Are there places where we really depend on the actual implementation used and so where using is_FiniteField(x) and similar stuff cannot be replaced by x.is_finite_field() or x in FiniteFields() anyway?

[jpflori]

comment:3

Attachment: pff.patch.gz

I've attached a patch I actually used and which let me use the IntegerModRing class with the category=Fields() trick and prevented all primality checking (in my use case at least; I don't say you can do whatever you want on top of the constructed object and it will never check primality).

I don't claim it should be used, but at least it may bring to light some places where Sage is to eager to check for primality.

[jpflori]

Changed keywords from finite fields, primality proving to finite fields, primality proving, sd53

[simon-king-jena]

comment:5

Concerning things that may be slower: Practical examples can probably by found on #11900.

Raw timings in Python

sage: class PyRing(Parent):
....:     def is_field(self):
....:         return False
....:     
sage: class PyField(Parent):
....:     def is_field(self):
....:         return True
....:     
sage: TrueRing = PyRing(category=Rings())
sage: RingInFields = PyRing(category=Fields())
sage: MockField = PyField(category=Rings())
sage: TrueField = PyField(category=Fields())
sage: F = Fields()

A ring that is not a field:

sage: TrueRing in F
False
sage: %timeit TrueRing in F
100000 loops, best of 3: 2.07 us per loop
sage: %timeit TrueRing.is_field()
1000000 loops, best of 3: 291 ns per loop

A ring that is put into the category of fields. Hence, R in Fields() and R.is_field() give different answers. I am doing this just for completeness:

sage: %timeit RingInFields in F
1000000 loops, best of 3: 821 ns per loop
sage: %timeit RingInFields.is_field()
1000000 loops, best of 3: 287 ns per loop

A field that is only initialised in the category of rings. Note that because .is_field() returns True and because of the way how Fields.__contains__ works, the category is refined after the first containment test:

sage: MockField.category()
Category of rings
sage: MockField in F
True
sage: MockField.category()
Category of fields
sage: %timeit MockField in F
1000000 loops, best of 3: 823 ns per loop
sage: %timeit MockField.is_field()
1000000 loops, best of 3: 312 ns per loop

And finally, a field that is a field that is a field...

sage: %timeit TrueField in F
1000000 loops, best of 3: 819 ns per loop
sage: %timeit TrueField.is_field()
1000000 loops, best of 3: 309 ns per loop

Raw timings in Cython

We construct similar examples as above, both for Python classes in Cython and for "real" extension classes. So, we have eight examples.

sage: cython("""
....: from sage.structure.parent cimport Parent
....: class CyRing(Parent):
....:     def is_field(self):
....:         return False
....: class CyField(Parent):
....:     def is_field(self):
....:         return True
....: cdef class ExtRing(Parent):
....:     def is_field(self):
....:         return False
....: cdef class ExtField(Parent):
....:     def is_field(self):
....:         return True
....: """)

First, the Python classes defined in Cython:

sage: TrueRing = CyRing(category=Rings())
sage: RingInFields = CyRing(category=Fields())
sage: MockField = CyField(category=Rings())
sage: TrueField = CyField(category=Fields())
sage: %timeit TrueRing in F
1000000 loops, best of 3: 1.85 us per loop
sage: %timeit TrueRing.is_field()
1000000 loops, best of 3: 236 ns per loop
sage: %timeit RingInFields in F
1000000 loops, best of 3: 850 ns per loop
sage: %timeit RingInFields.is_field()
1000000 loops, best of 3: 250 ns per loop
sage: %timeit MockField in F
1000000 loops, best of 3: 846 ns per loop
sage: %timeit MockField.is_field()
1000000 loops, best of 3: 252 ns per loop
sage: %timeit TrueField in F
1000000 loops, best of 3: 852 ns per loop
sage: %timeit TrueField.is_field()
1000000 loops, best of 3: 231 ns per loop

And finally the extension classes:

sage: TrueRing = ExtRing(category=Rings())
sage: RingInFields = ExtRing(category=Fields())
sage: MockField = ExtField(category=Rings())
sage: TrueField = ExtField(category=Fields())
sage: %timeit TrueRing in F
1000000 loops, best of 3: 1.81 us per loop
sage: %timeit TrueRing.is_field()
10000000 loops, best of 3: 166 ns per loop
sage: %timeit RingInFields in F
1000000 loops, best of 3: 826 ns per loop
sage: %timeit RingInFields.is_field()
10000000 loops, best of 3: 162 ns per loop
sage: %timeit MockField in F
1000000 loops, best of 3: 845 ns per loop
sage: %timeit MockField.is_field()
10000000 loops, best of 3: 163 ns per loop
sage: %timeit TrueField in F
1000000 loops, best of 3: 836 ns per loop
sage: %timeit TrueField.is_field()
10000000 loops, best of 3: 167 ns per loop

Remark

Testing containment in other singleton categories is faster then testing in Fields():

sage: TrueField = PyField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 358 ns per loop
sage: TrueField = CyField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 362 ns per loop
sage: TrueField = ExtField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 352 ns per loop

Conclusion

I think the timings clearly show that is_field() is always faster by a factor of more than two and often an even bigger factor. There might be a slow-down, however, because one should wrap R.is_field() into a try: ... except AttributeError: ... statement.

[jdemeyer]

comment:10

Please change the ticket title and description to better reflect what this patch is really about. It seems to be more about categories and less about primality proving.