Aplicaciones del cálculo en congruencias

Aritmética con números grandes

La mayoría de los procesadores no son tan distintos de nosotros a la hora de trabajar con enteros: trabajan mucho más rápido con números pequeños que con números grandes.

Una importante consecuencia que puede llegar a deducirse de las propiedades de las congruencias modulares y del teorema chino del resto es que si consideramos un conjunto {m1, m2,..., mk} de números primos entre sí (es decir, que mcd(mi,mj)=1 para cada i, j distintos), entonces cualquier entero positivo n menor que m = m1. m2... mk se puede expresar mediante un vector o k-upla (r1,r2, ... ,rk), tal que los ri cumplan las siguientes condiciones:

1) 0 < ri <mi

2)

x ≡ r1 (mod m1)

x ≡ r2 (mod m2)

...........................

x ≡ rk (mod mk)

Además n será el único número x ∈ {0,1,2,...,m} que satisface esas ecuaciones (se asegura la unicidad de representación)

Ventajas de la aritmética modular para operar con números grandes

Las operaciones aritméticas con dos enteros grandes se pueden realizar entre las k-uplas o vectores que representan a ambos enteros. Las operaciones se realizan en paralelo módulo mi, para cada par de componentes i-ésimos análogos de los dos vectores. Además al ser los componentes de las k-uplas siempre menores que el módulo m, pueden realizarse cálculos que en aritmética entera desbordarían los registros de la unidad aritmética del ordenador.

Supongamos como ejemplo que tenemos que trabajar con un hardware que sólo puede realizar aritmética entera sin signo de 4 bits. Tendríamos un rango de enteros de {0,...,15}. No podríamos hacer operaciones como 16x11 usando aritmética entera, pues el resultado desbordaría nuestras capacidades de cálculo y representación. Pero si consideramos los siguientes módulos primos entre sí: m1=13, m2=14, m3=15, con lo que m= 13.14.15= 2730

Entonces, representamos 16 como el vector (16 mod 13, 16 mod 14, 16 mod 15) = (3, 2, 1) y 11 se representa como el vector (11, 11, 11)

Para multiplicar 16x11 multiplicamos los dos vectores en paralelo componente a componente: (3, 2, 1) x (11, 11, 11) = (33 mod 13, 22 mod 14, 11 mod 15) = (7, 8, 11)

(7, 8, 11) es la representación del entero 176 = 16 x 11.

Igualmente para sumar 16 + 11 = (3, 2, 1) + (11, 11, 11) = (1, 13, 12) que representa al número entero 27= (27 mod 13, 27 mod 14, 27 mod 15)

En cambio no se podría con este sistema multiplicar, por ejemplo, 60 x 60, ya que su resultado excede a m=2730.


Generación de números pseudoaleatorios

Lo primero que hay que notar acerca de los algoritmos generadores de números aleatorios que usan los ordenadores es que ¡los números que generan no son aleatorios!. Los ordenadores usan algoritmos determinísticos y por tanto es más correcto llamarles generadores de numeros pseudo-aleatorios, ya que generan una secuencia de números que eventualmente pueden volver a repetirse y solamente se aproxima a una secuencia aleatoria.

Las congruencias lineales se han utilizado tradicionalmente para la implementación de funciones generadoras de números pseudoaleatorios en las bibliotecas de programación de la mayoría de los lenguajes de programación clásicos como C, Fortran, Basic, etc. Los generadores congruenciales lineales de números aleatorios fueron propuestos por primera vez por D.H. Lehmer en 1951, y utilizan una congruencia lineal de la siguiente forma:

Xn = (aXn-1+c) (mod M)

Los parámetros a,c y M deben ser elegidos cuidadosamente para asegurar un largo período (número de enteros generados antes de que se repita la secuencia) y que la secuencia generada tenga buenas propiedades estadísticas de aleatoriedad y uniformidad. Para empezar el algoritmo se requiere un valor inicial X0, al que se llama la semilla.

Así, para referirnos a un generador congruencial lineal determinado usamos la notación GCL(a, c, M, X0). Cuando el generador utiliza como constante de incremento c=0, se le llama generador multiplicativo puro. Muchas veces se deja al programador elegir la semilla inicial, y se emplea entonces la notación GCL(a, c, M).

Una vez que se obtiene el entero Xn puede dividirse (división real) entre M para obtener valores reales distribuidos uniformemente en [0,1).

