Ask Your Question
0

Correct way to construct a field with i adjoined?

asked 2018-05-24 08:52:10 -0500

zahllos gravatar image

Hello,

I'm an undergrad maths student looking to understand how I successfully adjoin elements to a finite field in sagemath, to explore some of my university topics.

I can construct a base field, for example:

B = GF(2**3-1)

and I can construct an extension to this by adjoining I, which is equivalent to using the minimum polynomial x^2+1 like so:

reset('i') # make sure we haven't clobbered the imaginary constant
E = B[i]

This does what I want (I think), creating a field E that is an extension of B. We can even list the elements:

[e for e in enumerate(E)]

and this looks correct. However, things get messy when I try to use a larger field, for example:

C = GF(2**127-1)
F = C[i]

This gives the error:

I already exists with incompatible valence

I haven't tried to redefine i at all, so far as I can tell, so, my questions are:

  1. How do I correctly extend a given finite field ?
  2. Following on from this, I tried the following:

    A = GF(2**3-1)
    B = A[i]
    C = A.extension(x^2+1, 'i')
    B==C
    

    So it appears I can't successfully adjoin 'i' using a minimum irr poly either. Printing B and C give:

    sage: B
    Finite Field in I of size 7^2
    sage: C
    Finite Field in i of size 7^2
    

    which would explain why they aren't equal... except i and I should be equal.

    In short, I would like to construct the quotient field PRIME BASE FIELD[x]/x^2-1 and have the arbitrary x treated as complex values ("adjoining sqrt(-1)") but I'm unclear from sage's documentation on how to achieve this.

  3. I see the notation

      R.<x> = GF(blah)
    

    quite a lot. Can someone please explain it? I can't find anything in the documentation that might help me understand what this is and why it is necessary.

You can assume I understand most of an undergraduate galois theory course and have a basic understanding of algebraic number theory - what I don't understand is how this maps into sage.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-05-24 20:14:58 -0500

dan_fulea gravatar image

The following code initializes a finite field $\Bbb F_p(j)$, for the prime $p= 2^{127}-1$, so that $j$ satisfies $j^2=-1$.

p = 2**127-1
F = GF(p)
R.<x> = PolynomialRing(F)
K.<j> = GF( p^2, modulus=x^2+1 )

The code is rather simple, but there are many tacitly done constructive details. Let us go step by step. After we define $p$, a prime, we initialize the field $F=\Bbb F_p$ woith $p$ elements. There is no need to specifiy any generator for this finite field, it is a standard construction, no chance for a choice.

Then we define the polynomial ring over $F$. This works also via F[] when we are in big hurry, but here i used the full name for the constructor. The polynomial ring over $F$ needs a transcendental generator, a name for it, so we give one, above it is x. In the next line, we want to introduce a field isomorphic to $\Bbb F_{p^2}$. Again, we need some care to name the generator, and we even want to prescribe it, its minimal polynomial, in sage terminology - its modulus. This is done using the variable x with the "right parent".

Sometimes, all details can be collected in a dialog with the interpreter. Here, i try to address aspects from the posted questions.

sage: p.is_prime()
True
sage: F
Finite Field of size 170141183460469231731687303715884105727
sage: R
Univariate Polynomial Ring in x over Finite Field of size 170141183460469231731687303715884105727 (using NTL)
sage: x
x
sage: x.parent()
Univariate Polynomial Ring in x over Finite Field of size 170141183460469231731687303715884105727 (using NTL)
sage: x == R.gens()[0]
True
sage: K
Finite Field in j of size 170141183460469231731687303715884105727^2
sage: K.modulus()
x^2 + 1
sage: K.modulus() == x^2+1
True
sage: j.minpoly()
x^2 + 1
sage: j^2
170141183460469231731687303715884105726
sage: K.order() == p^2
True

I always avoid "constructors" that do not have "names". For instance, yes, R.<x> = F[] is also a possible way to instantiate the polynoial ring over F, but the "correct", documented way is by using PolynomialRing. Moreovver, ?PolynomialRing gives documentation and examples for the class, for its constructor.

And also, i was avoiding i all the time.

edit flag offensive delete link more

Comments

I know it has taken me a little while to reply, but thanks a lot! That clears things up really nicely! It seems so simple and yet much harder than magma code I have seen (I don't have access to magma). Anyway, thanks again!

zahllos gravatar imagezahllos ( 2018-06-13 19:46:19 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-05-24 08:52:10 -0500

Seen: 20 times

Last updated: May 24