Change the field where a polynomial is considered

[Irene]

Hello!

I want to define a polynomial that I know lies in GF(p^2,'b')[x], p=3700001. The problem is that I have to define it as a product E=(X-a_1)*(X-a_2)*(X-a_3)*(X-a_4)*(X-a_5)*(X-a_6), where every a_j is in GF(p^13,'a')[X].

I tried to do GF(p^2,'b')[x](E), but then Sage just changes the generator 'a' and writes the same expression with the generator 'b'.

Any idea about how to do this?

Thank you!!

[John Cremona]

Did you write that correctly? GF(p^13) is not an extension of
GF(p^2). If a1 is in GF(p^13) then a1.minpoly() will give its min
poly, in GF(p)[x].

John Cremona

>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Irene]

Sorry, I didn't write it correctly. I meant GF(p^12,'a') instead of GF(p^13,'a'). As 2 divides 12, GF(p^12,'a') is an extension of GF(p^2,'b'). My question is the same now with the correct data.

[John Cremona]

OK, that makes sense now. It boils down to this: given an element of
F12=GF(p^12) which happens to lie in F2 = GF(p^2), how to express it
in terms of a generator of F2. This is not quite as easy as it should
be but this works (assuming that you have defined F12 with generator a
and F2 with generator b):

sage: bb = b.minpoly().roots(F12)[0][0]
sage: i = F2.hom([bb],F12)
sage: j = i.section()

Here we have defined an embedding i of F2 into F12 by find a place to
map b (called bb) and set j to be an inverse to i. (I think we should
be use i.inverse_image() but that gave me a NotImplementedError, which
is a pity since I have used sort of construction easily in extensions
of number fields).

Now if f is your polynomial in F12[x] whose coefficients lie in F2 you can say

sage: PolynomialRing(F2,'X')([j(c) for c in f.coeffs()])

to get what you want, I hope!

John

[Peter Bruin]

Hello,

I want to define a polynomial that I know lies in GF(p^2,'b')[x], p=3700001. The problem is that I have to define it as a product E=(X-a_1)*(X-a_2)*(X-a_3)*(X-a_4)*(X-a_5)*(X-a_6), where every a_j is in GF(p^13,'a')[X].

I tried to do GF(p^2,'b')[x](E), but then Sage just changes the generator 'a' and writes the same expression with the generator 'b'.

Any idea about how to do this?

There is a mathematical difficulty behind this: although the field of p^2 elements is a subfield of the field of p^12 elements, it is not a subfield in a canonical way.  If you want automatic conversion between the two fields, you have to make sure that Sage recognises GF(p^2) as being a subfield of GF(p^12) in some well-defined way.  This can be done using Conway polynomials as defining polynomials for the two finite fields.  If (in Sage 5.13 or newer) you create the finite fields with

  sage: K = GF(p^2, 'a', conway=True, prefix='z')
  sage: L = GF(p^12, 'b', conway=True, prefix='z')

then it should be possible to automatically map field elements back and forth between the two fields.

  sage: R = K['x']
  sage: S = L['x']
  sage: x = S.gen()
  sage: f = (x - b) * (x - b^9); f
  x^2 + (2*b^3 + 2*b^2)*x + 2*b^3 + 2*b^2 + 1
  sage: R(f)
  x^2 + (a + 2)*x + a
  sage: S(R(f)) == f
  True

There was actually another bug (involving polynomial rings) that caused this not to work; it was fixed only 6 weeks ago, so you may have to wait for Sage 6.2 or to download the latest development version.  I just saw that John Cremona gave another solution, which does not rely on Conway polynomials and automatic conversion, so this may be easier to use (although you have to explicitly invoke the maps i and j).

Peter

[Irene]

I think that this is exactly what I need. Nevertheless I cannot use neither i.section() nor i.inverse_image(). The second one because of the same reason as you, and the first one when I try it is says "TypeError: 'NoneType' object is not callable".

[John Cremona]

On 17 April 2014 08:43, Irene <irene....@gmail.com> wrote:
> I think that this is exactly what I need. Nevertheless I cannot use neither
> i.section() nor i.inverse_image(). The second one because of the same reason
> as you, and the first one when I try it is says "TypeError: 'NoneType'
> object is not callable".

You'll have to post your actual code (and say which Sage version) for
us to help debug that!

John

[Irene]

p=3700001

Fp=GF(p)

E=EllipticCurve([Fp(3),Fp(5)])

j=E.j_invariant()

l=13#Atkin prime

n=((l-1)/2).round()

r=2# Phi_13 factorize in factors of degree 2

s=12#Psi_13 factorize in factors of degree 12

#repsq(a,n) computes a^n

def repsq(a,n):

    B = Integer(n).binary()

    C=list(B)

    k=len(B)-1

    bk=a

    i=1

    while i <= k:

        if C[i]=="1":

            bk=(bk^2)*a

        else:

            bk=bk^2

        i=i+1

    return bk

d=E.division_polynomial(13)

Fps=GF(repsq(p,s),'a')

a=Fps.gen()

Fpr=GF(repsq(p,r),'b')

b=Fpr.gen()

FFps=PolynomialRing(Fps)

Fl=GF(l)

c=GF(2)

rts=d.roots(Fps,multiplicities=False)

Px=rts[0]

Py2=Px^3+3*Px+5

c=Fl.multiplicative_generator()

def produx(n,Qx):

    if is_odd(n):

        pro=Qx-(E.division_polynomial(n-1,(Qx,1),two_torsion_multiplicity=1)*E.division_polynomial(n+1,(Qx,1),two_torsion_multiplicity=1)* (Qx^3+3*Qx+5))/((E.division_polynomial(n,(Qx,1),two_torsion_multiplicity=1)^2))

    else:

        pro=Qx-(E.division_polynomial(n-1,(Qx,1),two_torsion_multiplicity=1)*E.division_polynomial(n+1,(Qx,1),two_torsion_multiplicity=1))/((Qx^3+3*Qx+5)*E.division_polynomial(n,(Qx,1),two_torsion_multiplicity=1)^2)

    return pro

Ep=(X-produx(2,Px))*(X-produx(4,Px))*(X-produx(8,Px))*(X-produx(3,Px))*(X-produx(6,Px))*(X-produx(12,Px))

bb=b.minpoly().roots(Fps)[0][0]

i=Fpr.hom([bb],Fps)

j=i.section()

PolynomialRing(Fpr,'x')([j(c) for c in Ep.coeffs()]) 

That was the code, and the version is 5.11. Maybe the problem is because the version is too old, but I was using another version and I got many problems and right now I don't have another option.

[Peter Bruin]

This works for me in Sage 5.13 (I don't have an older version installed), after replacing the definition of FFps by

FFps.<X>=PolynomialRing(Fps)  # the .<X> was missing

However, without the .<X> the error I got was different from yours (TypeError: You must specify the names of the variables.)


Op donderdag 17 april 2014 17:05:20 UTC+1 schreef Irene:

[John Cremona]

Your code works ok with Sage 6.1.1 (apart from a small slip in the
code you posted: the line
FFps=PolynomialRing(Fps)
should say
FFps<X>=PolynomialRing(Fps)

and the result is

x^6 + (973912*b + 2535329)*x^5 + (416282*b + 3608920)*x^4 + (686636*b
+ 908282)*x^3 + (2100014*b + 2063451)*x^2 + (2563113*b + 751714)*x +
2687623*b + 1658379

[Irene]

I got it in another version! Thank you very much!