Algunas propiedades e inconvenientes de los GCL

  1. El módulo M es una cota superior del número de valores diferentes que puede tomar la semilla.
  2. Cuando Xi vuelve a tomar el valor de la semilla inicial X0, la secuencia se repetirá cíclicamente.
  3. Todas las secuencias producidas por este tipo de generador si se prolongan lo suficiente (período) acaban en un ciclo que se repite indefinidamente

Un buen generador lineal tendrá un período tan largo como sea posible (es decir, M). Para los generadores mixtos (los que no son multiplicativos puros) este máximo se alcanza si y sólo si se cumplen las tres siguientes condiciones que fueron enunciadas por Donald Knuth en su famoso libro The Art of Computer Programming:

  1. c es primo con M
  2. a-1 es múltiplo de p para todo primo p que divida a M
  3. a-1 es múltiplo de 4 siempre que M sea múltiplo de 4

Estas condiciones se cumplen, por ejemplo, si se escogen M=2k, a=4t+1, y c número impar, siendo t, k enteros mayores que 0.

Los GCL son sencillos de implementar, pero en la práctica las secuencias pseudoaleatorias generadas presentan correlaciones altas entre los números generados en la secuencia, lo que les hace poco útiles como fuente de números aleatorios en simulaciones por computadora medianamente complejas. También el hecho de que la secuencia de números generados es totalmente predecible los hace inefectivos para la generación segura de bits aleatorios usables en criptografía.

Ejemplos clásicos de GCLs

Correr aplicación Prueba generadores congruenciales lineales de números aleatorios


Tablas y funciones hash

Un problema habitual en la programación: almacenar en una tabla una gran cantidad de datos alfanuméricos de forma que se puedan recuperar lo más rápidamente posible cuando se busque un dato determinado en esa tabla.

Una posibilidad es mantener la tabla ordenada por un campo clave, de forma que mediante un algoritmo de tipo de búsqueda dicotómica o tipo Quicksearch, se pueda encontrar rápidamente el dato buscado empleando el menor número de pasos (comparaciones) posibles. La desventaja de las tablas ordenadas es que las inserciones de nuevos datos resultan más costosas que en las tablas no ordenadas.

Otra posibilidad es encontrar una función h(k), a a que llamaremos función hash, tal que dada una clave k nos devuelva directamente la posición que ocupa en la tabla el dato asociado a la clave k, sin necesidad de que la tabla esté ordenada. Además es deseable que en la medida de lo posible, h(k) no devuelva el mismo resultado para dos claves k distintas. Si se da el caso de que h(k1) y h(k2) devuelven un mismo valor, entonces ambas claves distintas tendrían que ocupar la misma posición o registro en la tabla, lo que evidentemente no puede ser. Se dice en estos casos que se ha producido una colisión y que h1 y h2 son claves sinónimas. La función h(k) debe tratar de evitar esto en la medida de lo posible.

Lo que en principio puede parecer complicado, encontrar una función tan "conveniente", usando congruencias el asunto es bien sencillo...

Recapitulando: necesitamos una función que transforme claves (normalmente enteros o cadenas de caracteres) en enteros en un rango [0..M-1], donde M es el número de registros de la tabla que podemos manejar con la memoria de que dispongamos. Como factores a tener en cuenta para la elección de la función h(k) están que minimice las colisiones y que sea relativamente rápida y fácil de calcular. Vamos a ver como puede conseguirse esto basándonos en las congruencias lineales.

Hasing modular

En este caso la función hash se calcula simplemente como h(k) = k mod M, usando el 0 como el primer índice de la tabla hash de tamaño M, y M-1 será el último índice o posición disponible.

Aunque la fórmula es aplicable a tablas de cualquier tamaño es importante elegir el valor de M con cuidado para evitar excesivos sesgos en la distribución de las claves. Una regla simple para elegir M es tomarlo como un número primo, lo más próximo posible a la cantidad de posiciones de memoria disponibles para la tabla. En cualquier caso existen reglas mas sofisticadas para la elección de M (ver Knuth), basadas todas en estudios teóricos de funcionamiento de los métodos congruenciales de generación de números aleatorios.

Es evidente que en muchas ocasiones el dominio de valores posibles de las claves Ki es mucho más amplio que el dominio de los residuos módulo M: {0,1,...,M-1}, por lo que necesariamente se produciran colisiones usando este tipo de funciones hash. Una elección correcta de M puede hacer bajar el número de colisiones esperadas.

