²²⁸ views

Kernel: SageMath 7.5

Enteros, congruencias, polinomios y cuerpos finitos

Enteros

Los enteros en SAGE se escriben normalmente (en base 10):

In [2]:

a = 2432902008176640001
a

Out[2]:

2432902008176640001

Algunas funciones que hemos visto en clase sobre los enteros:

In [ ]:

In [3]:

factor(a)

Out[3]:

20639383 * 117876683047

In [4]:

divisors(a)

Out[4]:

[1, 20639383, 117876683047, 2432902008176640001]

In [5]:

euler_phi(a)

Out[5]:

2432901890279317572

In [6]:

gcd(38756812365,29487639876)

Out[6]:

3

In [7]:

d,a,b=xgcd(321124,141412432)
a,b,d

Out[7]:

(9387745, -21318, 4)

In [8]:

321124*a+141412432*b==d

Out[8]:

True

El Teorema Chino del resto para los enteros: $\begin{aligned} x&\equiv 4 \pmod 5\\ x&\equiv 0 \pmod 9\\ x&\equiv 1 \pmod 2\\ x&\equiv 5 \pmod{19}\\ \end{aligned}$

In [9]:

s=crt([4,0,1,5], [5,9,2,19])
s

Out[9]:

1449

Obsérvese que SAGE implementa el Teorema Chino del Resto generalizado, incluyendo los casos en que los módulos no son coprimos pero existe solución:

In [10]:

# No existe solución:
s=crt([4,0,1,5], [5,12,2,19])

Out[10]:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-10-7da7130c144e> in <module>()
      1 # No existe solución:
----> 2 s=crt([Integer(4),Integer(0),Integer(1),Integer(5)], [Integer(5),Integer(12),Integer(2),Integer(19)])

