Programa para resolver ecuaciones de congruencia lineal

Editado el 11/03/2018:

Casi un año después de su publicación, observo en Google Analytics que este artículo tiene un porcentaje de rebote muy elevado. Tal vez este sea debido a que la mayoría de visitantes estén buscando simplemente un programa que resuelva congruencias lineales. Si es tu caso, para ejecutar el programa que aparece al final de esta entrada, puedes instalar fácilmente el intérprete de Python 2 en tu ordenador, es muy ligero y existe para todas las plataformas. Como alternativa, dispones de intérpretes en línea (1, 2) donde puedes copiar y pegar el código; después deberás modificarlo ligeramente porque los parámetros no serán argumentos pasados a través de la línea de comandos.


Una ecuación de congruencia es una congruencia entre expresiones literales, los valores que la satisfacen son sus soluciones. Por ejemplo 13x ≡ 5 (mod 77) es una ecuación de congruencia.

Sus soluciones nos las da x ≡ 30 (mod 77) Es decir, todos los infinitos x que al dividirlos por 77 dan el mismo resto que 30/77 Dicho resto es 30 y todos los x serían múltiplos de 77· + 30: 30, 107, 184, 261…

Si reemplazamos estos x en la ecuación de congruencia lineal inicial veremos que son soluciones:

13*30 ≡ 30 (mod 77) => Resto 5. Así como dan el mismo resto:

13*107 ≡ 30 (mod 77)

13*184 ≡ 30 (mod 77)

Para poder encontrar la solución de una congruencia lineal en primer lugar hay que saber hallar el inverso de a (mod m) Este inverso, a’, es un número tal que a’*a ≡ 1 (mod m)

Por ejemplo, el inverso de 6 (mod 11) es 2: 2*6 ≡ 1 (mod 11)

Teorema: La condición necesaria y suficiente para que dos números a y b sean congruentes respecto al módulo m es que su diferencia sea un múltiplo de m, es decir, m | (a -b)

Por lo tanto en el ejemplo sería 11 | (a’ * 6 – 1) => 6a’ – 1 = 11· , 6a’ = 11· + 1 Como ha de ser un múltiple de 11 + 1 vemos fácilmente que a’ = 2 cumple la condición.

Si para hallar el inverso de 2 (mod 8) hacemos: 8 | (a’ * 2 – 1) Vemos que no hay solución pues 2a’ -1 siempre será un número impar mientras que 8 es par. Por lo tanto no siempre existe un inverso. El siguiente teorema nos permite saber cuando existe el inverso:

La condición necesaria y suficiente para que un entero a posea un inverso módulo m, m > 1, es que mcd(a, m) = 1 Además, si existe tal inverso, ese inverso es único módulo m.

Esto nos resulta familiar con el teorema de Bezout explicado en el artículo anterior. Por ejemplo, para calcular el inverso de 111 (mod 250) primero calculamos mcd(111, 250) = 1 Por lo tanto sabemos que existe un inverso a’ y que habrá un s y un t tal que:

111 *s + 250 * t = 1

Aplicando el algoritmo del artículo obtenemos s = -9 y t = 11 y por lo tanto a’ = -9. Así es:

-9 * 111 ≡ 1 (mod 250)

  • -999 dividido entre 250 da el mismo resto que 1 entre 250, r = 1
  • 250 | (-9 * 111 -1) => 250· = -9 * 111 – 1 => Efectivamente -1000 es múltiplo de 250

Ahora bien, existe un teorema que matiza el anterior:

Existe un entero positivo único a’ menor que m que es un inverso de a (mod m) y cualquier otro inverso de a (mod m) será congruente con a’ (mod m)

Como dijimos en el anterior artículo, el par s y t no es único. La expresión general que nos da todos los coeficientes es:

1 =111(-9 + 250h) + 250(4 – 111h) ∀ h ∈ Z

Para h = 1 tendríamos:

1 = 111*241 + 250*(-107)

