Opened 5 years ago

Last modified 2 years ago

#20670 new enhancement

Let the user define their own primitive element for Fq (in givaro)

Reported by: dimpase Owned by: dimpase
Priority: major Milestone: sage-7.6
Component: finite rings Keywords:
Cc: jakobkroeker, cpernet, malb Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by dimpase)

Sage does not allow Fq to be defined with a user-supplied polynomial together with a user-supplied primitive element. However, recent (4.0.2 or newer) givaro is able to accept such input and use it.

Change History (25)

comment:1 in reply to: ↑ description Changed 5 years ago by jdemeyer

Replying to dimpase:

Givaro does not allow Fq to be defined with a user-supplied polynomial.

Why do you think that?

sage: k.<a> = GF(9, modulus=x^2+1)
sage: k
Finite Field in a of size 3^2
sage: k.modulus()
x^2 + 1
sage: type(k)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>

comment:2 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-7.3 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:3 Changed 5 years ago by dimpase

Do you know how to do this on C++ level?

At least, that's what Macaulay2 people came up with, that patch in the ticket branch. Perhaps they should have done this differently?

comment:4 Changed 5 years ago by jdemeyer

In givgfq.h, there is

template<typename Vector>
GFqDom(const UTT P, const UTT e, const Vector& modPoly);

right above the line added by Macaulay2.

Note the subtle difference: it does not take a generatorPoly argument in case that matters.

comment:5 Changed 5 years ago by dimpase

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.3

well, yes, indeed, in Macaulay2 one can specify a primitive element along with a modulus. So with this patch Sage can do the same (although I don't see how to override k.multiplicative_generator(); I thought I can just specify self.__multiplicative_generator in FiniteField_givaro, but it does not work...)

It seems that FiniteField_givaro isn't even used, and the whole class structure is a mystery to me here.

comment:6 follow-up: Changed 5 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from needs_review to needs_info
  • Summary changed from let the user define their own polynomial for Fq in givaro to Let the user define their own modulus and primitive element for Fq in givaro

Are you sure that Macaulay2 really requires a custom primitive element and a custom polynomial or is that just an implementation detail?

comment:7 in reply to: ↑ 6 Changed 5 years ago by dimpase

Replying to jdemeyer:

Are you sure that Macaulay2 really requires a custom primitive element and a custom polynomial or is that just an implementation detail?

Given a modulus (or not), it can certainly compute a primitive element, although it does have an option to supply a custom primitive element. And to do this it uses givaro backend with the patch in question.

comment:8 Changed 5 years ago by dimpase

This is one of the two patches (another one is for ffpack) needed to build and run Macaulay2 v1.9 (the current version, with an adaptation of Sage's pari/mpir workaround --- after I told them about Sage's pari/mpir workaround related to memory allocators) within Sage.

comment:9 Changed 5 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Status changed from needs_info to needs_review

comment:10 follow-up: Changed 5 years ago by vbraun

The patch should have some sort of documentation (ideally in the patch header)

comment:11 in reply to: ↑ 10 Changed 5 years ago by dimpase

  • Cc malb added

Replying to vbraun:

The patch should have some sort of documentation (ideally in the patch header)

my hope is to implement a possibility to supply a primitive element to GF(), using this patch as a backend. But I got lost trying to figure out how the current implementation uses givaro.

Could anyone point me to the right place in the code?

comment:12 Changed 5 years ago by dimpase

I am told that the patch on the branch is in givaro 4.0.2.

comment:13 Changed 5 years ago by dimpase

  • Dependencies set to #17635
  • Status changed from needs_review to needs_info

comment:14 Changed 5 years ago by dimpase

  • Milestone changed from sage-7.3 to sage-7.4

comment:15 Changed 5 years ago by cpernet

Indeed, the patch has been merged upstream in https://github.com/linbox-team/givaro/pull/18 and released in 4.0.2 that is now in #17635.

comment:16 Changed 5 years ago by jdemeyer

  • Authors Dima Pasechnik deleted
  • Milestone changed from sage-7.4 to sage-duplicate/invalid/wontfix
  • Reviewers changed from Jeroen Demeyer to Dima Pasechnik, Jeroen Demeyer
  • Status changed from needs_info to positive_review

comment:17 Changed 5 years ago by dimpase

the question I asked in comment:11 is still unanswered.

comment:18 follow-up: Changed 5 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).

comment:19 Changed 4 years ago by dimpase

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.6
  • Owner changed from (none) to dimpase

comment:20 in reply to: ↑ 18 Changed 4 years ago by dimpase

Replying to embray:

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).

I have to re-open this, but is it possible without opening a new ticket?

comment:21 Changed 4 years ago by embray

  • Resolution wontfix deleted
  • Status changed from closed to new

Yes, (under action). I think you have the permissions to do that but I'm not sure. I've been yelled at before for doing this but in this case I was the one who closed the ticket so I don't mind reopening it too if you think it should be.

comment:22 Changed 4 years ago by dimpase

  • Description modified (diff)
  • Summary changed from Let the user define their own modulus and primitive element for Fq in givaro to Let the user define their own primitive element for Fq (in givaro)

comment:23 Changed 3 years ago by jdemeyer

  • Component changed from packages: standard to finite rings

comment:24 Changed 3 years ago by jdemeyer

  • Branch u/dimpase/givaropatch deleted
  • Commit adb59c0578594b351c0e7a9192ea0a992ec27339 deleted
  • Dependencies #17635 deleted
  • Reviewers Dima Pasechnik, Jeroen Demeyer deleted

comment:25 Changed 2 years ago by dimpase

Ping - I have been recently asked how to define a custom primitive element (Magma can do it, so they have to use Magma because of this, and better support for Zech transform)

Note: See TracTickets for help on using tickets.