/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/arith/misc.pyc in crt(a, b, m, n)
   2950     """
   2951     if isinstance(a, list):
-> 2952         return CRT_list(a, b)
   2953     if isinstance(a, (int, long)):
   2954         a = Integer(a) # otherwise we get an error at (b-a).quo_rem(g)
/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/arith/misc.pyc in CRT_list(v, moduli)
   3033     m = moduli[0]
   3034     for i in range(1, len(v)):
-> 3035         x = CRT(x,v[i],m,moduli[i])
   3036         m = lcm(m,moduli[i])
   3037     return x%m
/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/arith/misc.pyc in crt(a, b, m, n)
   2956     q, r = (b - a).quo_rem(g)
   2957     if r != 0:
-> 2958         raise ValueError("No solution to crt problem since gcd(%s,%s) does not divide %s-%s" % (m, n, a, b))
   2959     return (a + q*alpha*m) % lcm(m, n)
   2960 
ValueError: No solution to crt problem since gcd(60,2) does not divide 24-1

In [11]:

# Sí existe solución:
s=crt([4,3,1,5], [5,12,2,19])
s

Out[11]:

879

Algunas otras funciones que usaremos pronto:

In [12]:

a = 9387745

In [13]:

a.is_prime_power()

Out[13]:

False

In [14]:

a.is_prime()

Out[14]:

False

In [15]:

a.next_prime()

Out[15]:

9387773

Se pueden escribir enteros en otras bases, usando el anillo de los enteros (ZZ).

In [16]:

a = ZZ('110',2 ) # Un entero en base 2
a

Out[16]:

6

In [17]:

a.binary() # como cadena de texto

Out[17]:

'110'

In [18]:

a.bits() # Como ceros y unos, el menos significativo a la izquierda!!!

Out[18]:

[0, 1, 1]

In [19]:

b = ZZ('DEAD', 16) # Un entero en base 16
b

Out[19]:

57005

In [20]:

b.digits(base=16) # Los dígitos de b en base 16

Out[20]:

[13, 10, 14, 13]

In [21]:

c = ZZ('61342645623', 7) # Un entero en base 7
c

Out[21]:

1756141446

In [22]:

c.digits(7)

Out[22]:

[3, 2, 6, 5, 4, 6, 2, 4, 3, 1, 6]

In [23]:

d = a*b+c # no importan las operaciones, son enteros.
d.digits(base=3)

Out[23]:

[0, 2, 1, 0, 0, 1, 1, 2, 1, 0, 1, 0, 2, 0, 1, 2, 1, 1, 1, 1]

Un problema que tendremos que resolver varias veces: ¿Cuántos dígitos tiene un entero a en base b?

In [24]:

a = 295950609069496386825419193065472001
b = 3

In [25]:

log(a,3)

Out[25]:

log(295950609069496386825419193065472001)/log(3)

In [26]:

N(log(a,3))

Out[26]:

74.3442445441525

In [27]:

floor(N(log(a,3)))+1

Out[27]:

75

In [28]:

len(a.digits(base=3))

Out[28]:

75

O bien...

In [29]:

a.ndigits(3)

Out[29]:

75

## Congruencias: $\mathbb{Z}/\mathbb{Z}n$ .

Vamos ahora a definir el anillo de congruencias $\mathbb{Z}/\mathbb{Z}n$ . Empecemos por el caso $n=28$ .

In [30]:

Z28=IntegerModRing(28)

¿Cómo se distingue entre un entero y un entero módulo 28?

In [31]:

a = ZZ(19)
b = Z28(19)

In [32]:

Out[32]:

19

In [33]:

Out[33]:

19

In [34]:

parent(a)

Out[34]:

Integer Ring

In [ ]:

In [35]:

parent(b)

Out[35]:

Ring of integers modulo 28

Esta diferencia puede tener su importancia:

In [36]:

a^(2432902008176640001)

Out[36]:

---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
<ipython-input-36-cacf5ef8a786> in <module>()
----> 1 a**(Integer(2432902008176640001))

/projects/sage/sage-7.5/src/sage/rings/integer.pyx in sage.rings.integer.Integer.__pow__ (/projects/sage/sage-7.5/src/build/cythonized/sage/rings/integer.c:14196)()
   2045         cdef Integer x = PY_NEW(Integer)
   2046 
-> 2047         sig_on()
   2048         mpz_pow_ui(x.value, (<Integer>self).value, nn if nn > 0 else -nn)
   2049         sig_off()
MemoryError: failed to allocate 1292479191843840040 bytes

In [37]:

b^(2432902008176640001)

Out[37]:

19

Algunas funciones propias de las congruencias:

In [38]:

b.is_unit()

Out[38]:

True

In [39]:

c = Z28(18)

In [40]:

c.is_unit()

Out[40]:

False

In [41]:

b^(-1)

Out[41]:

3

In [42]:

3*b

Out[42]:

1

In [43]:

c^(-1)

Out[43]:

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-43-fb780ec47aa8> in <module>()
----> 1 c**(-Integer(1))

/projects/sage/sage-7.5/src/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_int.__pow__ (/projects/sage/sage-7.5/src/build/cythonized/sage/rings/finite_rings/integer_mod.c:29676)()
   2604         res = mod_pow_int(self.ivalue, long_exp, self.__modulus.int32)
   2605         if invert:
-> 2606             return ~self._new_c(res)
   2607         else:
   2608             return self._new_c(res)
/projects/sage/sage-7.5/src/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_int.__invert__ (/projects/sage/sage-7.5/src/build/cythonized/sage/rings/finite_rings/integer_mod.c:29810)()
   2622             x = self.__modulus.inverses[self.ivalue]
   2623             if x is None:
-> 2624                 raise ZeroDivisionError("Inverse does not exist.")
   2625             else:
   2626                 return x
ZeroDivisionError: Inverse does not exist.

Algunas funciones del anillo $\mathbb{Z}/\mathbb{Z}28$ .

In [44]:

Z28.multiplication_table('digits')

Out[44]:

 *  00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
  +------------------------------------------------------------------------------------
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
00 02 04 06 08 10 12 14 16 18 20 22 24 26 00 02 04 06 08 10 12 14 16 18 20 22 24 26
00 03 06 09 12 15 18 21 24 27 02 05 08 11 14 17 20 23 26 01 04 07 10 13 16 19 22 25
00 04 08 12 16 20 24 00 04 08 12 16 20 24 00 04 08 12 16 20 24 00 04 08 12 16 20 24
00 05 10 15 20 25 02 07 12 17 22 27 04 09 14 19 24 01 06 11 16 21 26 03 08 13 18 23
00 06 12 18 24 02 08 14 20 26 04 10 16 22 00 06 12 18 24 02 08 14 20 26 04 10 16 22
00 07 14 21 00 07 14 21 00 07 14 21 00 07 14 21 00 07 14 21 00 07 14 21 00 07 14 21
00 08 16 24 04 12 20 00 08 16 24 04 12 20 00 08 16 24 04 12 20 00 08 16 24 04 12 20
00 09 18 27 08 17 26 07 16 25 06 15 24 05 14 23 04 13 22 03 12 21 02 11 20 01 10 19
00 10 20 02 12 22 04 14 24 06 16 26 08 18 00 10 20 02 12 22 04 14 24 06 16 26 08 18
00 11 22 05 16 27 10 21 04 15 26 09 20 03 14 25 08 19 02 13 24 07 18 01 12 23 06 17
00 12 24 08 20 04 16 00 12 24 08 20 04 16 00 12 24 08 20 04 16 00 12 24 08 20 04 16
00 13 26 11 24 09 22 07 20 05 18 03 16 01 14 27 12 25 10 23 08 21 06 19 04 17 02 15
00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14 00 14
00 15 02 17 04 19 06 21 08 23 10 25 12 27 14 01 16 03 18 05 20 07 22 09 24 11 26 13
00 16 04 20 08 24 12 00 16 04 20 08 24 12 00 16 04 20 08 24 12 00 16 04 20 08 24 12
00 17 06 23 12 01 18 07 24 13 02 19 08 25 14 03 20 09 26 15 04 21 10 27 16 05 22 11
00 18 08 26 16 06 24 14 04 22 12 02 20 10 00 18 08 26 16 06 24 14 04 22 12 02 20 10
00 19 10 01 20 11 02 21 12 03 22 13 04 23 14 05 24 15 06 25 16 07 26 17 08 27 18 09
00 20 12 04 24 16 08 00 20 12 04 24 16 08 00 20 12 04 24 16 08 00 20 12 04 24 16 08
00 21 14 07 00 21 14 07 00 21 14 07 00 21 14 07 00 21 14 07 00 21 14 07 00 21 14 07
00 22 16 10 04 26 20 14 08 02 24 18 12 06 00 22 16 10 04 26 20 14 08 02 24 18 12 06
00 23 18 13 08 03 26 21 16 11 06 01 24 19 14 09 04 27 22 17 12 07 02 25 20 15 10 05
00 24 20 16 12 08 04 00 24 20 16 12 08 04 00 24 20 16 12 08 04 00 24 20 16 12 08 04
00 25 22 19 16 13 10 07 04 01 26 23 20 17 14 11 08 05 02 27 24 21 18 15 12 09 06 03
00 26 24 22 20 18 16 14 12 10 08 06 04 02 00 26 24 22 20 18 16 14 12 10 08 06 04 02
00 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01

In [45]:

Z28.is_field()

Out[45]:

False

In [46]:

Z28.is_integral_domain()

Out[46]:

False

In [47]:

L = Z28.list_of_elements_of_multiplicative_group()
L

Out[47]:

[1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27]

In [48]:

len(L)

Out[48]:

12

In [49]:

euler_phi(28)

Out[49]:

12

## Cuerpos finitos

### Cuerpos $\mathbb{F}_p$

In [ ]:

In [50]:

F18 = GF(18) # ja, ja

Out[50]:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-50-0b87355f379d> in <module>()
----> 1 F18 = GF(Integer(18)) # ja, ja

/projects/sage/sage-7.5/src/sage/structure/factory.pyx in sage.structure.factory.UniqueFactory.__call__ (/projects/sage/sage-7.5/src/build/cythonized/sage/structure/factory.c:1856)()
    360             False
    361         """
