¿Cómo pueden las computadoras calcular matemática exponencial sin errores de desbordamiento?

Al estudiar algunos métodos de cifrado / descifrado RSA, encontré este artículo: Un ejemplo del algoritmo RSA

Requiere esto para descifrar este mensaje

El resultado total de es tan grande, para una máquina de 64 bits / 32 bits, no creo que pueda tener un valor tan grande en un registro. ¿Cómo lo hace la computadora sin un desbordamiento?

Esta pregunta fue una pregunta de superusuario de la semana .
Lea la entrada del blog para más detalles o contribuya al blog usted mismo

Debido a que la operación de módulo entero es un homomorfismo de anillo ( Wikipedia ) de ℤ -> ℤ / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Puede verificar esto usted mismo con un poco de álgebra simple. (Tenga en cuenta que la final moden el lado derecho aparece debido a la definición de multiplicación en un anillo modular).

Las computadoras usan este truco para calcular exponenciales en anillos modulares sin tener que calcular una gran cantidad de dígitos.

               / 1 I = 0,
               El |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI impar,
               El |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI incluso & I / = 0.

En forma algorítmica,

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Puede usar esto para calcular (855^2753) mod 3233con solo registros de 16 bits, si lo desea.

Sin embargo, los valores de X y N en RSA son mucho más grandes, demasiado grandes para caber en un registro. ¡Un módulo suele tener una longitud de 1024-4096 bits! Entonces, puede hacer que una computadora haga la multiplicación de la manera "larga", de la misma manera que hacemos la multiplicación a mano. Solo que en lugar de usar dígitos 0-9, la computadora usará "palabras" 0-2 ¹⁶ -1 o algo así. (El uso de solo 16 bits significa que podemos multiplicar dos números de 16 bits y obtener el resultado completo de 32 bits sin recurrir al lenguaje ensamblador. En lenguaje ensamblador, generalmente es muy fácil obtener el resultado completo de 64 bits, o para una computadora de 64 bits , el resultado completo de 128 bits).

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Esto multiplicará X por Y en una cantidad de tiempo aproximadamente igual al número de palabras en X multiplicado por el número de palabras en Y. Esto se llama tiempo O (N ² ). Si observa el algoritmo anterior y lo separa, es la misma "multiplicación larga" que enseñan en la escuela. No tiene tablas de tiempos memorizadas con 10 dígitos, pero aún puede multiplicar 1,926,348 x 8,192,004 si se sienta y trabaja.

Multiplicación larga:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

En realidad, existen algunos algoritmos más rápidos para la multiplicación ( Wikipedia ), como el método de Fourier rápido de Strassen, y algunos métodos más simples que suman y restan extra pero menos multiplicación, y así terminan más rápido en general. Las bibliotecas numéricas como GMP son capaces de seleccionar diferentes algoritmos en función de qué tan grandes son los números: la transformación de Fourier es solo la más rápida para los números más grandes, los números más pequeños usan algoritmos más simples.

La respuesta simple es que no pueden, no solos. De hecho, si toma el concepto de una máquina de x bits, entonces hay un número limitado de números que se pueden representar por un número limitado de bits, al igual que hay un número limitado de números que se pueden representar por 2 dígitos en El sistema decimal.

Dicho esto, la representación por computadora de números muy grandes es un componente importante del campo de la criptografía. Hay muchas formas de representar números muy grandes en una computadora, cada una tan variada como la siguiente.

Cada uno de estos métodos tiene diferentes ventajas y desventajas, y aunque no enumero / no puedo enumerar todos los métodos aquí, presentaré uno muy simple.

Supongamos que un entero solo puede contener valores de 0-99. ¿Cómo podría uno representar el número 100? Esto puede parecer imposible al principio, pero eso se debe a que solo consideramos una sola variable. Si tuviera un entero llamado unitsy una llama hundreds, que fácilmente podría representar 100: hundreds = 1; units = 0;. Yo podría representar un número mayor, como 9223: hundreds = 92; units = 23.

Si bien este es un método fácil, se puede argumentar que es muy ineficiente. Al igual que la mayoría de los algoritmos que empujan los límites de lo que una computadora puede hacer, generalmente es una guerra de tirones entre el poder (representan grandes cantidades) y la eficiencia (recuperación / almacenamiento rápido). Como dije antes, hay muchas formas de representar grandes números en las computadoras; ¡solo encuentra un método y experimenta con él!

¡Espero que esto haya respondido a tu pregunta!

Otras lecturas:Este artículo y este pueden ser útiles para obtener más información.

La forma en que esto se puede hacer (hay formas mucho más rápidas que involucran la cuadratura repetida y similares) es multiplicando, y después de cada multiplicación, tome el módulo. Mientras el módulo al cuadrado sea menor que 2 ^ 32 (o 2 ^ 64), esto nunca tendrá un desbordamiento.

De la misma manera que puedes.

Supongo que no sabes de antemano qué es 342 * 189. Pero sí conoce los siguientes hechos:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Al conocer estos simples hechos y al haber aprendido una técnica para manipularlos, puede hacer operaciones aritméticas que de otro modo no podría.

Del mismo modo, una computadora que no puede manejar más de 64 bits de matemáticas a la vez puede dividir fácilmente los problemas más grandes en partes más pequeñas, hacer esas piezas más pequeñas y volver a unirlas para formar la respuesta a las más grandes, previamente problema sin respuesta

En cuanto a la suma y la resta, muchas CPU tienen un "bit de acarreo" que se establece si la operación aritmética se ha desbordado. Entonces, si un resultado requerirá 8 bytes para almacenar, y la CPU es de 32 bits (que equivale a 4 bytes de 8 bits), puede realizar dos operaciones de adición, primero en la "palabra baja" y luego en la "palabra alta" con la broca de transporte cuidando el desbordamiento. Necesario para limpiar el bit de transporte primero. Esta es una de las razones por las que las CPU de bits más altos aumentan el rendimiento porque esto no tiene que hacerse tanto.

Por supuesto, esto es de mi limitada experiencia de ensamblador con CPU de 8 bits. No sé cómo funciona el bit de acarreo con CPU modernas con instrucciones de multiplicar y dividir. Las CPU RISC que no son Intel también pueden comportarse de manera diferente.

No sé mucho sobre matemáticas de punto flotante, pero básicamente los bytes representan un número fijo de lugares, pero no lugares específicos. Por eso se llama punto "flotante". Entonces, por ejemplo, el número 34459234 consumiría aproximadamente el mismo espacio de memoria que 3.4459234, o 3.4459234E + 20 (eso es 3.4459234 x 10 ^ 20).