improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p

[ncalexan]

sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p is very old.

The attached patch removes (but doesn't yet delete -- could you verify it can be removed, reviewer?) Polynomial_dense_mod_p and implements polynomial_modn_dense_ntl.Polynomial_dense_modp_ntl_zz/ZZ using the newer techniques.

It makes basic arithmetic faster. I was finding that arithmetic in GF(next_prime(2^50))['x'] was slower than in Zmod(next_prime(2^50)+1)['x'], but now I cannot find the comparison! In any case, this is much faster for doing gcd/xgcd in GF(p)['x'].

CC: @craigcitro

Component: number theory

Keywords: polynomial modn finite field gf sd40.5

Reviewer: Mike Hansen

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

[sagetrac-mabshoff]

comment:1

Attachment: 4636-ncalexan-Polynomial_dense_modp_ntl_zz.patch.gz

[malb]

comment:2

Hi Nick, did you see the 'newest' technique to implement these things? It is not 100% polished yet (e.g. I suppose context handling should be improved) but it should be the most straight forward in terms of avoiding code duplication. See sage.rings.polynomial.polynomial_gf2x and sage.rings.polynomial.polynomial_template for details.

[williamstein]

comment:3

Nick, Is this supposed be "with patch; needs review"?

[williamstein]

comment:5

REFEREE REPORT:

I applied this patch and doctested the rings directory. I get a couple of doctest failures:

sage -t  devel/sage-main/sage/rings/integer_mod.pyx
**********************************************************************
File "/Users/wstein/sage/devel/sage-main/sage/rings/integer_mod.pyx", line 505:
    sage: type(a.polynomial())
Expected:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>
Got:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modp_ntl_zz'>
**********************************************************************

sage -t  devel/sage-main/sage/rings/finite_field_givaro.pyx
**********************************************************************
File "/Users/wstein/sage/devel/sage-main/sage/rings/finite_field_givaro.pyx", line 1799:
    sage: type(f)
Expected:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>
Got:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modp_ntl_zz'>
**********************************************************************
1 items had failures:


sage -t  devel/sage-main/sage/rings/finite_field.py
**********************************************************************
File "/Users/wstein/sage/devel/sage-main/sage/rings/finite_field.py", line 178:
    sage: type(f)
Expected:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>
Got:
    <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modp_ntl_zz'>
**********************************************************************
1 items had failures:

...
	sage -t  devel/sage-main/sage/rings/polynomial/multi_polynomial_libsingular.pyx # 1 doctests failed
	sage -t  devel/sage-main/sage/rings/integer_mod.pyx # 1 doctests failed
	sage -t  devel/sage-main/sage/rings/finite_field_givaro.pyx # 1 doctests failed
	sage -t  devel/sage-main/sage/rings/finite_field.py # 1 doctests failed

[malb]

comment:6

I should reimplement this using polynomial_template.pxi and Nick will review it once its done.

[mwhansen]

comment:9

What is the status of this? If no one is going to do the templated version, then we should probably include this code.

[malb]

comment:10

I vote for closing this ticket

sage: f = GF(7)['x']([2, 1, 3])
sage: type(f)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

[mwhansen]

comment:11

I agree with malb.

[mwhansen]

Changed keywords from polynomial modn finite field gf to polynomial modn finite field gf sd40.5

[jdemeyer]

Reviewer: Mike Hansen