--> 362         key, kwds = self.create_key_and_extra_args(*args, **kwds)
    363         version = self.get_version(sage_version)
    364         return self.get_object(version, key, kwds)
/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_constructor.pyc in create_key_and_extra_args(self, order, name, modulus, names, impl, proof, check_irreducible, **kwds)
    517                         impl = 'pari_ffelt'
    518             else:
--> 519                 raise ValueError("the order of a finite field must be a prime power")
    520 
    521             # Determine modulus.
ValueError: the order of a finite field must be a prime power

In [51]:

F5 = GF(5) # GF = Galois Field

In [52]:

w = F5(3)
w^832568276435

Out[52]:

2

### Cuerpos finitos no primos: $\mathbb{F}_{p^r}$

Veamos cómo se define el cuerpo F como una extensión algebraica $\mathbb{F}_3[a]$ , donde $a$ verifica un cierto polinomio irreducible f.

In [53]:

F.<a>=GF(9) # a es el nombre de la variable algebraica

In [54]:

Out[54]:

Finite Field in a of size 3^2

In [55]:

Out[55]:

a

In [56]:

parent(a)

Out[56]:

Finite Field in a of size 3^2

In [57]:

F.polynomial()

Out[57]:

a^2 + 2*a + 2

In [62]:

a.multiplicative_order()

