17.1.2: El teorema de la relación invariante

Algoritmos de exponentación

Considere el siguiente algoritmo implementado en Sage para calcular\(a^m mod \, n\text{,}\) dado un exponente\(a\text{,}\) no negativo entero arbitrario\(m\text{,}\) y un módulo\(n\text{,}\)\(n \ge 0\text{.}\) La evaluación de muestra predeterminada calcula\(2^5\, mod\,7 = 32\,mod\,7 = 4\text{,}\) pero puede editar la línea final para otras entradas.

def slow_exp(a,m,n):
    b=1
    k=m
    while k>0:
        b=(b*a)%n  # % is integer remainder (mod) operation
        k-=1
    return b
slow_exp(2,5,7)

Debe quedar bastante claro que este algoritmo calculará con éxito\(a^m (mod\, n)\) ya que imita la definición básica de exponenciación. Sin embargo, este algoritmo es altamente ineficiente. El algoritmo que más se utiliza para la tarea de exponenciación es el siguiente, también implementado en Sage.

def fast_exp(a,m,n):
    t=a
    b=1
    k=m
    while k>0:
        if k%2==1: b=(b*t)%n
        t=(t^2)%n
        k=k//2  # // is the integer quotient operation
    return b    
fast_exp(2,5,7)

La única dificultad con el “algoritmo rápido” es que puede que no sea tan obvio que siempre funcione. Cuando se implementa, se puede verificar con el ejemplo, pero se puede hacer una verificación aún más rigurosa utilizando el Teorema de la Relación Invariante. Antes de exponer el teorema, definimos alguna terminología.

17.1.2.2: Demostrar la exactitud del algoritmo rápido

Definición \(\PageIndex{1}\): Pre and Post Values

Dada una variable,\(x\text{,}\) el valor pre\(x\text{,}\) denotado\(\grave x\text{,}\) es el valor antes de una iteración de un bucle. El valor post, denotado\(\acute x\text{,}\) es el valor después de la iteración.

Ejemplo\(\PageIndex{1}\): Pre and Post Values in the Fast Exponentiation Algorithm

En el algoritmo de exponenciación rápida, las relaciones entre los valores pre y post de las tres variables son las siguientes.

\ comenzar {ecuación*}\ aguda {b}\ equiv\ tumba {b}\ tumba {t} ^ {\ tumba {k} mod\ ,2} (mod\, n)\ fin {ecuación*}

\ start {ecuación*}\ aguda {t}\ equiv\ grave t^2 (mod\, n)\ final {ecuación*}

\ begin {ecuación*}\ aguda k =\ grave k//2\ final {ecuación*}

Definición\(\PageIndex{2}\): Invariant Relation

Dadas las entradas de un algoritmo y un conjunto de variables que se utilizan en el algoritmo, una relación invariante es un conjunto de una o más ecuaciones que son verdaderas antes de ingresar a un bucle y permanecen verdaderas en cada iteración del bucle.

Ejemplo\(\PageIndex{2}\): Invariant Relation for Fast Exponentiation

Afirmamos que la relación invariante en el algoritmo rápido es\(b t^k = a^m (mod\,n)\text{.}\) Vamos a demostrar que esto es cierto a continuación.

Teorema \(\PageIndex{1}\): The Invariant Relation Theorem

Dado un bucle dentro de un algoritmo, si\(R\) es una relación con las propiedades

1. R es verdadera antes de entrar en el bucle
2. la verdad de R se mantiene en cualquier iteración del bucle
3. la condición para salir del bucle siempre se alcanzará en un número finito de iteraciones.

entonces R será verdadera al salir del bucle.

Prueba

La condición de que el bucle termine en un número finito de iteraciones nos permite aplicar inducción matemática siendo la variable de inducción el número de iteraciones. Dejamos los detalles al lector.

Podemos verificar la exactitud del algoritmo de exponenciación rápida utilizando el Teorema de la Relación Invariante. Primero observamos que antes de ingresar al bucle,\(b t^k = 1 a^m = a^m (mod\,n)\text{.}\) Asumiendo que la relación es verdadera al inicio de cualquier iteración, es decir\(\grave{b} \grave{t}^{\grave k} = a^m (mod\,n)\text{,}\) entonces

\ begin {equation*}\ begin {split}\ acute {b}\ acute {t} ^ {\ acute {k}} &\ equiv (\ grave {b}\ grave {t} ^ {\ grave {k}\, mod\ ,2}) (\ tumba t^2) ^ {\ tumba k//2} (mod\, n)\\ &\ equiv\ tumba {b}\ tumba {\ tumba {b}\ tumba {t} ^ {2 (\ tumba {k} //2) +\ tumba {k}\, mod\ ,2} (mod\, n)\\ &\ equiv\ tumba {b}\ tumba {t} ^ {\ tumba {k}} (mod\, n)\\ &\ equiv a^m (mod\ , n)\ end {split}\ end {ecuación*}

Finalmente, el valor de\(k\) disminuirá a cero en un número finito de pasos debido a que el número de dígitos binarios de\(k\) disminuye en uno con cada iteración. Al final del bucle,

\ comenzar {ecuación*} b = b t^0 = b t^k\ equiv a^m (mod\, n)\ final {ecuación*}

que verifica la exactitud del algoritmo.

Ejercicios

Ejercicio\(\PageIndex{1}\)

¿Cómo se relacionan los valores pre y post en el algoritmo de exponenciación lenta? ¿Cuál es la relación invariante entre las variables en el algoritmo lento?

Ejercicio\(\PageIndex{2}\)

Verificar la corrección del siguiente algoritmo para calcular el mayor divisor común de dos enteros que no son ambos cero.

def gcd(a,b):
    r0=a
    r1=b
    while r1 !=0:
        t= r0 % r1
        r0=r1
        r1=t
    return r0
gcd(1001,154)  #test

Insinuación

La invariante de este algoritmo es\(gcd(r0,r1)=gcd(a,b)\text{.}\)

Ejercicio\(\PageIndex{3}\)

Verificar la exactitud del Algoritmo de Conversión Binaria, Algoritmo 1.4.1, en el Capítulo 1.