Como s = 241 y t = -107 tendremos 111*241 ≡ 1 (mod 250) Por lo tanto es 241 el inverso positivo menor que 250.

Si por un lado tenemos la ecuación de congruencia lineal ax ≡ b (mod m) y esta tiene un a’ ∈ Z tal que a’*a = 1 (mod m) Por otro lado, como cualquier número es congruente consigo mismo módulo m podemos crear la congruencia a’ ≡ a’ (mod m).

Un importante teorema dice:

Sean a, b, c y d enteros y m un entero positivo. Si es ab (mod m) y cd (mod m), entonces también es ac ≡ bd (mod m).

Con este teorema, de las dos congruencias anteriores resulta:

ax * a’ ≡ a’ * b (mod m)

Como a’ * a (mod m) = 1 Queda:

1 * x ≡ a’ * b (mod m)

Si existe el inverso modular, es decir, si m y a son primos relativos, o lo que es lo mismo, si mcd(m, a) = 1, todo x congruente con a’ * b (mod m) será solución a la ecuación de congruencia.

Vamos a calcular la solución de 3x ≡ 5 (mod 13):

El programa del artículo anterior, para a y m, es decir, 3 y 13 nos devuelve:

m.c.d. = 1

Bezout s = -4

Bezout t = 1

Como a y m son primos entre si, sin más cálculos podemos ver que el inverso de 3 (mod 13) es 9, pero procedamos como hemos visto. Si el inverso es -4 necesitamos encontrar el positivo, busquemos para ello otro par s y t con h = 1:

1 = 3*(-4 + 13*1) + 13*(1 – 3*1) = 3*9 + 13*(-2)

Por esta vía también obtenemos a’ = 9. Todo x congruente con 9*5 (mod 13) será solución. Como 45 (mod 13) = 6, todos los múltiples de 13· + 6 serán las soluciones a 3x ≡ 5 (mod 13). Por lo tanto, x ≡ 6 (mod 13) es una congruencia equivalente más simple.

Vamos a calcular la solución de 5x ≡ 2 (mod 6):

El programa nos devuelve:

m.c.d. =  1
Bezout s =  -1
Bezout t =  1

Como a y m son primos entre si, tendremos que el inverso a’ es -1. Busquemos el positivo:

1 = 5 * (-1 + 6*1) + 6*(1 – 5*1) = 5 * 5 + 6 * -4

El inverso positivo menor que m es 5.

5*2 (mod 6), 10 (mod 6), x ≡ 10 (mod 6) Los infinitos x congruentes con 10 módulo 6 serán solución de 5x ≡ 2 (mod 6). Es decir, todos los múltiples 6· + 4 Por lo tanto, es equivalente x ≡ 4 (mod 6)

Cuando a y m no son primos entre si, es decir mcd(a, m) > 1 y b es un múltiplo del mcd, es decir mcd | b, la congruencia tiene solución. Si queremos entender el proceso para hallar las soluciones y no limitarnos a aplicar fórmulas será necesario introducir los conjuntos de restos y las clases de equivalencia, pero para ello será necesario un nuevo artículo.

El siguiente programa en Python calcula las ecuaciones de congruencia que se han tratado en este artículo.

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Resuelve ecuaciones de congruencia tipo ax ≡ b (mod m)

import sys
from sys import argv

def extendedEuclideanAlgorithm(old_r, r):
    negative = False
    s, old_t = 0, 0
    old_s, t = 1, 1

    if (r < 0):
        r = abs(r)
        negative = True

    while r > 0:
            q = old_r / r
            #MCD:
            r, old_r = old_r - q * r, r
            #Coeficiente s:
            s, old_s = old_s - q * s, s
            #Coeficiente t:
            t, old_t = old_t - q * t, t

    if negative:
        old_t = old_t * -1
        
    return old_r, old_s, old_t