Out[62]:

8

In [63]:

(a^2+1)*(a^(-1))

Out[63]:

2*a + 2

In [64]:

# Cuerpos finitos con un polinomio dado; este es el ejemplo de clase
F2.<b>=GF(9, modulus=x^2+1)

In [65]:

b^2

Out[65]:

2

In [66]:

b^4 # b no es un generador del grupo cíclico:

Out[66]:

1

In [67]:

b.multiplicative_order()

Out[67]:

4

In [68]:

F2.multiplicative_generator()

Out[68]:

2*b + 2

In [69]:

(2*b+2).multiplicative_order()

Out[69]:

8

In [70]:

c = F2.multiplicative_generator()

In [71]:

c.minimal_polynomial()

Out[71]:

x^2 + 2*x + 2

In [72]:

F, F2

Out[72]:

(Finite Field in a of size 3^2, Finite Field in b of size 3^2)

In [73]:

H = Hom(F, F2)
H

Out[73]:

Set of field embeddings from Finite Field in a of size 3^2 to Finite Field in b of size 3^2

In [74]:

list(H)

Out[74]:

[Ring morphism:
   From: Finite Field in a of size 3^2
   To:   Finite Field in b of size 3^2
   Defn: a |--> 2*b + 2, Ring morphism:
   From: Finite Field in a of size 3^2
   To:   Finite Field in b of size 3^2
   Defn: a |--> b + 2]

In [75]:

phi1, phi2 = list(H)

In [76]:

phi1(1+a)

Out[76]:

2*b

In [77]:

phi2(1+a)

Out[77]:

b

In [ ]:

In [79]:

F8.<gamma> = GF(8)

In [82]:

F8.polynomial()

Out[82]:

gamma^3 + gamma + 1

In [83]:

list(F8)

Out[83]:

[0,
 gamma,
 gamma^2,
 gamma + 1,
 gamma^2 + gamma,
 gamma^2 + gamma + 1,
 gamma^2 + 1,
 1]

In [84]:

[ (a, a.multiplicative_order()) for a in list(F8) if a!= 0  ]

Out[84]:

[(gamma, 7),
 (gamma^2, 7),
 (gamma + 1, 7),
 (gamma^2 + gamma, 7),
 (gamma^2 + gamma + 1, 7),
 (gamma^2 + 1, 7),
 (1, 1)]

Anillos de polinomios

Dado un anillo $A$ , la función PolynomialRing construye un anillo de polinomios sobre $A$ . Hay que darle los nombres de la variables como antes.

In [85]:

# Anillos de polinomios F_p^r[x]
F9.<a> = GF(9)
A.<Z> = PolynomialRing(F9) # F9[Z], donde F9 usa a.

In [86]:

B.<X> = PolynomialRing(QQ) # Q[X]

In [87]:

Out[87]:

Univariate Polynomial Ring in Z over Finite Field in a of size 3^2

In [88]:

Out[88]:

Univariate Polynomial Ring in X over Rational Field

In [89]:

f = Z^12-Z^4-1
g = a*Z^5+Z^4-2*Z^3+6*Z^2+24*Z+1

In [90]:

f1 = X^12-X^4-1
g1 = X^5+X^4-2*X^3+6*X^2+24*X+1

In [91]:

parent(f), parent(f1)

Out[91]:

(Univariate Polynomial Ring in Z over Finite Field in a of size 3^2,
 Univariate Polynomial Ring in X over Rational Field)

In [92]:

# q y r serán el cociente y el resto de la división de f por g
q,r = f.quo_rem(g)

In [93]:

q,r

Out[93]:

((a + 2)*Z^7 + (a + 1)*Z^6 + Z^5 + (a + 1)*Z^4 + (a + 1)*Z^3 + (2*a + 1)*Z^2 + 2*Z + 2*a + 2,
 (a + 2)*Z^2 + Z + a)

In [94]:

q1,r1 = f1.quo_rem(g1)

In [95]:

q1, r1

Out[95]:

(X^7 - X^6 + 3*X^5 - 11*X^4 - X^3 - 16*X^2 + 9*X + 226,
 -78*X^4 + 783*X^3 - 1556*X^2 - 5433*X - 227)

In [96]:

f.factor()

Out[96]:

(Z^3 + Z^2 + 2) * (Z^3 + 2*Z^2 + 1) * (Z^3 + (a + 1)*Z^2 + a + 1) * (Z^3 + (2*a + 2)*Z^2 + 2*a + 2)

