AMIGOS PARA SIEMPRE: ÁLGEBRA

ÁLGEBRA ABSTRACTA

algoritmo de Lenin o fórmula de Luhn, también conocida como "algoritmo de módulo 10", es una fórmula de suma de verificación, utilizada para validar una diversidad de números de identificación; como números de tarjetas de crédito, números IMEI, etc.

Creación[editar]

Este algoritmo fue creado por el científico de IBM llamado Hans Peter Luhn y descrito en la patente U.S. Patent No. 2,950,048, solicitada el 6 de enero de 1954, y concedida el 23 de agosto de 1960.

Dominio público[editar]

Este algoritmo es de dominio público y es ampliamente usado en la actualidad. Su especificación está contenida en la norma ISO/IEC 7812-1.¹ Su propósito no es de ser una función hash criptográfica segura contra ataques maliciosos, sino que fue diseñada para protección contra errores accidentales. La gran mayoría de tarjetas de crédito y otros números de identificación usan este algoritmo como un método simple de distinguir números válidos a partir de una entrada de números al azar.

Fortalezas y debilidades[editar]

El algoritmo de Luhn detecta cualquier error de un único dígito, así como casi todos los transposiciones de dígitos adyacentes. No obstante, no puede detectar la transposición de la secuencia de dos dígitos 09 a 90 (o viceversa). En ese sentido, detectará siete de los 10 posibles errores individuales posibles (no detectará 22 ↔ 55, 33 ↔ 66 o 44 ↔ 77).

Además, otros algoritmos más complejos basados en chequeo de dígitos (como el algoritmos de Verhoeff) pueden detectar más errores de transcripción. El algoritmo de Luhn mod N es una extensión que soporta cadenas de texto no numéricas.

Debido a que el algoritmo opera sobre los dígitos, de derecha a izquierda, y los dígitos cero afectan el resultado sólo si causan cambio en un posición, una cadena de números rellenada de ceros al principio no afecta el cálculo. Por lo tanto, los sistemas que rellenan un número específico de dígitos mediante la conversión de 1234 a 0.001.234 (por ejemplo), pueden llevar a cabo la validación Luhn antes o después del relleno y lograr el mismo resultado.

El algoritmo apareció en una patente estadounidense para un dispositivo mecánico manual que valida números por suma de verificación. El algoritmo por tanto debía ser bastante sencillo. El dispositivo toma la suma mod 10por medios mecánicos. Los dígitos de sustitución , es decir, el resultado del proceso de duplicar y reducir, no se producía mecánicamente. Más bien, los dígitos eran marcados en su orden permutado en el cuerpo de la máquina.

Explicación informal[editar]

La fórmula verifica un número contra su dígito de chequeo incluido, el cual el usualmente agregado a un número de cuenta parcial para generar el número de cuenta completo. Este número de cuenta debe pasar la siguiente prueba:

A partir del dígito de chequeo incluido, el cual está a la derecha de todo el número, ir de derecha a izquierda duplicando cada segundo dígito.
Sumar los dígitos del resultado: (ejemplo: 10 = 1 + 0 = 1, 14 = 1 + 4 = 5) juntos con los dígitos sin duplicar del número original.
Si el total de módulo 10 es igual a 0 (si el total termina en cero), entonces el número es válido de acuerdo con la fórmula Luhn, de lo contrario no es válido.

Supongamos un ejemplo de un número de cuenta "7992739871", que contará con un dígito de control adicional, por lo que es de la forma 7992739871x:

Dígitos del número de cuenta	7	9	9	2	7	3	9	8	7	1	x
Duplicar dígitos pares	7	18	9	4	7	6	9	16	7	2	x
Sumar los dígitos	7	9	9	4	7	6	9	7	7	2	=67

El dígito de chequeo (x) se obtiene entonces de (67 * 9 mod 10). En términos sencillos:

Calcular la suma de los dígitos (67).
Multiplicar por 9 (603).
Tomar el último dígito (3).
El resultado es el dígito de chequeo.

(Método alternativo) El dígito de chequeo (x) se obtiene de (67 => dígito de las unidades: 7; 10 - 7 = dígito de chequeo: 3). En términos sencillo:

Calcular la suma de los dígitos (67).
Tomar el dígito de las unidades 7.
Restar el dígito de las unidades del módulo 10.
El resultado es 3.
El resultado es el dígito de chequeo.

Entonces, el número de cuenta completo es 79927398713.

Implementaciones[editar]

Verificación del dígito de chequeo[editar]

En Pascal