a = long(argv[1])
b = long(argv[2])
m = long(argv[3])
#Para las soluciones no necesitaremos t pero lo recogemos para evitar el error.
mcd, s, t = extendedEuclideanAlgorithm(a, m)
if mcd == 1:
    inverse = (s * b) % m
    print "x ≡ {0} (mod {1})" . format(inverse, m)
elif b%mcd == 0:
    print "Ver siguiente artículo"
else:
    print "No tiene solución"

Para resolver la ecuación 3x ≡ 5 (mod 13) haríamos:

vic@LESBIAN:~/mates$ ./inversoModulo.py 3 5 13
x ≡ 6 (mod 13)

Cálculo del mcd y la identidad de Bezout

Editado el 11/03/2018:

Casi un año después de su publicación, observo en Google Analytics que este artículo tiene un porcentaje de rebote muy elevado. Tal vez este sea debido a que la mayoría de visitantes estén buscando simplemente un programa que calcule el mcd de dos números y sus coeficientes de Bezout. Si es tu caso, puedes instalar fácilmente el intérprete de Python 2 en tu ordenador, es muy ligero y existe para todas las plataformas. Como alternativa, dispones de intérpretes en línea (1, 2) donde puedes copiar y pegar el código; después deberás modificarlo ligeramente porque los parámetros no serán argumentos pasados a través de la línea de comandos.


He hecho un breve programa en Python que calcula el máximo común divisor (mcd) de dos números pasados como parámetros y sus coeficientes de Bezout. El teorema de Bezout nos dice que dados dos números a y b, cuyo mcd(a, b) = d existen dos números enteros s y t tales que:

a*s + b*t = d

Estos dos números s y t son los llamados coeficientes de Bezout. Este par s y t no tiene por qué ser único, pueden haber otros s y t que cumplan la igualdad. La identidad de Bezout no es una mera curiosidad matemática sino que tiene muchas aplicaciones: desde calcular el inverso de a módulo m, lo que permite resolver ecuaciones de congruencia lineal, hasta resolver ecuaciones diofánticas.

El máximo común divisor se puede calcular a mano como nos enseñaron en la escuela mediante el algoritmo de Euclides. Los coeficientes de Bezout los podemos calcular a mano mediante el algoritmo extendido de Euclides, pero a la hora de programar es más fácil implementar el siguiente algoritmo explicado en la Wikipedia.

Todos estos valores se calculan mediante la división euclídea y esta impone la condición 0 >= r < |d| Es decir, el resto debe ser mayor o igual a 0 y menor que el valor absoluto del divisor. Como expliqué en un artículo anterior, Python no hace la división euclídea cuando el divisor es negativo, por lo tanto en el código hago una pequeña manipulación al signo del segundo número para obtener los coeficientes de Bezout con los signos correctos.

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import sys
from sys import argv

old_r = long(argv[1])
r = long(argv[2])
negative = False
s, old_t = 0, 0
old_s, t = 1, 1

if r < 0:
    r = abs(r)
    negative = True

while r > 0:
    q = old_r / r
    #MCD:
    r, old_r = old_r - q * r, r
    #Coeficiente s:
    s, old_s = old_s - q * s, s
    #Coeficiente t:
    t, old_t = old_t - q * t, t

if negative:
    old_t = old_t * -1
    
print "m.c.d. = ", old_r
print "Bezout s = ", old_s
print "Bezout t = ", old_t

Ejemplo de su ejecución desde la terminal:

vic@LESBIAN:~/mates$ ./bezoutYmcd.py 23 -4
m.c.d. =  1
Bezout s =  -1
Bezout t =  -6

Si convertimos este programa en una función tendremos una herramienta útil para calcular el inverso de a módulo m, resolver ecuaciones de congruencia lineal y ecuaciones diofánticas.

Probando servicios web con HttpRequester

Cuando se trata de probar un Web Service RESTful, ya sea nuestro o de un tercero, existe un addon para Firefox muy útil: HttpRequester

Método Options