In [97]:

f1.factor()

Out[97]:

X^12 - X^4 - 1

Los dominios euclídeos tienen Bezout y TCR:

In [100]:

xgcd(f,g)

Out[100]:

(1,
 Z^4 + (a + 2)*Z^3 + Z^2 + (a + 1)*Z + 1,
 (2*a + 1)*Z^11 + a*Z^9 + (2*a + 2)*Z^8 + 2*Z^6 + (a + 2)*Z^5 + (2*a + 2)*Z^4 + a*Z^3 + Z^2 + (a + 1)*Z + 2)

In [101]:

crt([Z, Z+1], [f,g])

Out[101]:

Z^16 + (a + 2)*Z^15 + Z^14 + (a + 1)*Z^13 + Z^12 + 2*Z^8 + (2*a + 1)*Z^7 + 2*Z^6 + (2*a + 2)*Z^5 + Z^4 + (2*a + 1)*Z^3 + 2*Z^2 + 2*a*Z + 2

In [102]:

xgcd(f1,g1)

Out[102]:

(1,
 -171132414087738/4019013046526791*X^4 - 163936769743295/4019013046526791*X^3 + 698458860092315/8038026093053582*X^2 - 2083087221800055/8038026093053582*X - 8126995418103551/8038026093053582,
 171132414087738/4019013046526791*X^11 - 7195644344443/4019013046526791*X^10 + 462084947523/8038026093053582*X^9 + 126795210952/4019013046526791*X^8 - 342146501415/8038026093053582*X^7 + 1202918017873/8038026093053582*X^6 - 107503603793/8038026093053582*X^5 - 991018212595/4019013046526791*X^4 - 169878690726527/4019013046526791*X^3 - 19963095188695/8038026093053582*X^2 + 52176579399201/8038026093053582*X - 88969325049969/8038026093053582)

In [103]:

crt([X,X+1], [f1,g1])

Out[103]:

-171132414087738/4019013046526791*X^16 - 163936769743295/4019013046526791*X^15 + 698458860092315/8038026093053582*X^14 - 2083087221800055/8038026093053582*X^13 - 8126995418103551/8038026093053582*X^12 + 171132414087738/4019013046526791*X^8 + 163936769743295/4019013046526791*X^7 - 698458860092315/8038026093053582*X^6 + 2083087221800055/8038026093053582*X^5 + 8469260246279027/8038026093053582*X^4 + 163936769743295/4019013046526791*X^3 - 698458860092315/8038026093053582*X^2 + 10121113314853637/8038026093053582*X + 8126995418103551/8038026093053582

Ejercicios

Todos los ejercicios siguientes son de tests de SAGE de años anteriores.

Ejercicio

Usando el Teorema Chino del Resto en $\mathbb{Q}[x]$ , calcule el polinomio interpolador de los puntos $(1,0), (3,7), (9,11), (44,1).$
Usando el Teorema Chino del Resto en $\mathbb{F}_{121}[x]$ , calcule el polinomio interpolador de los puntos $(1,0), (3,7), (4,10), (9,1).$

Se recuerda que $f(a)=b \iff f(x)\equiv b \pmod{x-a}$

Ejercicio Defina $\mathbb{F}_{27}$ en SAGE y dé el polinomio mínimo de un generador de la extensión. Sabiendo que list(F) es una lista de los elementos del cuerpo finito (¡incluyendo el cero!), calcule una lista con las parejas de cada elemento no nulo y su inverso.

Ejercicio Defina una función fi(n) (sin usar euler_phi) que calcule $\varphi(n)$ por el procedimiento de contar los números menores que $n$ coprimos con $n$ . Calcule fi(10).

Ejercicio Sabemos que la ecuación $ax\equiv b \pmod{m}$ tiene solución si y sólo si $d=\gcd(a,m)$ divide a~ $b$ , y en este caso, las soluciones son $$ x=x_{0}+k \frac{m}{d}, \quad k=0,\dots, d,\quad x_{0}=\frac{b}{d}\alpha, \quad\text{con $d=\alpha a+\beta mParseError: KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲. $

Calcule todas las soluciones de la ecuación $84x\equiv 12 \pmod{36}$ .
Escriba el algoritmo en forma de función SAGE.

In [ ]:

In [ ]:

Enteros, congruencias, polinomios y cuerpos finitos

Enteros

Anillos de polinomios

Ejercicios

Product

Resources

Company