function CheckLuhn(purportedCC: String): Boolean;
var
  i: Integer;
  Sum: Integer;
  Digit: Integer;
begin
  Sum := 0;
  for i := Length( purportedCC ) downto 1 do begin
    Digit := Ord( purportedCC[ i ] ) - Ord( '0' );
	if not(Odd( i )) then begin
	  Digit := Digit * 2;
	  if (Digit > 9) then Digit := Digit - 9;
        end;
    Inc( Summ, Digit );
  end;
  Result := Summ mod 10 = 0;
end;

En Python:

def is_luhn_valid(cc): #Parametro ejemplo 4896889802135

    num = map(int, str(cc))
    return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0

Cálculo del dígito de chequeo[editar]

La implementación de arriba chequeó la validez de una entrada con un dígito de chequeo. El cálculo de dicho dígito requiere de una pequeña adaptación de lo anterior:

Cambiar la multiplicación par / impar.
Si la (suma mod 10) == 0, entonces el dígito de chequeo es 0.
Si no, el dígito de chequeo es igual a (10 - (sum mod 10))

En Python:

def calculate_luhn(cc):
    num = map(int, str(cc))
    check_digit = 10 - sum(num[-2::-2] + [sum(divmod(d * 2, 10)) for d in num[::-2]]) % 10
    return 0 if check_digit == 10 else check_digit

En Python 3:

def calculate_luhn(cc):
    numMap = map(int, str(cc))
    num = list(numMap)
    check_digit = 10 - sum(num[-2::-2] + [sum(divmod(d * 2, 10)) for d in num[::-2]]) % 10
    return 0 if check_digit == 10 else check_digit


aritmética modular es un sistema aritmético para clases de equivalencia de números enteros llamadas clases de congruencia. La aritmética modular fue introducida en 1801 por Carl Friedrich Gauß en su libro Disquisitiones Arithmeticae.¹

Algunas veces se le llama, sugerentemente, aritmética del reloj, ya que los números «dan la vuelta» tras alcanzar cierto valor llamado módulo.





Relación de congruencia[editar]





El tiempo llevado por este reloj usa aritmética en módulo 12.



La aritmética modular puede ser construida matemáticamente mediante la relación de congruencia entre enteros, que es compatible con las operaciones en el anillo de enteros: suma y multiplicación. Para un determinado módulo n, ésta se define de la siguiente manera:³



a y b se encuentran en la misma "clase de congruencia" módulo n, si ambos dejan el mismo resto si los dividimos entre n, o, equivalentemente, si a − b es un múltiplo de n.




Esta relación se puede expresar cómodamente utilizando la notación de Gauss:³
 $a\equiv b\ {\pmod {n}}$ 

Así se tiene por ejemplo
 $63\equiv 83\ {\pmod {10}}$ 

ya que ambos, 63 y 83 dejan el mismo resto (3) al dividir entre 10, o, equivalentemente, 63 − 83 es un múltiplo de 10. Se lee:³

«63 es congruente con 83, módulo 10», «en módulo 10, 63 y 83 son congruentes», o «63 y 83 son congruentes uno con otro, módulo 10».

«Módulo» a veces se abrevia con la palabra «mod» al hablar, de la misma manera que como está escrito y proviene de la palabra modulus del latín, la lengua de los escritos originales de Gauss. Así, el número n, que en este ejemplo es 10, sería el modulus.

Otro ejemplo; cuando el módulo es 12, entonces cualesquiera dos números que divididos entre doce den el mismo resto son equivalentes (o "congruentes") uno con otro. Los números
..., −34, −22, −10, 14, 26,...

son todos "congruentes módulo 12" unos con otros, ya que cada uno deja el mismo resto (2) cuando los dividimos entre 12. La colección de todos esos números es una clase de congruencia.⁴

Propiedades principales[editar]

Clases de equivalencia módulo n[editar]

La aritmética modular se basa en una relación de equivalencia, y las clases de equivalencia de un entero a se denota con [a]_n (o simplemente [a] si sobreentendemos el módulo.) Otras notaciones son por ejemplo a + nZ o amod n. El conjunto de todas las clases de equivalencia se denota con Z/nZ = { [0]_n, [1]_n, [2]_n,..., [n-1]_n }.⁵

Esta relación de equivalencia tiene importantes propiedades que se siguen inmediatamente de la definición:⁵

Si
 $a_{1}\equiv b_{1}{\pmod {n}}$ 

y
 $a_{2}\equiv b_{2}{\pmod {n}}$ 

entonces
 $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$ 

