Loading
Apuntes
Study Reminders
Support
Text Version

Aritmética modular

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Conferencia – 55 Número de teoría Hola a todos. Bienvenidos a esta conferencia. Sólo una rápida recapitulación, en la última conferencia concluimos nuestra discusión sobre la criptografía de clave pública. Así que en esta conferencia la hoja de ruta es la siguiente. (Consulte el tiempo de la diapositiva: 00:29) Básicamente discutiremos algunos de los principales resultados relacionados con la teoría de números que hemos utilizado durante nuestra extensa discusión sobre la criptografía de clave pública. Hago hincapié en que no vamos a tener una discusión en toda regla sobre la teoría de números porque personalmente siento que como; en un curso sobre los fundamentos de la criptografía deberíamos básicamente utilizar los hechos importantes de la teoría de números. Pero pensé que probablemente deberíamos tener una discusión de muy alto nivel sobre algunos de los resultados importantes que usamos extensamente durante nuestra discusión sobre la criptografía de clave pública. Tan motivado por eso tendremos esta discusión; la conferencia de hoy está basada completamente en la teoría de números fueron discutiremos acerca de la aritmética Modular, números Prime y sus propiedades y veremos el algoritmo GCD de Euclides Ampliados. (Consulte el tiempo de la diapositiva: 01:28)Así que comencemos con la aritmética modular. Así que imagina que te dan 2 números o 2 enteros a, N pertenecientes al conjunto de enteros Z. Y aquí N es el módulo donde N > 1. Entonces un mod N se define para ser el resto r, de tal manera que el resto r está en el rango de 0 a N-1, de tal manera que la relación a = q veces N + r se mantiene para algún entero q. Si ese es el caso, entonces decimos que un módulo N es r. Así que por ejemplo, si quiero encontrar 5 modulo 4 entonces 5 modulo 4 es 1, porque si divide 5/4 obtengo el resto 1. De la misma manera, si quiero encontrar -11 módulo 3 entonces -11 módulo 3 es 1 porque 1 está en el rango de 0 a 2 y -11 puede estar relacionado con 3 por esta relación a saber puedo decir que -11 es 3 veces-4 + 1. Resulta que puedo escribir -11 como una combinación lineal de mi módulo 3 en otra forma también, a saber, puedo decir que – 11 = (3 veces – 3)-2. Y por lo tanto uno podría sentir que -11 módulo 3 debe ser-2 pero no es ese caso porque según nuestra definición el resto r debe estar en el rango de 0 a N-1. Es por ello que -11 módulo 3 es 1 y no -2. Ahora tenemos la definición de un módulo N; así que si tenemos dos enteros a y b de tal manera que tanto a como b le da el mismo módulo restante, el módulo N entonces decimos que a es congruente a b y nosotros la notación que un ≡ b módulo N. Así que esto significa que a y b son equivalentes en el sentido de que le da el mismo recordatorio cuando se divide por el módulo N. Así que por la definición de un módulo N resulta que, si a es congruente a b módulo N entonces esto es posible si y sólo si la diferencia de a y b es completamente divisible por N. Porque si a da el resto r módulo N y ya que a es congruente a b módulo N que significa b módulo N es también el mismo recordatorio r y si me resta b de un entonces el resto r y r cancela fuera y lo que obtengo es que a-b es completamente un múltiplo de N y por lo tanto será completamente divisible por N. (Consulte el tiempo de la diapositiva: 03:58) Así que tenemos algunas reglas aritméticas bien conocidas para la aritmética modular. Así, por ejemplo, tenemos dos números a y b y si sé que un módulo N es un’ y b módulo N es b’ entonces puedo decir que un módulo N + b será el mismo valor que el que obtuviste haciendo la operación un’ + b’ módulo N. Lo mismo es cierto para la sustracción, así como para la multiplicación. Así que la forma en que puedes interpretar estas reglas es que puedes imaginar como si primero puedes realizar los modulares o primero puedes hacer el módulo de reducción, el módulo N. Y luego puedes realizar la adición, resta, operación de multiplicación en lugar de sumar o restar o multiplicar y luego hacer el módulo de reducción N. Para ser más específico por ejemplo imagínate que quiero calcular el valor de este número a saber, quiero realizar el producto de 1093028 y 190301 módulo 100. Si quiero calcular este valor, entonces hay dos maneras de hacerlo. La primera manera será que primero realice el producto aquí o primero calcule el producto aquí y luego hago el módulo de reducción 100. Pero esto será una operación complicada porque multiplicar estos dos grandes números será realmente desafiante. No puedo hacerlo fácilmente en un cuaderno. Por otro lado, la misma operación que puedo realizar reduciendo primero los valores individuales aquí es decir, 1093028 y 190301 módulo 100. Y reducir cada uno del módulo 100 es muy sencillo. Porque sólo tengo que centrarme en los dos últimos dígitos aquí que tengo como 28 y 1 y luego puedo multiplicar 28 y 1 y luego volver a reducirlo, reducir el módulo de respuesta 100. Y todo lo obtenido por la opción 1 y el resultado que obtengo por la opción 2 serán los mismos según nuestras reglas de las reglas aritméticas de la aritmética modular. Así que este es un truco muy potente o concepto poderoso aplicable en el contexto de la aritmética modular donde se debe; donde; en lugar de aplicar la operación y luego hacer el módulo modular o de reducción N y primero se puede reducir el módulo de operandos N y luego se puede realizar la operación y si es necesario puede volver a realizar un módulo de reducción N. (Consulte el tiempo de la diapositiva: 06:13) Así hemos visto la adición, la sustracción y el módulo de multiplicación N y qué hay de la división modular. Así que la pregunta es que podemos decir lo siguiente, imaginar un módulo N es un’ y b módulo N es b’ entonces podemos decir que un dividido por b módulo N será el mismo que un’/b’ módulo N. La respuesta es no, porque de hecho en resulta que la operación a dividida por b módulo N no está en absoluto bien definida. Así que para demostrar mi punto imagina mi a y b son 3 y 5 y mi módulo es 4 así que me dan 3 módulo 4 es 3 y 5 módulo 4 es 1 y sé que 3 dividido por 1 módulo 4 lo que me han dado 3 pero si quiero calcular 3 dividido por 5 módulo 4 no tengo la respuesta, porque esta operación 3 dividida por 5 modulo 4 no está en absoluto bien definida. Eso significa en aritmética modular no puedo decir que, si me dan que el producto de ac módulo N y el producto bc módulo N son los mismos. Entonces no puedo decir que cancelar la c de ambos lados y no puede implicarse que un módulo N = b módulo N, que hubiera sido posible si hubiera realizado la misma operación en la aritmética regular y c no; y c no es 0. Eso significa en la aritmética regular si sé que ac = bc y c no es 0 entonces puedo decir que si divide ambos lados por c entonces obtengo un = b. Pero lo mismo no puedo concluir en la aritmética modular porque la división modular no está bien definida. (Consulte la hora de la diapositiva: 07:50) Así que ahora vamos a discutir algunos de los algoritmos para la aritmética modular. Así que imagine que se nos dan dos operandos a y b cada uno de tamaño n-bit y el módulo N cuyo tamaño también es n-bit, y algunas de las operaciones comunes que encontramos en la criptografía de clave pública son para realizar la adición modular, la multiplicación, la sustracción y la exponenciación. Así que recordar la exponenciación modular es una operación muy importante en casi todas las instanciaciones del criptosistema de clave pública, donde nos encontramos con la exponenciación modular. Así que ahora queremos tener algoritmos para realizar estas operaciones aritméticas modulares, tales que los algoritmos resultantes, su complejidad, su complejidad de tiempo debe ser una función polinómica en el número de bits a saber n. Así que resulta que si quiero realizar la adición modular, la sustracción y la multiplicación puedo realizarlos en poli (n) número de operaciones de bits. Pero lo que sobre la exponenciación modular, imagine que quiero computar ab modular N, un algoritmo ingenuo será que realizo a2 módulo N lo que sea el resultado lo multiplique de nuevo con un y hacer un módulo N, y como que tengo que realizar básicamente b-1 multiplicaciones modulares y ya que cada multiplicación modular requiere un número de poli (n) de operaciones y estoy realizando b tal orden de b tales operaciones se puede decir que, la complejidad del tiempo global de este algoritmo de exponenciación modular ingenuo será O (b * poli (n))-bit de operaciones y por lo tanto es polinomio general. Pero eso no es correcto porque lo que es exactamente el valor de b aquí. Tengo que expresar el valor de b también como alguna función de n y resulta que la magnitud de b aquí es una función exponencial en número de bits n. Básicamente b puede ser tan grande como 2n. Eso significa, este ingenuo algoritmo de exponenciación modular; su complejidad de tiempo es función exponencial y el número de bits que necesitas para representar tu a b y el módulo N y por eso es el algoritmo de tiempo exponencial. No podemos utilizar este algoritmo de exponenciación ingenuo para realizar; para calcular ab módulo N. (Consulte Tiempo de diapositiva: 10:16)Por lo tanto ahora lo que vamos a discutir es que veremos un algoritmo de tiempo de poli para calcular las exponencias modulares. Por lo que este método se llama como el método Square y Multiply. Y para demostrar el algoritmo voy a tomar un ejemplo aquí. Quiero computar un a la potencia 53 módulo N. Recuerda, el enfoque ingenuo será multiplicar un 52 veces y cada uno; con cada multiplicación haces una operación mod N. Por lo tanto, básicamente, el enfoque ingenuo requerirá que realice 52 multiplicaciones modulares. Pero lo que vamos a ver aquí es que usando el método cuadrado y multiplique podemos realizar el mismo cómputo con apenas 9 multiplicaciones modulares. Así que la idea detrás de este cuadrado y método de multiplicar es como sigue. Así que expreso mi exponente 53 en este caso en binario. Y dependiendo de la representación del bit de 53 dondequiera que tenga el valor del bit 1 tengo que tomar ese poder de 2. Dondequiera que el poco de poder es 0 tengo que excluir ese poder de 2 y por lo tanto puedo decir que 53 dependiendo de su representación binaria se puede expresar como suma de estos poderes de 2. Y por lo tanto puedo decir que un a la potencia 53 no es más que el producto de algunos poderes selectivos de a a saber un a la potencia 32, a a la potencia 16, a a la potencia 4 y a la potencia 1. Así que la idea detrás de este cuadrado y el método de multiplicar como el nombre sugiere es que en cada iteración vamos a acumular o vamos a calcular los poderes sucesivos de a. Y eso significa, vamos a empezar con una potencia 1 y entonces vamos a ir a un cuadrado entonces de un cuadrado vamos a ir a a la potencia 4 entonces de un a la potencia 4 vamos a ir a a la potencia 8 y así sucesivamente y entonces de forma selectiva dependiendo del bit actual en la representación binaria del exponente a saber 53 en este caso vamos a decidir si acumular el poder actual de un o no, y por eso el nombre de cuadrado y multiplicar. De una manera más detallada imagine que escribo 53 en esta representación binaria de LSB a MSB en este formulario. Y a medida que voy de LSB a MSB los diferentes poderes de un que obtengo a medida que voy de 1 bit actual al siguiente bit es sólo un cuadrado de la potencia anterior, justo y es fácil ver que mi objetivo es calcular un a la potencia 53 y a a la potencia 53 básicamente se puede calcular con sólo multiplicar algunos poderes selectivos de a a saber los poderes de un correspondiente a las posiciones de bit donde en la representación binaria de 53, donde tengo el bit 1. Así que basado en esta idea el algoritmo es el siguiente. Así que establecemos un acumulador aquí que tendrá la respuesta final. La respuesta final que quiero calcular es a la potencia b o a a la potencia 53 en este caso. Así que inicializo mi acumulador para ser 1 y una vez que realice todas las iteraciones mi acumulador tendrá la respuesta final. Así que en cada iteración lo que voy a hacer es, voy a hacer una actualización condicional, a saber, voy a hacer la operación que y = y en el poder actual de un dependiendo de si mi bit actual en el exponente b que estoy explorando ahora mismo es 1 o no. Así que por ejemplo, actualmente empiezo con el LSB de 53 o el exponente b, ahora mismo el bit es 1 que significa que tengo que tomar acumulando este poder y por eso actualizaré mi acumulador por y existente y el poder actual de a y luego voy a la siguiente potencia de a. Y compruebo la posición del bit, la posición de bit es 0; bit es 0 así que no necesito acumular este poder. Entonces voy a la siguiente potencia de un que será un a la potencia 4 y compruebo el bit actual, es uno. Eso significa que tengo que acumular esta potencia, así que por eso actualizaré mi acumulado multiplicando el contenido actual del acumulado con la potencia actual de un. Entonces voy a la siguiente potencia de un que no necesito incluir o acumular porque la posición de bit en el exponente es 0 entonces voy a la siguiente potencia de a y compruebo la posición de bit del exponente en su representación binaria es 1, por lo que tengo que acumular. Y por lo tanto actualizo mi acumulador, y luego finalmente voy a la MSB de la representación de bits de mi exponente, es 1, eso significa que tengo que acumular el poder actual de un y por lo tanto esa es mi respuesta final. Así que no estoy escribiendo el pseudo código exacto aquí. Usted puede entender; espero que usted será capaz de escribir el pseudo código aquí. Pero la idea aquí es que voy a necesitar para realizar una secuencia de iteración, el número de iteraciones no es más que el número de bits que usted necesita para representar su exponente b. Y en cada iteración tenemos que hacer un cuadrante obligatorio para computar la próxima potencia de un. Y una acumulación opcional dependiendo de si el bit actual en la representación binaria del exponente b es 0 o 1 y resulta que en el peor de los casos mi exponente b podría ser tal que todos los bits en su representación binaria es 1, eso significa en el peor de los casos en cada iteración esta acumulación opcional tiene que ser realizada de manera obligatoria. Pero incluso en ese caso el número total de multiplicación modular que terminamos realizando es dos veces n que es una función polinómica en el número de bits que usted necesita para representar su n, su módulo y sus números a y b y por lo tanto este es un algoritmo de tiempo de poli y este es el algoritmo que utilizamos para realizar la exponenciación modular en todos nuestros criptosistemas de clave pública. (Consulte la hora de la diapositiva: 15:33)Ahora vamos a discutir sobre los números primos. Así que la definición de números primos es que un entero p > 1 se llama un número primo si sus únicos factores positivos son el número en sí y 1. Y un número entero positivo mayor que 1 que no es primo se llama como número compuesto. Y un teorema bien conocido de la aritmética que también se llama a menudo como el teorema fundamental de la aritmética es que cualquier número n > = 1 siempre se puede expresar como producto de diferentes poderes de prime y esto es verdad para cada n > = 1. Este es un hecho bien conocido que podemos probar usando la inducción y no entrar en la prueba exacta. Y hay otro hecho bien conocido de la teoría de números que dice que, hay infinitamente muchos primos. No es el caso de que usted tiene sólo número finito de primos. Y de nuevo este teorema podemos probar usando la contradicción o cualquier método a prueba. Así que hay varias pruebas bien conocidas para probar el hecho de que hay infinitamente muchas primes. No voy a entrar en los detalles de la prueba aquí. (Consulte la hora de la diapositiva: 16:39)Por lo tanto, si recuerda que en nuestro criptosistema RSA y también en el contexto del esquema de cifrado Elgamal, básicamente requerimos como parte de la descripción de configuración de un número primo que esté disponible para todas las partes y el número primo debe ser suficientemente grande. Así que la pregunta es cómo escogemos exactamente los números primos. Eso significa, necesitamos un algoritmo para comprobar si un número de n-bit elegido al azar es un número primo o no. Y hay un algoritmo ingenuo para hacer eso. Y el algoritmo ingenuo se basa en el hecho de que si un número p es compuesto entonces tiene al menos uno de los divisores que es menor o igual a   y la prueba de este teorema es muy simple porque si usted tiene todos los divisores de un número compuesto p mayor que  . Decir que tienes dos factores tales a y b y ni a y ni b es menor o igual a y ambos a y b son los factores de p y p es compuesto entonces resulta que el producto ab será mayor que p que es una contradicción. Así que eso significa que si en todo usted tiene un número compuesto p está obligado a tener al menos uno de los factores en el rango 1 a. Y en base a esta observación podemos tener este siguiente algoritmo de Pruebas de Primalidad. Así que imagina que te dan un número p y quieres verificar si el número p es primo o no y decir que el número p es un número de n-bit. Por lo tanto, el algoritmo ingenuo es básicamente comprobar si existen algún divisor i en el rango 2 a   para el número p. Porque si de hecho p habría sido compuesto su límite para tener al menos uno de los divisores en el rango 2 a eso significa que tendrá al menos un divisor i en el rango 2 a y que es lo que está buscando en este algoritmo ingenuo. Resulta que el tiempo de ejecución de este algoritmo es O ( ) divisiones porque está realizando el número de divisiones en este algoritmo. Y puesto que p es n-bit el número de la magnitud de p es 2n así que básicamente usted está realizando 2 a la potencia n/2 divisiones en este algoritmo ingenuo. Y por lo tanto este es un algoritmo de tiempo exponencial que no podemos usar en la práctica para probar si un número determinado p es primo o no, si mi n es suficientemente grande. Así que fue realmente un problema muy difícil verificar si un determinado número p es primo o no en cantidad polinómica de tiempo. De hecho, la gente creía que no es posible llegar con el algoritmo de tiempo de poli para comprobar si un determinado número p es primo o no. Pero la historia se hizo en el año 2002, donde un grupo de científicos informáticos de IIT-Kanpur, a saber, Manindra Agrawal, Neeraj Kayal y Nitin Saxena. Se les ocurrió un algoritmo de tiempo de poli, polinomio en el número de bits que usted necesita para representar con su primer p, o número p. Y surgieron que este algoritmo de tiempo de poli que le dice si un determinado número p es primo o no y que el algoritmo es ahora bien conocido como AKS algoritmo. Por lo tanto, puede utilizar ese algoritmo para comprobar si un número determinado p es primo o no. Pero resulta que no usamos el algoritmo AKS porque a pesar de que es un algoritmo de poli tiempo los polinomios subyacentes son suficientemente grandes y eso nos impide desplegar este algoritmo como es en la práctica. En cambio lo que hacemos en realidad para comprobar si un número determinado es primo o no es que utilizamos un algoritmo que se llama como algoritmo de pruebas de primalidad Miller-Rabin. Y es un algoritmo aleatorio en el sentido de que no siempre se puede confiar en la salida de este algoritmo. En el sentido de que, para los casos del 99,99% le dará la respuesta correcta mientras que hay una pequeña probabilidad de error en la salida de este algoritmo. Eso significa que a pesar de que su entrada puede no ser un número primo que puede terminar etiquetando el número como un número primo. Así que en ese sentido es un algoritmo propenso a errores. Y la razón por la que useMiller-Rabin prueba para comprobar si un número dado es primo o no es que su tiempo de ejecución es super, super rápido en comparación con su algoritmo AKS. Subrayo que el algoritmo AKS es completamente libre de errores. Puede confiar completamente en el resultado proporcionado por el algoritmo AKS porque es un algoritmo determinista. No hay ninguna aleatorización implicada como parte del algoritmo. (Consulte la hora de la diapositiva: 21:08) Ahora vamos a discutir acerca de Greatest Common Divisor o GCD. Así que si a y b son dos no cero entero entonces el GCD de a y b es el mayor entero que es un factor común tanto para un como b. Y si tenemos 2 números o 2 enteros a y b cuyo GCD es 1 entonces decimos que los enteros a y b son coprime. Y si tenemos varios pares de tales números o varios enteros dicen a1 a un nosotros decimos que son par-sabio co-prime o relativamente primo si par-wise los GCD son 1 para cada par de entero ai, aj en la lista. Así que si queremos fuera el GCD de 2 números a y b entonces el algoritmo ingenuo será que primero averigüe la factorización principal de un porque según el teorema fundamental de la aritmética puedo expresar un como el producto de poderes de prime. Y de la misma manera puedo expresar mi número b como un producto de poderes de prime. Y entonces puedo decir que GCD de a y b no es nada sino que tomo los máximos exponentes de la factorización individual individual de a y b y los arregla y eso me dará el GCD de a y b. Pero el problema con este algoritmo es que cómo en primer lugar encuentro la factorización principal de a y b. (Consulte la hora de la diapositiva: 22:31) Por lo tanto, resulta que podemos hacer algo muy interesante aquí. Podemos utilizar un algoritmo eficiente para calcular el algoritmo GCD y este algoritmo se denomina algoritmo GCD de Euclides. Y el algoritmo de base para Euclides es el siguiente hecho. Así que si se le dan enteros a y b de tal manera que a es (b veces q) + r. Y si tu objetivo es encontrar GCD de a y b entonces GCD de a y b no es más que GCD de b y r, si a = (b veces q) + r. Una vez más no estoy dando la prueba de este hecho. Hay que creerme. Pero en base a esto podemos encontrar un algoritmo para calcular el GCD de a y b. Y básicamente, lo que hacemos en este algoritmo es que establecemos mi valor x a a y valor y a b e iterativamente encuentro el valor de x módulo y, pongo mi actual y para ser la siguiente x y tomo el resto de mi actual x módulo y para ser el siguiente y. Y realizo esta operación hasta que mi y se convierta en 0. Tan pronto como mi y se convierta en 0 que eventualmente sucederá, obtengo la x en ese punto para ser el GCD de a y b. Y una corrección de este algoritmo se desprende del hecho de que GCD de a y b serán los mismos que GCD de b y r y GCD de b y r serán los mismos que GCD de r y b módulo r y así sucesivamente. Eso significa que en cada paso estoy básicamente reduciendo el valor de la llamada b y eventualmente se convertirá en 0.Entonces si usted se está preguntando que cuál es la complejidad del tiempo o cuántas divisiones modulares estoy realizando aquí; cuántas operaciones de mod estoy realizando dentro de este algoritmo de Euclides. Puedo llegar con un límite exacto usando el conocido teorema de Lame ’ s que dice que si el GCD de a, b se calcula utilizando el algoritmo de Euclid ’ s y necesita n número de divisiones entonces su b debe ser al menos n + 1o números de Fibonacci a saber b debe ser mayor o igual a f (n + 1), por lo que aquí f (n + 1) denota un número de Fibonacci n + 1 Fibonacci. Si usted se pregunta cuál es el número de Fibonacci, es una secuencia que comienza con 0 el siguiente número es uno. Estos son los dos primeros números de Fibonacci. Y entonces si quiero calcular el valor del número de Fibonacci de ith, el número de Fibonacci de ith es básicamente la suma del número de Fibonacci anterior y luego anterior al número de Fibonacci anterior. Así que esa es mi secuencia de Fibonacci aquí. Así que lo que el teorema de Lame ’ s básicamente dice es que, si el algoritmo GCD de Euclides hubiera realizado n número de divisiones entonces la magnitud de b será al menos tan grande como el número de Fibonacci n + 1. Y también existen límites más bajos conocidos en el valor del número de la nésima Fibonacci. Dice, el límite inferior dice que para cada extremo del valor del número de nth Fibonacci es al menos &alfa; veces n-2 donde &alfa; también se llama como la proporción áurea a saber 1 + 5. 2 Así que basándome en estos dos hechos puedo decir que si mi GCD de a, b necesita n número de divisiones entonces es máximo el n será el máximo cinco veces 10 (b). Por lo tanto, asintóticamente el número de divisiones que necesitamos realizar en este algoritmo es proporcional al número de bits que necesitamos para representar el valor b y por lo tanto el algoritmo general es un algoritmo eficiente. (Consulte la hora de la diapositiva: 25:57)Resulta que podemos utilizar el algoritmo GCD de Euclides para hacer algo más. Así que para entender que primero voy a aquí Bezout ’ s teorema aquí. Así que lo que dice el teorema de Bezout es que, siempre se puede expresar el GCD de dos números a y b como la combinación lineal de los números a y b. Eso significa que siempre se puede llegar, siempre se puede encontrar combinador lineal s y t, de tal manera que usted puede expresar las entradas a y b como una combinación lineal que le dará el GCD de a y b. Esto significa que el GCD de a y b se puede expresar siempre como una combinación lineal de las entradas a y b donde los combinadores s y t siempre existe. Y si usted se está preguntando cómo exactamente usted puede encontrar estos coeficientes de Bezout ’ s y t o los combinadores s y t donde se puede hacer eso mediante la realización de algunos libros de contabilidad extra o mantener algunas variables adicionales en el algoritmo de Euclides. Y este algoritmo ampliado donde se realiza la actividad de contabilidad adicional para averiguar los combinadores lineales s y t también se conoce como el algoritmo de Euclides ampliado s. Así que no voy a entrar en los detalles completos de cómo exactamente esta contabilidad adicional sucede en el algoritmo de Euclides. Permítanme que lo demuestre. Por lo tanto, supongamos que desea averiguar los coeficientes de los combinadores lineales o Bezout ’ s para que los números sean 252 y b sean 198. Así que si ves la forma en que funcionará el algoritmo GCD, el algoritmo GCD de Euclides funcionará para que la entrada sea de 252 y b para ser 198 es la siguiente. En la primera iteración tu a será 252, b será 198 y obtendrás el valor de 252 módulo 198. En la siguiente iteración, su a se convertirá en 198 y su b se convertirá en el resto actual 54 y así sucesivamente. Y usted hace esta operación hasta que su resto se convierta en 0. Y cuando su resto se convierte en 0, usted sabe que 18 es su GCD. Así que ahora su objetivo es encontrar los combinadores lineales para que usted pueda representar el GCD 18 como la combinación lineal de 252 y 198. Y para eso lo que podemos hacer es que podemos volver a rastrear aquí y podemos ver que puedo reescribir 18 para ser; basado en esta ecuación, puedo reescribir 18 para ser 54 veces 1-36. Y si vuelvo una vez por arriba, entonces sé que mi 36 no es más que 198-3 veces 54. Así que si vuelvo aquí y sustituyo el valor de 36 aquí, entonces obtengo que 18 puede ser reescrito como una combinación lineal de 54 y 198, pero ese no es mi objetivo. Lo que puedo hacer es volver a dar un paso hacia arriba y puedo reescribir mis 54 como una combinación lineal de 252 y 198. Y si sustituyo esa combinación lineal en esta última ecuación termino consiguiendo que 18 esté representado como una combinación lineal de 252 y 198, eso significa que mis coeficientes de Bezout ’ s son 4 y-5. Así que en esta demostración en realidad para encontrar los coeficientes de Bezout ’ s hice un seguimiento de fondo, pero en el algoritmo de Euclides en realidad que necesita sólo para el pase hacia adelante, no es necesario hacer una pista de fondo en, hacer la contabilidad y averiguar los coeficientes de Bezout ’ s. (Consulte la hora de la diapositiva: 29:21)De modo que el algoritmo GCD de Euclides ampliado será útil. Por lo tanto, será útil calcular el módulo inverso multiplicador N. Así que recuerde cómo lo hizo; la forma en que definimos la operación de módulo N multiplicativo. Así que a * b módulo N se define al recordatorio de a en b módulo N y recuerda que definimos un entero b para ser el inverso multiplicativo de un módulo N si el producto de a y b módulo N te da 1. Y utilizamos la notación b = a-1 para denotar el inverso multiplicativo de un módulo N y el hecho básico aquí es que si b es inverso multiplicativo de un módulo N entonces a es también el inverso multiplicativo de b módulo N y resulta que si de hecho tenemos un inverso multiplicativo de un módulo N, a saber si tienes b tal que a veces b módulo N es 1 entonces es b + cualquier múltiplo del módulo N. Eso significa que no importa si se añaden múltiplos de módulo N a b o se restan múltiplos de módulo N de b todos ellos también será el inverso multiplicativo de un módulo N y esto es debido al hecho de que a veces b +-k veces N termina hacia arriba como la combinación lineal de a y N utilizando los combinadores s y t. Y ahora si tomo mod N en ambos lados de esta ecuación entonces en el lado derecho obtengo un módulo N y 1 módulo N me dará 1. Pero mi lado izquierdo es decir un tiempo s + N veces t módulo N me dará un módulo N veces s porque N veces t módulo N me dará 0 porque es el múltiplo de N. Así que lo que obtengo al tomar mod N en ambos lados es que obtengo la relación que a veces s módulo N = 1 que muestra que s es en realidad el inverso multiplicativo de un módulo N. Y así es como podemos obtener el; o se puede computar el inverso multiplicativo de un número a si es co-prime a N. Así que eso me lleva al final de esta conferencia. Sólo para resumir y esta conferencia acabamos de discutir sobre un muy alto nivel algunos de los básicos; algunos de los hechos importantes de la teoría de números que hemos utilizado extensamente durante nuestra discusión sobre la criptografía de clave pública. En concreto, vimos; discutido sobre la aritmética modular. Vimos un algoritmo de tiempo de poli para calcular la exponenciación modular que es una operación clave que realizamos en cualquier criptosistema de clave pública o cualquier algoritmo de cifrado en el criptosistema de claves públicas. También discutimos acerca de una prueba de Primalidad, propiedades de número primo. Y también discutimos sobre el algoritmo ampliado de Euclides para calcular el GCD de dos números y calcular los coeficientes de Bezout ’ s será útil para calcular el inverso multiplicativo de los números.