Grupos cíclicos | Introducción | Alison
Loading
Apuntes
Study Reminders
Support
Text Version

Introducción a los grupos cíclicos

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

    +

Fundamentos de la Criptografía Prof. Ashish Choudhury Departamento de Informática Instituto Indio de Ciencia – Conferencia de Bangalore-38 Grupos cíclicos Hola a todos. Bienvenidos a esta conferencia. (Hora de la diapositiva: 00:30) El plan para esta conferencia es el siguiente. En esta conferencia introduciremos el concepto de grupos cíclicos. Usted verá varias definiciones y propiedades y la razón por la que estamos interesados en estudiar los grupos cíclicos es que más adelante vamos a introducir algunos supuestos de dureza criptográfica en el contexto de grupos cíclicos que nos ayudarán aún más a diseñar o desarrollar las ideas básicas que se utilizan para diseñar el Diffie – Hellman Key Exchange Protocol. (Consultar tiempo de la diapositiva: 01 :00) Así que recuerde el abstracto Diffie – Hellman Key Exchange Protocol que hemos explicado suponiendo que tenemos algunas funciones especiales E y F. Sólo para recordar qué es exactamente el requisito de la función E y F fueron, bien necesitamos las siguientes propiedades: necesitamos que la función E debe ser fácil de calcular para cualquier entrada. También necesitamos que si se le da cualquier α del dominio de E y una salida de función E (β), entonces sin conocer el valor β debería ser fácil calcular el valor de la función F en el par de entrada (α, β) y esto debería contener cualquier (α, β). Si desea lograr una privacidad débil, entonces la propiedad que requerimos aquí de la función E y F es que para cada aleatorio (α, β) Debe ser difícil calcular el valor de F (α, β) si se le acaba de dar el valor de E (α) y E (β). Mientras que para una privacidad fuerte necesitamos que el valor de F (&alp;, β) debe ser computacionalmente indistinguible de cualquier valor aleatorio del codominio, incluso si conoce el valor de E (α) y conoce el valor de E (β). Ahora la pregunta es ¿cómo crear una instancia de esta función E y F? Podría ser como sigue: así que imaginemos que tomamos la exponenciación a la base pública g. Por lo tanto, usted asume que g es una base fija públicamente conocida y podemos tomar la función de candidato E para ser la siguiente: E (&alfa;) se define como esta base g α y esta función F (α, β) se puede definir como la exponenciación de esto con respecto a esta base g y una potencia de exponenciación de potencia es &alfa; times β. Así que es mi candidato F (α, β). Ahora es fácil ver que si defino mi función E y la función F así. Entonces soy capaz de satisfacer uno de los requisitos de la función E y F que estoy interesado en. Es decir, si me dan E (&alfa;) y si quiero calcular F (α, β) entonces lo que tengo que hacer es simplemente plantear que E (&alfa;) β que me dará el valor de F (α, β). De la misma manera si poseo E (β) y no sé β, sólo conociendo α y E (β) Puedo calcular F (α, β) elevando el valor E (β) α. Así que eso satisface uno de los requisitos clave que necesito de mi función E y función F, pero resulta que tomar esta exponenciación de entero no es suficiente para crear una instancia de que abstract Diffie – Hellman Key Exchange Protocol porque hay varios otros problemas de seguridad con esta función E y F. El primer problema importante es que es la función E no es una función candidata unidireccional y ver que imagina que conoces la descripción de la base g y sabes el valor de E (&alfa;) A saber, g &alfa; y su objetivo es averiguar el &alfa; entonces es muy fácil calcular el α desconocido simplemente tomando el logaritmo natural. Y calcular el logaritmo natural es una tarea computacionalmente fácil. Así que la función E en el primer lugar en sí no es una función unidireccional y eso significa que no puedo lograr estas nociones de privacidad débil y privacidad fuerte. No sólo la función E es una función unidireccional, el problema aquí es que no puedo utilizarlo con fines prácticos. No puedo utilizar esta función de candidato E y la función de candidato F con fines prácticos porque aquí mis α y β pueden ser enteros arbitrarios. Mientras que si quiero instanciar e implementar esta función E y F, no puedo trabajar en una función o dominio en el rango que consiste en números enteros arbitrarios y que podría ser de tamaño infinito. Más bien estaremos interesados en trabajar en dominios que son finitos en la naturaleza por lo que ahora vamos a tratar de buscar las funciones de E y F candidatos que no son sólo funciones unidireccionales y no sólo satisface el requisito en las funciones E y F que necesitamos para este abstracto Diffie – Hellman Key Exchange Protocol, pero también estamos interesados en que esas funciones deben ser de un dominio algebraico finito apropiado. Para eso ahora tenemos que recordar la teoría de grupos que habíamos visto cuando construimos nuestra información de MACs teóricos, a saber, cuando construimos la función universal. Así que permítanme pasar rápidamente por la definición de grupos. Así que un grupo que denoté por este símbolo es un conjunto con una operación apropiada sobre los elementos del conjunto y decimos que se establece (es un grupo si satisface los siguientes axiomas, es decir, debe satisfacer la propiedad de cierre que establece que para cada,, el elemento. La segunda propiedad es que la operación debe satisfacer la propiedad de asociatividad, es decir, para cada,,, () = (). Necesitamos la existencia de un elemento de identidad, a saber, debe existir un elemento único que denoté como e en el conjunto de tal manera que, tal que para cada. Usted debe tener un elemento inverso para cada elemento en el conjunto, es decir, para cada elemento a del conjunto debe existir un elemento único que denotan por un -1 tal que a -1 = a -1 = sostiene. Subrayo que este elemento a -1 no significa el 1/a numérico. Es sólo una interpretación o sólo una notación para el elemento inverso especial correspondiente al elemento a que necesito de mi conjunto. Así que, de nuevo sólo para recordar que también habíamos visto algunos ejemplos de grupos. El conjunto de enteros (Z, +) constituye un grupo abeliano. ¿Qué es un grupo abeliano? Un grupo abeliano es un grupo especial que satisface todos los axiomas del grupo y encima de eso debe satisfacer la propiedad conmutativa. Es decir, su operación debe satisfacer la propiedad conmutativa y es fácil ver que el conjunto de enteros junto con esta operación + que satisface los axiomas del grupo. Si usted toma cualquier 2 enteros añadirlos, usted obtiene un entero, la adición es asociativo, 0 es el elemento de identidad porque si usted añade 0 a cualquier entero que obtenga ese entero. Si toma cualquier entero a, el inverso correspondiente es – a. Mientras que resulta que el conjunto de números naturales no forma un grupo con respecto a la operación + porque no tenemos el aditivo inverso. Debido a que el aditivo inverso del elemento, digamos 2 es – 2, pero -2 no pertenece al conjunto de números naturales. De la misma manera el conjunto de números reales no cero R − {0} forman un grupo con respecto a la operación de multiplicación porque la multiplicación de 2 números reales te da un número real, por lo que el cierre está satisfecho, la multiplicación es asociativa, el elemento 1 es el elemento de identidad. Para cada elemento distinto de cero a, el inverso correspondiente es el número 1/a porque el número real multiplicado por 1/a inverso le dará el elemento de identidad 1 y es por eso que el conjunto de números reales no cero forma un grupo. (Consultar tiempo de la diapositiva: 08:59) Ahora estamos interesados en tipos especiales de grupos a los que llamamos grupos cíclicos. Entonces, ¿vamos a ver qué es exactamente un grupo cíclico? Un grupo con respecto a una operación o se llama un grupo cíclico de orden q si las siguientes condiciones se mantienen: en primer lugar, (, o) debe satisfacer los axiomas del grupo, es decir, el cierre, la propiedad asociativa, la existencia de la identificación, la existencia de la inversa para cada elemento del grupo. Si es un grupo abeliano entonces está bien, pero no necesitamos que sea un grupo abeliano. Tan pictorialmente imaginan que tenemos ciertos elementos de este set y esta operación o satisface todos los axiomas de este grupo. El segundo requisito apropiado aquí es que puesto que estoy diciendo que el grupo es un grupo cíclico de orden q. Por orden q, quiero decir que hay q número de elementos en mi set. Por lo tanto, eso es lo que quiero decir con el orden del grupo de ser q. ¿Y por qué se llama grupo cíclico? Se llama un grupo cíclico porque necesito un elemento especial que yo llamo un generador que denotan por decir g. Este g debe ser uno de los elementos de este conjunto de tal manera que todos los elementos del conjunto pueden ser generados por este elemento especial g por diferentes potencias. Aquí “ poderes ”, será claro para ustedes muy pronto lo que quiero decir exactamente por poderes aquí. Básicamente, la idea aquí es que este elemento especial g que llamo como generador tiene la capacidad, tiene la capacidad de generar todos los elementos en su conjunto. Si tengo al menos un elemento generador especial de este tipo que yo llamo como generador, entonces mi grupo es llamado como un cíclico, pero no tengo ningún elemento especial g entonces mi grupo no se llama un grupo cíclico. Así que, déjenme explicarles qué es exactamente lo que quiero decir al generar diferentes elementos por diferentes poderes del generador de elementos. Así que dejar p ser un primo y definir un conjunto Zp * que consiste del elemento 1 a p – 1 y ahora déjenme definir una operación de multiplicación que es diferente de la multiplicación aritmética normal por lo que la operación que voy a definir es se denota por .p y que también se llama como módulo de multiplicación p. La forma en que se va a realizar esta multiplicación es la siguiente: Si tomo alguno 2 elementos a, b del conjunto Zp * entonces el módulo de multiplicación p de a y b es el mismo que se multiplica a y b numéricamente y se lleva el recordatorio con respecto al módulo p. Cualquier recordatorio que obtenga que será un número en el rango de 0 a p-1 y esa es la forma en que definimos esta operación de módulo de multiplicación. Ahora voy a declarar un resultado que es un resultado estándar que sigue de la teoría de números. No voy a demostrar eso, pero si usted está interesado en la prueba de este teorema entonces usted puede referirse a cualquier referencia estándar de la teoría de números. Así que el teorema básicamente afirma que para cada número primo p el conjunto Zp * junto con el módulo de multiplicación de la operación p es un grupo o constituye un grupo que consta de p – 1 elementos. Eso significa que la orden del grupo es p – 1. Así que no vamos a demostrar eso, pero voy a demostrar que de hecho esto es cierto si p es su mejor. Así que estoy tomando p = 5 aquí y Z5 * básicamente consisten en elementos {1, 2, 3, 4}. Así que lo que he hecho es a lo largo de las filas que he escrito el elemento 1, 2, 3, 4 y a lo largo de las columnas he denotado los elementos 1,2, 3, 4 y esto es como una matriz aquí. Y lo que he hecho aquí es (i, j) la entrada denota los resultados de (i. j) módulo 5 aquí. Si considero esta entrada, este es el resultado de (2. 2) módulo 5. De la misma manera (4. 3) el módulo 5 te va a dar 2 y demás. Por lo tanto, puede ver desde esta matriz que su propiedad de cierre está satisfecha. Usted toma cualquier i y cualquier j en el rango que pertenece a Z5 * y realizar la operación (i. j) módulo 5, usted va a obtener el número en el rango de 1 a 4. La operación de multiplicación que hemos definido aquí satisface la propiedad de la asociatividad que significa que si tomo (i, j) la entrada, entonces no importa en qué orden voy a multiplicar (i, j) la entrada y tomar el módulo 5, voy a obtener el mismo recordatorio. El elemento identity es el elemento 1 aquí porque si ves esta matriz aquí y si te centras en la columna bajo 1 aquí entonces bajo ese 1, 1 punto 1 módulo 5 te da 1, 2 punto 1 módulo 5 te da 2, 3 punto 1 módulo 5 te da 3 y 4 punto 1 módulo 5 te da 4. Así que el elemento 1 sirve como elemento de identidad aquí. Ahora bajo cada elemento tendrás el correspondiente elemento inverso. Así que el inverso de 1 es 1 aquí porque 1 punto 1 te da 1. El inverso de 2 es 3 porque 2 punto 3 módulo 5 le da el elemento de identidad 1, el inverso de 3 es 2 porque 3 punto 2 módulo 5 le da el elemento de identidad 1 e inverso de 4 es 4 porque 4 punto 4 módulo 5 le da el elemento de identidad 1. Así que tienes todos los axiomas satisfechos y ahora puedes ver, tienes algunos elementos generadores especiales presentes aquí también. Voy a demostrar eso también. Antes de entrar en si el elemento generador aquí existe o no, déjenme definir primero lo que queremos decir por la exponenciación de grupo en este set Zp *. Para cualquier elemento g que pertenezca a set Zp *, defino g0 como 1. Y defino g 1 to be g porque de hecho g0 módulo p vas a obtener 1 módulo p que es igual a 1 y g 1 si g es un elemento de Zp *. Por supuesto, es menor que p y si se hace g1 y luego tomar mod p entonces el efecto de mod p no afecta. Usted sólo va a obtener g. Mientras que yo defino g i a ser la operación del módulo de multiplicación aplicado i – 1 veces. Y resulta que no importa si tomo el recordatorio al final o si tomo en recordatorio después de realizar cada individuo. p operación i – 1 veces, los resultados serán los mismos porque viene de la propiedad de asociatividad de mi grupo Zp *. Así que puedo definir a gi para que sea el mismo que usted realiza el gi numérico y luego usted toma un mod final p para traer de vuelta el resultado en el rango de 0 a p – 1. Por lo tanto, debido a la forma en que gi se define para el caso i a ser 0, yo para ser 1 y yo para ser un genérico i, puedo decir que puedo definir mi gi. Puedo utilizar la notación gi en el conjunto Zp * para denotar el valor numérico gi módulo p así que es una notación que voy a utilizar aquí y que es lo que quiero decir por la potencia de un elemento g en el conjunto Zp * aquí. Así que de nuevo voy a declarar otro resultado bien conocido de la teoría de números que establece que para cada número primo p, existen por lo menos a un elemento g en el conjunto Zp * tal que cuando se calcula cuando se eleva g a diferentes poderes y realizar la operación de módulo p a saber, se g0 mod p, g1 mod p hasta gp – 2 mod p, entonces usted va a obtener todos los elementos en el conjunto Zp * en algún orden arbitrario. Eso significa p – 1 poderes distintos de este elemento especial g va a darle todos los elementos en Zp * y eso significa que tiene al menos un generador presente en este set Zp *. Eso es lo que quiero decir al generar todos los elementos del conjunto por diferentes potencias. Su aquí en este ejemplo en particular es Zp * y la afirmación de la teoría de números es que existen por lo menos un elemento en esta Zp * de tal manera que si usted eleva g a los diferentes poderes aquí y realizar la operación de grupo, a saber, la operación de multiplicación de módulo p que va a obtener todos los elementos de Zp *. Una vez más no estoy dando una prueba de esto, pero si usted está interesado en la prueba usted puede ver cualquier referencia estándar. Veamos si este teorema se sostiene para el ejemplo actual que estamos considerando aquí. Así que si tomo el elemento 2 que es un elemento de Z5 * y realizar 20 módulo 5, 21 módulo 5, 22 módulo 5 y 23 módulo 5, voy a obtener los elementos 1, 2, 4, 3 respectivamente. Así que note que no estoy obteniendo todos los elementos de Z5 * en el orden exacto. Pero estoy obteniendo todos los elementos en algún orden arbitrario. Así que para la definición de grupo cíclico, el requisito es que las diferentes potencias de g deben darle a todos los elementos de ese conjunto en cualquier orden arbitrario. El orden no importa aquí. De la misma manera el elemento 3 también es un elemento especial aquí porque 30 módulo 5, 31 módulo 5, 32 módulo 5 y 33 módulo 5 le va a dar el elemento 1,3, 4, 2 a saber todo el Z5 *. Pero si tomo el elemento 4 y intento levantar o computar diferentes potencias de 4, no soy capaz de generar todos los elementos de Z5 *. Podría generar solo los elementos 1 y 4. Así que desde el resultado de la teoría de números que estoy diciendo aquí afirma que tengo algún elemento especial g que tiene la capacidad de generar todo el conjunto Zp *. Eso significa que el conjunto Zp * junto con este módulo de multiplicación p operación es un grupo cíclico de orden p – 1. Porque tiene p – 1 elementos y de hecho en este ejemplo 2 es el de los generadores de Z5 *, 3 es también uno de los generadores de Z5 *, pero 4 no es un generador de Z5 *. Ahora usted podría estar pensando que por qué el nombre cíclico aquí. La razón por la que lo estoy llamando cíclico porque tan pronto si usted tiene un generador g decir por ejemplo para el grupo Zp*y luego si usted calcula la potencia siguiente de g a saber g p – 1 usted va a obtener uno de los elementos que ya está allí en Zp *. Básicamente, sólo obtendrá el elemento g0. Así que de nuevo la prueba para eso sigue de la teoría de números, pero no voy a demostrar que si usted calcula g p – 1 obtendrá el mismo valor que g 0. La siguiente potencia de g le dará g1 y así sucesivamente. En ese sentido es cíclico que significa que tan pronto se sube al límite gp – 2, y si vas a empezar a tomar la siguiente secuencia de poderes de g comenzarás a recuperar el mismo ciclo. Usted obtendrá los mismos elementos de Zp * y seguirá sucediendo y es por eso que el nombre de grupo cíclico. Por lo tanto, los grupos cíclicos, sólo para resumir los grupos cíclicos son tipos especiales de grupo que tiene al menos un generador. (Ver Diapositiva: 20 :59) Por lo tanto, el grupo Zp * con respecto a la operación de multiplicación de módulo p constituye el grupo cíclico multiplicativo porque allí la operación fue multiplicación. No fue la multiplicación natural. No era la multiplicación entera, pero podría ser interpretada como una operación multiplicativa. Resulta que también podemos definir grupos cíclicos basados en la noción de operación de adición y hagamos eso. Por lo tanto, dejar p ser un prime y definir un conjunto Zp para ser el conjunto de enteros 0 a p – 1. Así que la diferencia entre Zp * y Zp es que el elemento 0 no está allí en Zp *, pero el elemento 0 ahora está permitido en Zp. Ahora déjenme definir una operación de adición en este conjunto Zp que llamo como módulo adicional p denotado por este símbolo + p y el módulo de adición p de algún par de números a, b del conjunto Zp no es más que realizar la adición numérica o entera a y b y tomar el módulo p. De modo que el resultante es un elemento en el conjunto 0 a p – Así que de nuevo tomemos un ejemplo aquí el conjunto Z5 consiste en el entero {0, 1, 2, 3, 4} y lo que he hecho aquí es que he hecho la matriz que denota el resultado de realizar la operación + módulo 5 en cualquier par de elementos en el conjunto Z5. Una vez más, hay un hecho bien conocido de la teoría de números que afirma que si usted toma cualquier primer p entonces el conjunto Zp junto con el módulo de adición de operación p constituye un grupo. Pero ahora el orden del grupo es primordial a saber que tiene p número de elementos porque ahora está teniendo el elemento 0 a p – 1, mientras que el conjunto Zp * era un grupo multiplicativo de orden p – 1. Así que ahora vamos a ver cómo podemos interpretar la exponenciación del grupo en este grupo de aditivos. Así que definimos 0 veces g para ser 0 y definimos una vez g para ser g donde g es cualquier elemento en el conjunto Zp. Mientras que i veces g se define como el resultado de esta adición de módulo p operación que se aplica en el elemento g, i – 1 veces. Resulta que no importa si tomo el mod en el último o si tomo el mod después de cada operación + el resultado va a ser el mismo porque eso sigue de la propiedad de asociatividad de la operación + y por lo tanto puedo decir que los tiempos g es lo mismo que la multiplicación entera de i y g módulo p. Así que cuando digo que veces g que no significa que estoy multiplicando i y g, i veces g es la notación que he seguido por g y seguido por g es lo mismo que la multiplicación entera de i y g módulo p. Así que basado en estas 3 maneras o la forma en que este grupo exponenciación se define con respecto a esta operación + puedo utilizar la notación que yo. g es igual a la multiplicación entera de i y g módulo p. Y de nuevo hay un resultado bien conocido de la teoría de números que afirma que para cada primer p existe por lo menos un elemento especial g en el conjunto Zp tal que 0 veces g, 1 veces g hasta p – 1 veces g es decir, el p – 1 poderes distintos de g va a devolver todos los elementos del conjunto Zp en algún orden arbitrario. Así que ahora aquí la exponenciación se trata básicamente como si se quiere calcular g x. Básicamente, g x aquí se interpreta como si usted está realizando el + módulo p operación x – 1 número de veces. Así que es la interpretación del poder de g cuando estoy considerando la operación del grupo subyacente en los conjuntos de aditivos. Así que de nuevo, en el contexto de Z5 el elemento 1 resulta ser un elemento tan especial donde todas las diferentes potencias de 1 le va a devolver todos los elementos de Z5. Lo mismo tiene para 2, así que diferentes potencias de 2 le va a devolver todos los elementos de Z5. Eso significa que el conjunto Zp junto con la operación + módulo p es un grupo cíclico de orden p. Así que habíamos visto ejemplos de grupos cíclicos basados en la operación de multiplicación. (Consulte el tiempo de la diapositiva: 25 :26) Así que hemos visto ejemplos de grupos cíclicos basados en la operación de adición. Ahora vamos a definir lo que queremos decir por la exponenciación del grupo en los grupos cíclicos abstractos. Así que por explicación estoy asumiendo que mi es un grupo abstracto donde la operación subyacente es una operación multiplicativa. No necesita ser una multiplicación de enteros, pero puede interpretarse en el sentido multiplicativo y tiene un orden q es decir tiene q números de elementos. Dado que es un grupo abstracto, denoté que el elemento de identidad sea e y que g sea un elemento de este grupo. Entonces utilizamos la siguiente notación. Así que ya que estamos utilizando la notación multiplicativa aquí para ese grupo abstracto, usaré la notación g0 para denotar el elemento identity y g1 para denotar el elemento identity. Y la notación gi para denotar el elemento que obtengo componiendo o realizando la operación de grupo en el elemento g, i – 1 número de veces. Subrayo que esta notación es completamente diferente de la exponenciación entera. Esto es sólo una notación, gi no significa que estoy multiplicando g, i – 1 veces. Es básicamente sólo una notación que solía representar que estoy realizando la operación de grupo en el elemento g, i – 1 número de veces. Sin embargo, resulta que las reglas de la exponenciación de enteros siguen siendo aplicables en este grupo multiplicativo abstracto. A saber, si tomo el elemento de grupo gm que es básicamente el elemento g compuesto a sí mismo m – 1 números de veces según la operación del grupo y tomo el otro elemento del grupo decir g n que es el elemento del grupo g compuesto a sí mismo n – 1 número de veces. A continuación, si realizo la operación de grupo en estos 2 elementos, el resultado será el mismo que el elemento g que se compone m + n – 1 número de veces. De la misma manera, si tomo el elemento gm y realizo la operación de grupo en ese elemento n – 1 número de veces entonces obtendré el mismo resultado que obtengo al realizar la operación de grupo en el elemento g, m + n – 1 número de veces y así sucesivamente. Por otra parte, si este elemento g es un grupo cíclico entonces resulta que las diferentes potencias de g y otra vez por diferentes poderes de g no me refiero a la exponenciación entera. El poder por diferentes poderes de g significa la definición de la exponenciación del grupo en ese sentido abstracto. Así que si este g es un generador entonces diferentes poderes de g que van desde el poder 0º a la q – 1 ° poder me va a devolver todo el elemento de set en algún orden arbitrario. Y finalmente un hecho interesante que vamos a encontrar más adelante o usar más adelante es el siguiente: si usted tiene algún elemento g que es un generador del grupo entonces el elemento gi es el mismo que el elemento gi módulo q, que significa que usted puede realizar la operación mod q en el exponente también. Así que para cualquier i que sea < q este hecho es trivial true porque gi y gi mod q son iguales si i < q. Pero lo que este hecho dice que si yo soy más grande que q, entonces g al poder que mayor poder yo le voy a devolver la misma respuesta que el resultado que usted obtendrá al elevar g al índice i módulo q. Una vez más, no le estoy dando la prueba para esto usted puede referirse a cualquier texto estándar en la teoría de números para la prueba de esto. Ahora esta discusión que tenemos hasta ahora aquí es con respecto a un grupo cíclico multiplicativo. Podemos ampliar nuestra definición para cualquier grupo cíclico abstracto donde la operación subyacente sea aditiva. Así que podemos definir g a los g times g para ser e o el elemento de identidad es decir, la potencia 0th de g aquí es el elemento de identidad y g1 en el grupo cíclico aditivo se interpretará como una vez g y definición dice que 1 veces g va a darle el elemento g. Y los gi en este grupo cíclico aditivo se interpretarán como i veces g que se define como la operación de grupo, o la operación de grupo aditivo realizada en el elemento g, i – 1 veces. Y resulta que las reglas de la exponenciación se mantienen en el grupo cíclico aditivo también. A saber, si tomo el elemento m veces g que es igual a gm en el grupo cíclico aditivo y otro elemento n veces g que es el equivalente de gn en el grupo cíclico aditivo. Si realizo la operación de grupo entonces el resultado será el mismo que m + n veces el elemento g es decir el equivalente del elemento g (m + n).Y lo mismo tiene así. Si tomo el elemento m tiempo g y luego si realizo n veces ese elemento, entonces el resultado será el mismo que nm veces ese elemento g y así sucesivamente. Por otra parte, si el elemento g es un generador, entonces diferentes poderes de g me va a dar todo el conjunto en algún orden arbitrario y las diferentes potencias de g se escribe como 0 veces g, 1 veces g y q- 1 veces g. Y como fue el caso para el grupo cíclico multiplicativo tengo un hecho correspondiente aquí también que si g es un generador entonces cualquier i veces g que es el equivalente correspondiente de gi es igual que el módulo q veces g. Eso significa si yo > q y luego si usted quiere calcular que i veces g entonces usted puede primero reducir ese índice i módulo q y luego elevar ese índice al elemento g para obtener la respuesta resultante. (Consultar Tiempo de Slide: 31:55) Así que ahora hemos definido una noción de grupos cíclicos y ahora vamos a ver lo que entendemos por logaritmo discreto en los grupos cíclicos. Así que imagina que te dan un grupo cíclico arbitrario de orden q y sin pérdida de generalidad asumen que la operación de grupo subyacente es una operación multiplicativa. No necesita ser una multiplicación de enteros, pero para propósito de notación usaremos la notación multiplicativa aquí. Ya que la orden es q que significa que tiene un número finito de elementos. Por lo tanto, este color indica el elemento en su conjunto. Ya que es un grupo cíclico tiene algún generador por lo menos un generador que denotan por g. Así que he destacado ese elemento g aquí y según la definición de grupo cíclico diferentes poderes de este elemento g va a darle todo el conjunto en algún orden arbitrario. Lo que significa que si usted toma cualquier elemento y de este conjunto entonces existe algún índice único x en el rango de 0 a q – 1 tal que gx le habría dado el elemento y y recordar gx está realizando la operación de grupo en el elemento g, x – 1 número de veces. No significa necesariamente que yo esté multiplicando g, x número de veces. Estoy realizando la operación de grupo multiplicativo subyacente en el elemento g, x – 1 número de veces. Así que la razón por la que existe una x única en este rango de 0 a q – 1 tal que gx le habría dado y. Viene del hecho de que el elemento g es un generador. Ahora este x único en el rango de 0 a q – 1 se llama el logaritmo discreto de su elemento y a la base g que denotamos por esta notación DLog yg = x. Y puede considerar este registro discreto como un equivalente al registro natural. En el mundo número real si usted tiene cualquier número real g a la energía que le da y entonces decimos que definimos que log yg = x. Lo que estamos tratando de hacer aquí es que estamos tratando de dar una definición equivalente en el mundo discreto, es decir, en el contexto de un grupo donde tenemos un número finito de elementos dicen q números de elementos y desde que estamos considerando un grupo. Los elementos aquí son discretos. Entre los dos elementos de grupo no se producirá un elemento de grupo arbitrario. Así que es por eso que este logaritmo que estamos definiendo la noción de logaritmo que estamos definiendo en este grupo cíclico se llama como el logaritmo discreto. Curiosamente, resulta que el logaritmo discreto obedece a las reglas del logaritmo natural i.e Dlogge = 0, Dlogghr = r (Dloggh) mod q. Por qué estamos tomando módulo q es que esto es lo que estamos teniendo la ménsula que puede salir de q, que puede cruzar el rango de 0 a q – 1, pero según la definición de registro discreto el índice de logaritmo discreto tiene que estar en el rango de 0 a q – 1 y por eso estamos tomando módulo q aquí y de la misma manera Dloggh1 h2 = (Dloggh1 + Dloggh2) mod q. Usted va a verificar estos hechos. Estos son algunos ejercicios sencillos para ti y el hecho final que vamos a utilizar en el contexto de logaritmo discreto es que si tienes algún gx dado a ser y donde x no necesita estar en el rango de 0 a q – 1. Entonces el DLogyg es igual que x módulo q. Bueno, si su x que se le da es de hecho en el rango de 0 a q – 1 entonces x módulo q es igual que x. pero el hecho interesante aquí es que si usted tiene si se le da una x que está fuera del rango de 0 a q – 1 tal que gx se da y y si usted es interesante para calcular el DLogyg es igual que la realización de la operación x módulo q. Una vez más, este es un hecho bien conocido de la teoría de números que no voy a probar aquí usted puede ver cualquier texto estándar para la prueba de este teorema. Así que eso me lleva al final de esta conferencia. Para resumir en esta conferencia, hemos introducido la noción de grupos cíclicos y hemos visto la definición de logaritmo discreto. En la próxima conferencia veremos algunos supuestos de dureza de criptografía de candidatos basados en

Notification
You have received a new notification
Click here to view them all