Solicito al servidor las opciones disponibles (OPTIONS) y devuelve: GET, HEAD, PUT, PATCH, POST y DELETE

Cabecera del método Get

Get sobre la misma URL y a la derecha vemos la cabecera que devuelve el servidor

Cuerpo del método Get

Si hacemos doble click sobre la petición podremos ver el cuerpo de la misma

Método Delete

Borramos el post con ID = 1

Como se puede apreciar en los ejemplos, HttpRequester es una herramienta de Firefox bastante útil para un desarrollador de aplicaciones web.

Javascript ya no es un lenguaje de juguete

Hace años que Javascript ya no es un lenguaje de juguete con el que manipular con Dios y ayuda el DOM del navegador1 y para muestra un botón, ¡pero qué botón!

Emulador de PC con Javascript

También incorpora una versión reducida del compilador gcc

Se trata de un simulador de PC desarrollado en Javascript que puede ejecutarse perfectamente en tu navagador. Concretamente emula un procesador 486 (sin coprocesador matemático), RTC (reloj interno), puerto serie, disco duro, etc.

Además el emulador no viene solo sino que incorpora un Linux (Kernel 2.6.20) y una versión del compilador GCC que el mismo programador del emulador creó: Tiny C Compiler. Se trata de una versión mucho mucho más ligera y rápida que el compilador original.

El genial autor de esta obra es el francés Fabrice Bellard. Es un su web podéis encontrar otras muestras de su genio.

Desde que en 2008 los navegadores empezaron a incorporar compiladores JIT en vez de interpretar el código Javascript, la velocidad de ejecución dio un enorme salto. A medida que van mejorando (hoy en día son capaces incluso de optimizar código) siguen reduciéndose los tiempos. Esto ha dado más alcance a Javascript, por ejemplo Node.js funciona mediante una implementación en el lado servidor del compilador JIT para Chrome llamado V8.

Eso sí, a pesar de todas las librerías y software que ha crecido entorno a este lenguaje, y a pesar de su evolución, sigue teniendo características que hacen difícil la vida del programador:


1 Posiblemente las dificultades más que ser debidas a carencias de Javascript lo eran por los bugs de los navegadores a la hora de manipular el Document Object Model y a las diferencias entre ellos para implementar su manipulación (o el estándar no era muy concreto o era ignorado donde convenía implementarlo de otra manera, no lo sé). En todo caso, sobre Javascript recaían parte de las culpas con el consiguiente desprestigio.

En PHP un sistema de plantillas es prescindible

Si bien es cierto que PHP hace muchos años que dejó de ser un sistema de plantillas tampoco me parece que necesite implementar un sistema de plantillas de forma imperiosa. En su origen, PHP era un sencillo lenguaje, cuyo intérprete programó en C Rasmus Lerdorf, destinado a implementar su página personal, de ahí el acrónimo Personal Home Page. Mucho ha llovido desde entonces y hace tiempo que PHP es un lenguaje orientado a objetos bastante potente con muchas librerías a su disposición. A pesar de ello, un motor de plantillas me parece una sobrecarga innecesaria y mucho menos me convence el razonamiento de querer dotar al lenguaje de una especie de aura de seriedad. En casos concretos hace más bien que mal, pero hay 2 razones por las que en muchos casos me parece prescindible.

Primera: Un sistema de templates añade una sobrecarga no despreciable. El entorno más frecuente para PHP son los servidores web compartidos que alojan diversas webs. Los costes de alojamiento son reducidos por la poca carga que supone PHP, tanto en tiempo de CPU como RAM consumida. Poner en esos servidores mastodontes como Symfony tiene su peaje. El patrón MVC es conveniente, la sobrecarga no, y la V de vista no implica usar plantillas. Más sobre esto en mi segunda razón.

