ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 18 Apr 2021 12:48:15 +0200Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problemhttps://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/There seems to be a unnecessary performance problem with constructing large extension fields:
sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: GF(p^2)
This hangs trying to factor the 891-bit integer $p^2 - 1$, which is longer than the longest solved RSA Challenge number. (As it happens, the hard part of this factorization is a 675-bit integer which is still impractical.)
It is not unreasonable that constructing the extension field requires knowing the factorization of the multiplicative order. (You can get around this by constructing it with a specific modulus, but then many operations, e.g. taking roots, require this factorization anyway.)
However, we know that $p^2 - 1$ splits as $(p-1)(p+1)$, and factoring those may be much more feasible:
sage: factor(p-1)
2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
sage: factor(p+1)
2 * 313 * 751 * 2003 * 2671 * 738231097 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299
(this takes less than a second on my desktop).
In general, computing the multiplicative order of an extension field should take advantage of the factorization of $p^k - 1$ as a polynomial. There might also be other cases where we know the factorization by construction, and should be able to provide it.dairaSun, 18 Apr 2021 12:48:15 +0200https://ask.sagemath.org/question/56710/Extension field over p-adics: how to write an element in the standard basis?https://ask.sagemath.org/question/56008/extension-field-over-p-adics-how-to-write-an-element-in-the-standard-basis/Suppose we have an extension field $\mathbb{Q}_2(w)$, where $w$ is a root of $f(x) = x^3 + 4x^2 + 2$. By default, Sage represents $w^3$ as $w^3 + O(w^d)$, where $d$ is the precision. How do I get Sage to print $w^3$ out as a linear combination of the standard basis, i.e., as $-4w^2 - 2$ (with -4 and -2 written as they would be in $\mathbb{Q}_2$)?caelanritterWed, 03 Mar 2021 20:50:03 +0100https://ask.sagemath.org/question/56008/Efficiently computing tower fields for pairingshttps://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/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?zahllosFri, 24 Jan 2020 02:02:27 +0100https://ask.sagemath.org/question/49663/parametric solution for a system of polynomial equationshttps://ask.sagemath.org/question/46043/parametric-solution-for-a-system-of-polynomial-equations/I have the following system of equations,
1+x+y+z==0, 1+xy+yz+xz==0
which I want to solve in the extension field of GF(2) for example. There is a parametric solution of these equations in terms of the parameter s as x=1+s, y=1+$\omega$ s, z=1+$\omega^2$s where $s$ is the parameter and $\omega^2+\omega+1=0$. How can I modify the following for Sage to be able to output parametric solutions like this one?
R.<x,y,z> = PolynomialRing(GF(4))
I = R.ideal([1 + x + y + z, 1 + x*y + y*z + x*z])
I.variety()arpitSun, 07 Apr 2019 22:40:40 +0200https://ask.sagemath.org/question/46043/i want to define field \mathbb Q (\sqrt 2,\sqrt 3) what command should use?https://ask.sagemath.org/question/43983/i-want-to-define-field-mathbb-q-sqrt-2sqrt-3-what-command-should-use/ i tried doing it by spiliting field comand but it is not working ,if possible let me know about spliting field commands alsoSunil pasupulatiFri, 19 Oct 2018 09:23:40 +0200https://ask.sagemath.org/question/43983/Declaring symbols in a Fieldhttps://ask.sagemath.org/question/45146/declaring-symbols-in-a-field/Lets define a field F.<t> = GF(2^n)
now i want to define a variable points of the form x1+x2*t+...+xn*t^(n-1) and then solving equation with this by comparing coefficients of t^i.
Now I am defining R= PolynomialRing(ZZ,'x',n)
c=R.gens()
R=R.quotient_ring([c[i]^2-c[i] for i in range(0,n)])
then i get n variables but if
I write x= sum(c[i]*t^i for i in (0,n)) I get the parent of x is R. and I am unable to collect the coefficients of t^i. after defining y and z in the same way. if I do X=x+y+z then I am getting the value as a Ring element with monomials in xi's and coefficients in F as X in a Ring element.
Can anyone suggest any way to get the results as f1+f2*t+f3*t^2+...+fn*t^(n-1) and then collect fi's where fi's are functions in the variables xi's.
suppose I want to solve for X,Y in GF(2^3) with X^2Y^2= X^2+(1+t)Y^2
sage: F.<t>=GF(2^3)
sage: R.<a1,a2,b1,b2,c1,c2>= PolynomialRing(ZZ)
sage: R.<a1,a2,b1,b2,c1,c2>= R.quotient_ring([a1^2-a1,a2^2-a2,b1^2-b1,b2^2-b2,c1^2-c1,c2^2-c2])
sage: X=R(a1)+R(b1)t+R(c1)t^2
sage: Y=R(a2)+R(b2)t+R(c2)t^2
sage: X^2*Y^2
Now i want to store this output as A+Bt+Ct^2(how to do this? )
then I do:
sage: X^2+(1+t)*Y^2
and I want to store this as E+Ft+Gt^2(is it possible to do?)
finally I want to solve for ai's and bi's from the eqns A=E, B=F,C=G,ai^2=ai,bi^2=bi,ci^2=ci for i=1,2BishwajitCWed, 23 Jan 2019 15:12:45 +0100https://ask.sagemath.org/question/45146/Reduction In Quotient Rings (x^2 - x = 0)https://ask.sagemath.org/question/44514/reduction-in-quotient-rings-x2-x-0/Hi,
Thank you for taking the time to read this, it is very much appreciated.
My question concerns how to ensure that a polynomial within a quotient ring has the following property:
(x^2)k = 0
whereby x is any variable in the quotient ring and k is a positive integer.
This is the way I tried to go about the situation: I created a polynomial ring
P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
Since I am not working within a quotient ring, x^2 (or any of the other three variables) does not 'become' 0. Since I would like the property of x^2 = 0, I decided to create a quotient ring with some field equations:
Q = P.quotient_ring(ideal([var**q - var for var in P.gens()]))
whereby `q = P.base_ring.order()` .
However, when I then created the following polynomial, its parent was still P, so I changed its ring:
f1 = y*z + y*w + w^2
f1 = f1.change_ring(Q)
However, when I print f1, it, w^2 is still w^2 and has not reduced down to 0. I was wondering if I am missing something, please? This gets annoying because I am going to be working with Macaulay Matrices and hence, it is essential that I work within a quotient ring. Maybe I am missing some mathematics since this is all very new to me...
This is my sage input:
sage: P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
sage: q = P.base_ring().order()
sage: Q = P.quotient_ring(ideal([var**q - var for var in P.gens()]))
sage: f1 = y*z + y*w + w^2
sage: f1
y*z + y*w + w^2
sage: f1 = f1.change_ring(Q)
sage: f1
y*z + y*w + w^2
How would go about to ensure that w^2 = 0? I've already tried adding the original polynomial to the field equations when creating the quotient ring and changing its ring afterwards, like so:
sage: P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
sage: q = P.base_ring().order()
sage: f1 = y*z + y*w + w^2
sage: Q = P.quotient_ring(ideal([f1] + [var**q - var for var in P.gens()]))
sage: f1 = f1.change_ring(Q)
sage: f1
y*z + y*w + w^2
But as you can see, nothing happened...
Thank you!JoaoDDuarteFri, 30 Nov 2018 02:06:30 +0100https://ask.sagemath.org/question/44514/Minimal polynomial in tower of finite fields?https://ask.sagemath.org/question/43349/minimal-polynomial-in-tower-of-finite-fields/ I have two extension field $E=K(d)$ and $K=F(a)$ where $F=GF(p)$ for a prime $p$. How can I compute the minimal polynomial of $d$ over $F$.
There is a command "absolute_minpoly" that works for number fields and not extension fields of finite fields. I want a command like that. RuhollaSun, 12 Aug 2018 02:18:49 +0200https://ask.sagemath.org/question/43349/Correct way to construct a field with i adjoined?https://ask.sagemath.org/question/42420/correct-way-to-construct-a-field-with-i-adjoined/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.zahllosThu, 24 May 2018 15:52:10 +0200https://ask.sagemath.org/question/42420/Element to sequence in field extensionhttps://ask.sagemath.org/question/42039/element-to-sequence-in-field-extension/I have constructed a big prime field:
p = 68235916425158872634653027
F = GF(p)
And then I make two extension fields
E1 = GF(p^2)
E2 = GF(p^6)
It is obvious that `E2` is a field extension of `E1`.
Now how can I express the element in `E2` with the basis in `E1`.FanxuejunMon, 16 Apr 2018 09:02:26 +0200https://ask.sagemath.org/question/42039/Normal base of a finite extersion fieldhttps://ask.sagemath.org/question/41281/normal-base-of-a-finite-extersion-field/ Hi all,
any finite extension (say degree *n*) of a field *K* may be considered as vector space over *K*. In particular, the roots of any irreducible polynomial *f* of degree *n* over a finite field *K* constitute a basis of this vector space.
Does SageMath provide a routine to construct the vector space for given *K* and *f*?
Such a vector space seems to be used internally when constructing *Kn=GF(K.order()^n,'a',modulus=f)*. If so then the question becomes: Is this vector space open to the public? And how can I use it?
Thanks in advance
Wolfgang JansenwjansenTue, 27 Feb 2018 16:04:13 +0100https://ask.sagemath.org/question/41281/How to get the imaginary and real parts in quadratic extension?https://ask.sagemath.org/question/40778/how-to-get-the-imaginary-and-real-parts-in-quadratic-extension/I have the following code segment in Sage:
proof.arithmetic(False)
p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
assert p.is_prime()
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
v = 9207905618485976447392495823891126491742950552335608949038426615382964807887894797411491716107572732408369786142697750332311947639207321056540404444033540648125838904594907601875471637980859284582852367748448663333866077035709*j + 4651155546510811048846770550870646667630430517849502373785869664283801023087435645046977319664381880355511529496538038596466138807253669785341264293301567029718659171475744580349901553036469330686320047828171225710153655171014
Now, if I try to get the real and imaginary parts with `v.real()` and `v.imag()`, I get errors that those methods do not exist. I guess because `v` has some different structure and type. How can I get the imaginary and real parts here?ninhoFri, 26 Jan 2018 11:26:15 +0100https://ask.sagemath.org/question/40778/Quadratic extension field of a finite fieldhttps://ask.sagemath.org/question/40568/quadratic-extension-field-of-a-finite-field/ I want to create a quadratic extension of a finite field via `x^2 + 1`, and for that purpose I have the following Sage code:
proof.arithmetic(False)
# Parameters
f = 1
lA = 2
lB = 3
eA = 372
eB = 239
# Define the prime p
p = f*lA**eA*lB**eB-1
assert p.is_prime()
# Prime field of order p
Fp = GF(p)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<i> = Fp.extension(x^2+1)
Though, the above code throws a rather cryptic error `UnboundLocalError: local variable 'E' referenced before assignment`. Any ideas how to solve the problem and create a quadratic extension field.ninhoThu, 11 Jan 2018 16:22:01 +0100https://ask.sagemath.org/question/40568/Multiplication of elements of tower fieldshttps://ask.sagemath.org/question/39835/multiplication-of-elements-of-tower-fields/Let
p=13
R = GF(p)
_.<v> = PolynomialRing(R)
R4.<v> = R.extension(v^4 - 2, 'v')
_.<w> = PolynomialRing(R4)
R16.<w> = R4.extension(w^4-v, 'w')
I need to compute
f1 = R16(1)
for i in range(34):
A=R4.random_element() #in my case, this is not random, its derived by an function
f1 = f1^2*A #this is not the whole code, but it displayes the problem
This element stays allways in R4. But the result i expect, is an element of R16.
So: How can I tell sage to use the R16 multiplication instead? I need a full degree 15 polynomial. If it is possible, in one variable (w, since w^4=v).
Furthermore: How can I tell Sage to print any coefficient in Hex?ShalecWed, 29 Nov 2017 09:31:10 +0100https://ask.sagemath.org/question/39835/Monkey-patching PARI callshttps://ask.sagemath.org/question/39807/monkey-patching-pari-calls/I'm currently trying to implement some number field computations on a very particular number field (specifically, $K = \mathbb{Q}(\zeta_{n-1},n^{1/(n-1)})$). The code I've written so far has some bottlenecks that profiling via %prun has identified, namely:
1. `{method '_nf_rnfeq' of 'sage.libs.cypari2.gen.gen' objects}`, which seems to compute the minimal polynomial of $K$ (currently I'm defining $K$ via `F.<u> = CyclotomicField(n-1)`, and then `K.<a> = F.extension(x^(n-1) - n)`, so $K$ is a relative extension. `_nf_rnfeq` seems to compute the absolute minimal polynomial of a given relative extension (via PARI).
2. `{method 'discriminant' of 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint' objects}`, which appears to just be the polynomial discriminant computation.
Assume I've done analysis by hand gives me a much faster computation of the absolute minimal polynomial for this particular number field. I'd then want a version of `_nf_rnfeq` that:
1. Checks if it's being called on my special case, where better algorithms exist. If so, run that.
2. Otherwise, run the traditional algorithm.
Of course, I'd prefer to make this modification without modifying the source code, as that seems to be an especially ugly solution.
One way to implement this is to change is by modifying the relevant method at run-time, via a technique known as "Monkey-Patching" (see [here](https://stackoverflow.com/questions/47503061/replacing-specific-function-calls/47503146#47503146)).
The issue I'm having now is that attempting to monkey-patch the PARI call gives me the error:
`TypeError: can't set attributes of built-in/extension type 'sage.libs.cypari2.gen.gen'`
The code I'm using (in the first cell of my IPython notebook) is below:
import sage.libs.cypari2.gen
orig_nf_rnfeq = sage.libs.cypari2.gen.gen._nf_rnfeq
def _nf_rnfeq(*args, **kwargs):
print("Rnfeq works!")
return orig_nf_rnfeq(*args, **kwargs)
sage.libs.cypari2.gen.gen._nf_rnfeq = _nf_rnfeqorangejakeMon, 27 Nov 2017 00:37:25 +0100https://ask.sagemath.org/question/39807/field extension not implementedhttps://ask.sagemath.org/question/37467/field-extension-not-implemented/I'm trying to construct some field extenstions of GF(p), this is what I have
p=5
F=GF(p)
R1.<x> = F['x']
F1.<alpha1> = F.extension(x^p - x - 1)
R2.<x> = F1['x']
F2.<alpha2> = F1.extension(x^p - x - alpha1^(p-1))
R3.<x> = F2['x']
F3.<alpha3> = F2.extension(x^p - x - (alpha1*alpha2)^(p-1))
R4.<x> = F3['x']
F4.<alpha4> = F3.extension(x^p - x - (alpha1*alpha2*alpha3)^(p-1))
It creates F3 like it should but it doesn't create F4. I get a NotImplementedError... What did I do wrong?gelatine1Sat, 29 Apr 2017 19:39:32 +0200https://ask.sagemath.org/question/37467/