Un comentario breve sobre resolución de colisiones entre sinónimos. Una posible solución es mantener listas enlazadas de sinónimos, de forma que si en la posición h(k) no se encuentra el dato asociado a la clave, sino que esta ocupada por una clave sinónima, entonces se busca el dato correcto en la lista enlazada correspondiente para ese sinónimo. Pero hay otras posibilidades para resolver colisiones, aunque no vamos a profundizar en el tema.


Dígitos de control

La aritmética modular se emplea a menudo en la vida diaria para validar códigos numéricos, caso del DNI, de los dígitos de control de una cuenta corriente bancaria, o del ISBN para la clasificación de libros. Veamos alguno de estos ejemplos:

Dígitos de control de una cuenta corriente

Un número de cuenta o Código de Cuenta Cliente (CCC) es una cadena de 20 dígitos de la forma EEEEOOOODCNNNNNNNNNN. Los cuatro primeros dígitos (EEEE) representan el código de la entidad bancaria, los cuatro siguientes (OOOO) representan el código de la oficina donde se dio de alta la cuenta, los dos siguientes (DC) son dos dígitos de control y los 10 restantes (NNNNNNNNNN) representan el número de cuenta.

Un número de cuenta se da por válido cuando los dígitos de control que aparecen en el código CCC coinciden con los dígitos de control que se calculan a partir del CCC. En concreto, el dígito D se calcula a partir del código de entidad (EEEE) y del código de oficina (OOOO) utilizando un algoritmo basado en asignar distintos pesos a los dígitos del código de entidad y de oficina y en la aritmética módulo 11. El algoritmo de cálculo de D es como sigue:

  1. La tabla de pesos para los dígitos de control correspondientes es:

    pos.E0E1E2E3O0O1O2O3
    peso485109736

  2. Se calcula el valor ponderado siguiente: valor = ∑Ei.pi + ∑Oj.pj
    Donde pi y pj son los pesos del correspondiente dígito Ei u Oj, según la tabla anterior.
  3. D = 11 - (valor mod 11)
  4. Como quiera que sólo se permiten dígitos entre 0 y 9, si D=11 se reemplazaría por D=0; y D=10 se reemplazaría por D=1.

El dígito de control C se refiere al número de cuenta corriente (NNNNNNNNNN) del código CCC y se calcula de forma análoga al dígito anterior:

  1. La tabla de pesos correspondiente es:

    pos.N0N1N2N3N4N5N6N7N8N9
    peso12485109736

  2. Se calcula el valor ponderado siguiente: valor = ∑Ni.pi
    Donde pies el peso del correspondiente dígito Ni, según la tabla anterior.
  3. C = 11 - (valor mod 11)
  4. Como quiera que sólo se permiten dígitos entre 0 y 9, si C=11 se reemplazaría por C=0; y C=10 se reemplazaría por C=1.

El cálculo de la letra del DNI

Un número de DNI es válido cuando la letra calculada a partir del DNI coincide con la letra que aparece en el DNI (a veces se la llama "la letra del NIF"). La forma de calcular esta letra es de la siguiente forma:

  1. Se calcula el resto de dividir el valor numérico del DNI entre 23.
  2. Una vez se tiene ese resto, para encontar la letra correspondiente se utiliza la siguiente tabla que establece la relación entre el resto de la división efectuada y la letra que debe aparecer en el DNI:

    Resto012345678 91011121314151617 1819202122
    LetraTRWAGMYFP DXBNJZDQV HLCKE

Validación del número ISBN

ISBN es el número que se utiliza universalmente para la catalogación de publicaciones impresas. Un número ISBN contiene distinta información identificadora de la editorial que publica y del título en cuestión. Consta de 9 dígitos decimales, que aparecen en grupos separados por guiones que pueden figurar en muy distintas posiciones, seguidos de un dígito de control para la suma de verificación. Este dígito puede tomar valores entre 0 y 10, usándose la letra X para representar el valor 10.

La forma de cálculo de ese dígito de control (checksum) es muy sencilla. Si representamos los 9 primeros dígitos como d1d2d3...d9, el décimo dígito se calcula como:

d10 = (1.d1 + 2.d2 + 3.d3 + ... + 9.d9) mod 11

Correr aplicación Validador para Códigos de Cuenta bancarios, DNI e ISBN


Anterior Arriba Siguiente