Hace ya años que PHP es usado también en grandes aplicaciones web, con miles de usuarios conectados simultáneamente y cuyo alojamiento no alcanza en un sólo servidor sino que se requiere de una server farm. Trabajé en una empresa así y recuerdo que la competencia de dicha empresa había apostado por Java, un lenguaje más «serio» (más empleado a nivel corporativo). El gasto en servidores de esa empresa multiplicaba en varias veces el de la nuestra y cuando se llega a cierto volumen los costes dejan de ser despreciables y empiezan a marcar diferencias. Que PHP, a diferencia de Java, no necesite ingentes recursos para declarar un simple entero es una poderosa razón por la que barrió a Java de la web.

Segunda: Algunos argumentan que PHP es demasiado «parlanchín» para ser empleado en la vista pero no estoy de acuerdo. Puede (o no) que esto:

{foreach $foo as $bar}

Sea mejor que esto:

<?php foreach($foo as $bar){ ?>

Pero es idéntico a los «short tags» que PHP sigue permitiendo. Además, PHP dispone de una sintaxis alternativa para las estructuras de control:

<? foreach($foo as $bar): ?>

Esto también es objeto de crítica:

<?php echo htmlspecialchars($var, ENT_QUOTES, 'UTF-8') ?>

¿Por qué no usar esto?

<?=htmlspecialchars($var, ENT_QUOTES, 'UTF-8') ?>

Para que nadie sufra del síndrome metacarpiano podemos encapsular en algún helper esa función, como hace CakePHP:

<?=h($var) ?>

La función sería algo así:

function h($text)
{
return htmlspecialchars($text, ENT_COMPAT | ENT_HTML5, 'UTF-8');
}

Así mismo se pueden crear fácilmente otras funciones para agilizar la programación de las vistas.

También se argumenta que diseñadores y maquetadores no tienen por qué saber acerca de temas de seguridad como los ataques XSS y CSRF y que para que ellos puedan programar las vistas con seguridad debe implementarse un sistema de plantillas. En estos casos sí sería necesario usarlo y sólo añadiría lo siguiente: he conocido muchos diseñadores y no he visto ninguno interesado en programar en el lado servidor. Iría más lejos: no he conocido ninguno interesado en programar. A lo sumo, sí en aprender Flash en sus años buenos. Frecuentemente, ni tan siquiera Javascript, a pesar de incluir ficheros en sus diseños. Obviamente les interesan las funcionalidades que aporta pero en general no están interesados en saber cómo funciona. En la industria que yo conozco, programar las vistas acaba siendo trabajo también del programador y éste sí conoce (o debería) las implicaciones de seguridad. Si en la empresa los diseñadores sí están por la causa sí sería conveniente usar un sistema de templates.

Otras casos en los que puede ser interesante usarlo es cuando se requiere una sandbox con un susbset de las funciones propias y/o de PHP. Por ejemplo si el usuario desde el back end ha de poder acceder a arrays con datos y a ciertas funciones para transformar y operar esos datos. Para estos casos hay sistemas de templates como Twig que proporcionan una sandbox y sería razonable usarlos en vez de reinventar la rueda programando uno propio.

A pesar de no ser necesario un sistema de plantillas en la mayoría de aplicaciones web, ya consiguen hacer negocio con ellos. ¿Necesidad real o creada?

La diferencia entre getElementById y el dólar de jQuery

j-query

Cuando atiendo las preguntas de un programador junior en problemas con su código Javascript me doy cuenta de que muchas son debidas a la confusión entre jQuery y un objeto del DOM. Los que empezamos a tocar Javascript antes de la llegada de librerías como jQuery vemos la diferencia claramente, pero hoy en día, cuando un programador novel se lanza a desarrollar en el lado cliente código Javascript estará usando, como mínimo, una librería como jQuery, por lo que lo raro sería que no confundiera ambos.

Vamos a ver en qué consiste la confusión. Cuando trabajamos con la librería jQuery podemos pensar que seleccionar un elemento por su ID:

$('#myVideo').....

Es equivalente a como lo hacíamos antes, cuando no existía la librería jQuery:

document.getElementById('myVideo');

Sigue leyendo