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.Thu, 28 Sep 2023 09:59:24 +0200xgcd for several argumentshttps://ask.sagemath.org/question/73642/xgcd-for-several-arguments/SageMath has a built-in method for performing the extended Euclidean algorithm for two numbers (or polynomials), called xgcd. The algorithm also works for several arguments, by recursion. One can implement this easily with a SageMath helper function, but I was wondering: does SageMath have a built-in extension of xgcd to several arguments?
Martin-BrThu, 28 Sep 2023 09:59:24 +0200https://ask.sagemath.org/question/73642/ExtGCD in Finite Fieldshttps://ask.sagemath.org/question/61929/extgcd-in-finite-fields/I want to implement Extended GCD with SageMath so that the internal can be printed. The below is a modification of [this](https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code). This should be straightforward, however, I might miss something;
def extended_euclides(a,b):
s = 0; old_s = 1
t = 1; old_t = 0
r = b; old_r = a
while r != 0:
quotient,rem = old_r.quo_rem(r)
old_r, r = r, old_r - quotient*r
old_s, s = s, old_s - quotient*s
old_t, t = t, old_t - quotient*t
return [old_r, old_s, old_t]
K.<a> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
print(K)
print("m = ", K.modulus())
g = a^7 + a^5 + a^4 + a
h = a^4 + a^2 + 1
r,s,t = extended_euclides(g,h)
print("The GCD of \n \t [ {} ] and \n \t [ {} ] is \n\t [ {} ]".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == g.gcd(h), "The gcd should be {}!".format(g.gcd(h))
assert r == s*g + t*h, "The cofactors are wrong!"
In the end, I've got the assertion error `AssertionError: The gcd should be 1!`
Any idea to solve this?klxTue, 12 Apr 2022 11:02:29 +0200https://ask.sagemath.org/question/61929/How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field?https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/
Hi, as the title says I`m trying to define a function that finds the gcd of two polynomial without using the pre-established function gcd. I've tried everything I thought it would work:
First, I tried to use the Euclidan Algorithm, for that you need to divide the polynomials. Knowing so, I tried to find the degrees of the different polynomials to divide in consequence of the degrees (which gave me error). Then I tried it without the degree part and it didn't work at all since % couldn't be used as a divisor of polynomials.
def GCD(field, f, g):
R.<x> = PolynomialRing(field, 'x')
x.parent()
a = f.degree()
b = g.degree()
if a>b:
while g != 0:
r = g
g = f%g
else:
while f != 0:
r = g
f = g%f
return r
Shortly after I tried to factor both of the polynomial and make the función return the part that repeated. But I rapidly saw my hopes decay when I realized I have not a single clue in how to do so (even though I've done some research I couldn't find the answer).
def mcd(field, f, g):
R.<x> = PolynomialRing(field)
a = f.factor()
b = g.factor()
And this was the last code I wrote before asking for some enlightening:
def MCD(Field,PolynomialA, PolinomialB):
R.<x> = PolynomialRing(Field, 'x')
a = PolynomialA
b = PolynomialB
c = 1
while c != 0:
c = a%b
a = b
b = c
return aEscolopendraWed, 17 Nov 2021 00:58:06 +0100https://ask.sagemath.org/question/59777/finding inverse of en element wiht Ext-GCD fails due to defining polynomial converts zero in functionhttps://ask.sagemath.org/question/53183/finding-inverse-of-en-element-wiht-ext-gcd-fails-due-to-defining-polynomial-converts-zero-in-function/ I'm trying to implement a fast Ext-GCD to find the inverse of an element in the finite field $GF(2^8)$ of AES.
def egcd(a, b):
print(a)
print(b)
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b/a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
#Base field
R.<y> = PolynomialRing(GF(2), 'y')
#Defining polynomial
G = y^8+y^4+y^3+y+1
#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()
print(egcd(x^8+x^4+x^3+x+1,x^7+x+1))
When the $x^8+x^4+x^3+x+1$ is sent to this function it is converted to zero, so the `print(a)` prints zero.
Is there a way to protect the variable from converting to zero so that this function can work as intended?
klxTue, 25 Aug 2020 22:44:40 +0200https://ask.sagemath.org/question/53183/What are the specific steps to find XGCD on the polynomial ring $Z_8[x]$https://ask.sagemath.org/question/50389/what-are-the-specific-steps-to-find-xgcd-on-the-polynomial-ring-z_8x/Division cannot be performed on rings with zero divisors.
There are zero divisors in Z8[x], how do we calculate the value of XGCD in a polynomial ring Z8[x] ?wormFri, 27 Mar 2020 11:05:24 +0100https://ask.sagemath.org/question/50389/Compute xgcd over Gaussian integershttps://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/As you can see below, I can create the ring of [Gaussian integers](https://en.wikipedia.org/wiki/Gaussian_integer) and compute the greatest common divisor of two elements:
sage: ZZ[I]
Gaussian Integers in Number Field in I with defining polynomial x^2 + 1
sage: F = ZZ[I].random_element()
sage: G = ZZ[I].random_element()
sage: F
-I - 4
sage: G
-I + 1
sage: gcd(F, G)
1
However, when I try to find $u, v \in \mathbf{Z}[i]$ such that $u\cdot F + v\cdot G = 1$ in $\mathbf{Z}[i]$ (that is, to run the extended GCD), I get the following error:
> sage: xgcd(F, G)
>. . .
> TypeError: Unable to coerce -I - 4 to an integer
Do you know how I can find such $u$ and $v$?Hilder Vitor Lima PereiraWed, 13 Feb 2019 10:25:35 +0100https://ask.sagemath.org/question/45441/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 10:46:07 +0100https://ask.sagemath.org/question/44376/