Opened 8 years ago

Closed 8 years ago

#15777 closed defect (fixed)

Problems with polynomials over extensions of finite fields

Reported by: tscrim Owned by: tscrim
Priority: critical Milestone: sage-6.2
Component: basic arithmetic Keywords: NTL
Cc: brucin, roed, jdemeyer, pbruin Merged in:
Authors: Jean-Pierre Flori Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: c742335 (Commits, GitHub, GitLab) Commit: c742335903c24c5021e9bd159169c6bb14906688
Dependencies: #13642 Stopgaps:

Status badges

Description

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.

Change History (13)

comment:1 Changed 8 years ago by tscrim

  • Dependencies set to #13642

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

comment:2 Changed 8 years ago by jpflori

  • Authors set to Jean-Pierre Flori
  • Branch set to u/jpflori/ticket/15777
  • Commit set to 2f4851d59727507cbb96ef1801e95cc0fc7a971a
  • Keywords NTL added
  • Status changed from new to needs_review

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:

d3e730dtrac #13642: modular exponentiation of polynomials
9917b28Reinstated doctest.
878bd99Marked new doctests as "not tested".
30d7f5bMerge remote-tracking branch 'trac/develop' into ticket/13642
623c5b6Reenable previously failing doctests for modular exponentiation of
2f4851dFix modular exponentiation of polynomials over finite field extensions.

comment:3 Changed 8 years ago by jpflori

  • Status changed from needs_review to needs_work

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

comment:4 follow-up: Changed 8 years ago by jpflori

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

comment:5 Changed 8 years ago by jpflori

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.

comment:6 Changed 8 years ago by jpflori

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.

comment:7 Changed 8 years ago by jpflori

This one is nice enough as well:

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

comment:8 in reply to: ↑ 4 Changed 8 years ago by jpflori

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.

comment:9 Changed 8 years ago by git

  • Commit changed from 2f4851d59727507cbb96ef1801e95cc0fc7a971a to c742335903c24c5021e9bd159169c6bb14906688

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

c742335Fix modular exponentiation of polynomials over finite field extensions.

comment:10 Changed 8 years ago by jpflori

  • Status changed from needs_work to needs_review

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.

comment:11 Changed 8 years ago by jpflori

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

comment:12 Changed 8 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

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

comment:13 Changed 8 years ago by vbraun

  • Branch changed from u/jpflori/ticket/15777 to c742335903c24c5021e9bd159169c6bb14906688
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.