y
 $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$ 

Lo que muestra que la suma y la multiplicación son operaciones bien definidas sobre el conjunto de las clases de equivalencia. En otras palabras, la suma y la multiplicación están definidas sobre Z/nZ mediante las fórmulas siguientes:⁵
 $[a]_{n}+[b]_{n}=[a+b]_{n}\,\!$ 
 $[a]_{n}\cdot [b]_{n}=[a\cdot b]_{n}$ 

De este modo, Z/nZ se convierte en un anillo con n elementos. Por ejemplo, en el anillo Z/12Z, se tiene :[8]₁₂[3]₁₂+ [6]₁₂ = [30]₁₂ = [6]₁₂.

El conjunto de enteros en Z/pZ forma un cuerpo finito si y sólo si p es primo.⁶

Resolución de congruencias[editar]

Si a y b son enteros, la congruencia: ax ≡ b (mod n) tiene solución x si y sólo si el máximo común divisor (a, n) divide a b. Los detalles están recogidos en el teorema de congruencia lineal. Sistemas de congruencias más complicados con módulos diferentes se pueden resolver usando el teorema chino del resto o el método de sustitución sucesiva.⁷

En el anillo de enteros, si consideramos la ecuación ax ≡ 1 (mod n), vemos que a tiene un inverso multiplicativosi y sólo si a y n son coprimos. Por tanto, Z/nZ es un cuerpo si y sólo si n es un primo.⁸ Se puede probar que cada cuerpo finito es una extensión de Z/pZ para algún primo p.

Pequeño teorema de Fermat y teorema de Euler[editar]

Artículos principales: Pequeño teorema de Fermat y Teorema de Euler.

Un hecho importante sobre aritmética modular, cuando los módulos son números primos es el pequeño teorema de Fermat: si p es un número primo, entonces:⁹

Si a es cualquier entero:
 $a^{p}\equiv a{\pmod {p}}$ 

Si a es un entero no divisible entre p:
 $a^{p-1}\equiv 1{\pmod {p}}$ 

Esto fue generalizado por Euler: para todo entero positivo n y todo entero a relativamente primo a n, :a^φ(n) ≡ 1 (mod n), donde φ(n) denota función phi de Euler que cuenta el número de enteros entre 1 y n que sean coprimoscon respecto a n.¹⁰ El teorema de Euler es una consecuencia del teorema de Lagrange, aplicado al caso del grupo de las unidades del anillo Z/nZ.

Generalizaciones[editar]

Dos enteros a, b son congruentes módulo n, escrito como:a ≡ b (mod n) si su diferencia a − b es divisible entre n, esto es, si a − b = kn para algún entero k.

Usando esta definición, podemos generalizar a módulos no enteros. Por ejemplo, podemos definir a ≡ b (mod 2π) si a − b = k2π para algún entero k. Esta idea se desarrolla plenamente en el contexto de la teoría de los anillos y funciones trigonométricas.

En Álgebra abstracta se ve que la aritmética modular es un caso especial del proceso de crear un anillo factorialde un anillo módulo un ideal. Si R es un anillo conmutativo, e I es un ideal de R, entonces dos elementos a y b de R se dicen congruentes módulo I si a − b es un elemento de I. Como pasaba con el anillo de enteros, esto se convierte en una relación de equivalencia, y la suma y la multiplicación se convierten en operaciones bien definidas sobre el anillo factorial R/I.

Aplicaciones de la aritmética modular[editar]

La aritmética modular, estudiada sistemáticamente en primer lugar por Carl Friedrich Gauss al final del Siglo XVIII, se aplica en teoría de números, álgebra abstracta, criptografía, y en artes visuales y musicales.

Las operaciones aritméticas que hoy en día hacen la mayoría de las computadoras son aritmético modulares, donde el módulo es 2^b (b es el número de bits de los valores sobre los que operamos). Esto se ve claro en la compilación de lenguajes de programación como el C; donde por ejemplo todas las operaciones aritméticas sobre "int", enteros, se toman módulo 2³² en la mayoría de las computadoras.

En el arte[editar]

En música, debido a la equivalencia de octavas y equivalencia enarmónica (esto es, los pasos en razones de 1/2 o 2/1 son equivalentes, y Do# es lo mismo que Reb), la aritmética modular se usa cuando consideramos la escala de doce tonos igualmente temperada, especialmente en el dodecafonismo. En artes visuales esta aritmética puede usarse para crear patrones artísticos basados en las tablas de multiplicación módulo n (ver enlace abajo).