ASKSAGE: Sage Q&A Forum - Latest question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 03 Mar 2020 16:49:52 -0600given an euclidean domain get the euclidean functionhttps://ask.sagemath.org/question/50151/given-an-euclidean-domain-get-the-euclidean-function/ I am writing a polymorphic function that implements an algorithm that should work in all euclidean domains. My function should work in all euclidean domains, even ones that have not been implemented yet. My algorithm uses the euclidean function. How do I polymorphically get the canonical euclidean function for my particular domain?Paul ElliottTue, 03 Mar 2020 16:49:52 -0600https://ask.sagemath.org/question/50151/Extended Euclidean Algorithm for Univariate Polynomials with Coefficients in a Finite Fieldhttps://ask.sagemath.org/question/44376/extended-euclidean-algorithm-for-univariate-polynomials-with-coefficients-in-a-finite-field/Consider the following snippet, intended to compute the extended euclidean algorithm for polynomials in $F_q[x]$.
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
GFX.<x> = GF(5)[x]
g = x^3 + 2*x^2 - x - 2
h = x - 2
r,s,t = extended_euclides(f,g)
print("The GCD of {} and {} is {}".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == gcd(g,h), "The gcd should be {}!".format(gcd(g,h))
assert r == s*g + t*h, "The cofactors are wrong!"
Executing this snippet produces the following output:
The GCD of x^3 + 2*x^2 + 4*x + 3 and x + 3 is 3*x + 1
Its Bézout coefficients are 2*x + 4 and 3*x^2 + 4
Error in lines 45-45
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError: The gcd should be 1!
That is, my code disagrees with sagemath's `gcd` function, and I think sagemath's result is correct; `g(2)!=0`, so `g` and `h` should not have common factors.
Why is mine wrong?JsevillamolThu, 22 Nov 2018 03:46:07 -0600https://ask.sagemath.org/question/44376/Gaussians as Euclidean Domainhttps://ask.sagemath.org/question/44271/gaussians-as-euclidean-domain/Follow up to [a comment](https://ask.sagemath.org/question/44251/making-a-quotient-with-gaussian-elements/?comment=44265#post-id-44265) by @nbruin in a previous question:
> One reason that Euclidean division isn't available by default on ZI is because as far as sage is concerned, it's a quadratic ring, and those generally are not euclidean rings. There are some quadratic rings that are, but most of them are only euclidean with rather obscure euclidean norms. The fact that Z[i] is euclidean with the "standard" norm is really quite anomalous among quadratic rings.
> If you're interested in studying euclidean rings you probably should write some utility functions yourself to help you with it (or search if such utilities are already available). You could even consider writing a new ring subclass for Euclidean rings. To illustrate that sage doesn't know that ZI is a euclidean domain:
sage: ZI in EuclideanDomains()
False
context: `ZI = QuadraticField(-1, 'I').ring_of_integers()`
My question is: Is there a built in way in SageMath to work with Gaussian integers as an Euclidean domain?JsevillamolTue, 13 Nov 2018 10:48:43 -0600https://ask.sagemath.org/question/44271/