zahllos's profile - activity

I don't think it will be instructive, for learning purposes, to use a prime that big and plot it (assuming this is what you want to do) and I suspect the problem is the size of the field.

Here's the curve I use as an example, with cofactor 1, for "ecc" curves that are like NIST ones.

  E=EllipticCurve(GF(17),[3,5])
  E.order()
  E.is_supersingular()
  E.plot()

As you can see, it's a prime order group (so cofactor 1) and not supersingular, although it is obviously way too small for real world use. The plot however is nicer. Can't upload it to show you, but you can reproduce from this.

This is relatively easy to do using the documentation, see the basic algebra page on differentation: https://doc.sagemath.org/html/en/tuto....

One of my favourite problems is to show that:

$$\int \ln(x) dx = x\ln(x) - x + C$$

In sagemath this can be done as follows:

u = var('u')
f(u) = ln(u)
f
u |--> log(u)
integral(f(u),u)
u*log(u) - u

You should be able to adapt this example to your case.

@rburing Thanks. Unfortunately, this is hard to translate to sage, because $F_p^{12}[w]$ for example is defined by F12.<w> = ... and I can't use w on the RHS of that expression (nor can I use v, because that's the polynomial ring in the intermediate extension field $F_p^6$ and my hypothesis is that sage just can't cope with this level of towering, so I was hoping simply not to use anything in F6or K6 and associated terms. Have edited my question with what I think is the correct derivation based on your comment.

Hello all,

I'm messing around trying to create a toy bls12-381 implementation. In order to create the required tower of fields, I'm doing this:

reset()
F = GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab)
g1curve = EllipticCurve(F, [0,4])

K2.<x> = PolynomialRing(F)
F2.<u> = F.extension(x^2+1)
K6.<y> = PolynomialRing(F2)
F6.<v> = F2.extension(y^3 - (u+1))
K12.<z> = PolynomialRing(F6)
F12.<w> = F6.extension(z^2 - v)

Such towering is described in multiple places, e.g, Optimal Ate Pairings at the 128-bit Security level (hxxps://hal.archives-ouvertes.fr/hal-01620848/document), Implementing Pairings at the 192-bit Security Level (hxxps://eprint.iacr.org/2012/232.pdf) and Faster Subgroup Checks for BLS12-381 (hxxps://pdfs.semanticscholar.org/f413/bf4f22f682043616261e463abd0fd9fdcc54.pdf).

I am implementing example code given in Guide to Pairing Based Cryptography (hxxps://www.crcpress.com/Guide-to-Pairing-Based-Cryptography/Mrabet-Joye/p/book/9781498729505) that relies on the w $F_p^{12}$ element defined in the above extension tower. However, the last step, of this code appears to take an inordinate amount of time (yet to see it complete).

Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:

F12.<w> = F6.extension(x^2 - v)

but this fails with a type conversion error.

I've tried to search this site to find out how I might generate F12 directly from F2 as I've seen comments indicating that performance of towers of field extensions is... not great and this is also my experience. I have tried to define Fp12 entirely in terms of x from the first PolynomialRing, but I haven't found a way to try to extend directly from Fp2 to Fp12 yet (I only need Fp12 and its sextic twist. I have seen how to create a homomorphism to embed one elements in another field, but I haven't yet tried to use this to simplify. Can this be done? Is there a way to make this performant?

Apologies for the broken links, I'm not allowed to include links yet.

Update: Following @rburing's comment, I noted that the tower field is as follows:

$$\mathbb{F}_{p^2} = \mathbb{F}_p[a]/(a^2+1) $$ $$\mathbb{F}_{p^6} = \mathbb{F}_{p^2}[b]/(b^3-(a+1)) $$ $$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^{12}}[c]/(c^2-b) $$

From this we have that $b^3 = a+1$ and $c^2 = b$, hence $c$ alone being a sixth root of $a+1$. If $c$ is a sixth root, then $c^2$ is a third root, so $c^2 = (a+1)^(1/3)$ and we can see also that $b=a+1$. To give sage some help, we cube both terms. I think therefore that:

$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$

which can be represented two ways in sage:

F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)

Sage dislikes the latter ("finite field in u is not alphanumeric") but the former at least constructs and object in a second or two, and gives:

F12
Univariate Quotient Polynomial Ring in w over Finite Field in u of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787^2 with modulus w^6 + 6*w^4 + 12*w^2 + 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786*u + 7

My question is, is this the correct object?

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!

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.