Ticket #4636 (new defect)

Opened 1 month ago

Last modified 1 month ago

[with patch, needs work] improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p

Reported by: ncalexan Assigned to: was
Priority: major Milestone: sage-3.4
Component: number theory Keywords: polynomial modn finite field gf
Cc:

Description (Last modified by mabshoff)

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?.

Attachments

4636-ncalexan-Polynomial_dense_modp_ntl_zz.patch (24.7 kB) - added by ncalexan on 11/26/2008 08:45:22 PM.

Change History

11/26/2008 08:45:22 PM changed by ncalexan

  • attachment 4636-ncalexan-Polynomial_dense_modp_ntl_zz.patch added.

11/26/2008 08:51:09 PM changed by mabshoff

  • description changed.

11/27/2008 02:27:11 AM changed by malb

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.

11/27/2008 08:41:10 AM changed by was

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

11/27/2008 08:44:19 AM changed by ncalexan

  • summary changed from improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p to [with patch, needs review] improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p.

11/27/2008 08:45:08 PM changed by was

  • summary changed from [with patch, needs review] improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p to [with patch, needs work] improve polynomial_modn_dense_ntl.Polynomial_dense_mod_p.

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