Problems with polynomials over extensions of finite fields

[tscrim]

While looking at #13642, I noticed the following:

sage: k = GF(5)
sage: D.<x> = k[]
sage: l.<x> = k.extension(x^2 + 2)
sage: R.<t> = l[]
sage: f = t^4 + (2*x - 1)*t^3 + (2*x + 1)*t^2 + 3
sage: h = t^4 - x*t^3 + (3*x + 1)*t^2 + 2*t + 2*x - 1
sage: pow(f, 2, h)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
...
RuntimeError: PowerMod: bad args

sage: pow(t, 2, x) # segfault

This occurs on a clean 6.1.

Depends on #13642

CC: @burcin @roed314 @jdemeyer @pjbruin

Component: basic arithmetic

Keywords: NTL

Author: Jean-Pierre Flori

Branch: c742335

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:1

Also we should re-enable the tests in #13642.

[tscrim]

Dependencies: #13642

[jpflori]

Changed keywords from none to NTL

[jpflori]

Commit: 2f4851d

[jpflori]

Author: Jean-Pierre Flori

[jpflori]

comment:2

It was a problem with the use of NTL modular exp which does not like the base of equal or higher degree than the modulus.

---

New commits:

d3e730d	trac #13642: modular exponentiation of polynomials
9917b28	Reinstated doctest.
878bd99	Marked new doctests as "not tested".
30d7f5b	Merge remote-tracking branch 'trac/develop' into ticket/13642
623c5b6	Reenable previously failing doctests for modular exponentiation of
2f4851d	Fix modular exponentiation of polynomials over finite field extensions.

[jpflori]

Branch: u/jpflori/ticket/15777

[jpflori]

comment:3

Oops, I forgot the segfault which was not in the disabled tests.

[jpflori]

comment:4

Ok NTL does not like building a pre conditionning modulus object when the modulus is of degree one...

[jpflori]

comment:5

Not sure what to do about this one:

sage: x = polygen(GF(5))
sage: x % 2
0

and similar stuff.
Whatsoever, I propose to postpone that case where the modulus is of degree < 1 to a later ticket.

[jpflori]

comment:6

This one in not so good as well:

sage: x = polygen(GF(5))
sage: pow(x,100000000000,x)
Exception (FLINT memory_manager). Unable to allocate memory.

[jpflori]

comment:7

This one is nice enough as well:

sage: x = polygen(ZZ)
sage: pow(x,100,x+1)
x^100

[jpflori]

comment:8

Replying to @jpflori:

Ok NTL does not like building a pre conditionning modulus object when the modulus is of degree one...

Same problem for NTL GF2X polynomials.

[sagetrac-git]

Changed commit from 2f4851d to c742335

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c742335

Fix modular exponentiation of polynomials over finite field extensions.

[jpflori]

comment:10

At least the two problems mentioned in the ticket description and involving NTL are fixed now.

The polynomial stuff needs major refactoring anyway, we should move the template files to different folders in the spirit of what was done in #12555 for p-adics, use templating for additional classes, etc.; so let's postpone the other issues I reported here to follow up tickets.

[jpflori]

comment:11

Follow-up tickets: #15866, #15867, #15868.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:12

Well let's get on those, but first, positive review here. Thanks Jean-Pierre.

[vbraun]

Changed branch from u/jpflori/ticket/15777 to c742335

[fchapoton]

Changed commit from c742335 to none