Grupos Cíclicos | Introdução | Alison
Loading
Nota de Estudos
Study Reminders
Support
Text Version

Introdução aos 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 da Cryptography Prof. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture-38 Cyclic Groups Hello todos. Bem-vindo a esta palestra. (Consulte O Tempo De Deslizamento: 00:30) O plano para esta palestra é o seguinte. Nesta palestra introduziremos o conceito de grupos cíclicos. Você verá várias definições e propriedades e a razão pela qual estamos interessados em estudar grupos cíclicos é que, mais adiante, introduziremos algumas premissas de dureza criptográficas no contexto de grupos cíclicos que nos ajudarão ainda mais a projetar ou desenvolver as ideias básicas que são usadas para projetar o Diffie – Hellman Key Exchange Protocol. (Consulte Slide Time: 01 :00) Então lembre-se do abstract Diffie – Hellman key Exchange Protocol que nós explicamos supondo que temos algumas funções especiais E e F. Apenas para relembrar qual exatamente a exigência da função E e F foram, bem precisamos das seguintes propriedades: precisamos que a função E deve ser fácil de computar para qualquer entrada. Também precisamos que se você for dado a qualquer α do domínio do E e uma saída de função E (β), então sem saber o valor β deve ser fácil computar o valor da função F no par de entrada (α, β) e isto deve guardar para qualquer (α, β). Se você deseja atingir a privacidade fraca então a propriedade que exigimos aqui da função E e F é que para cada aleatório (α, β) deve ser difícil computar para o valor de F (α, β) se você for apenas dado o valor de E (α) e E (β). Considerando que para a privacidade forte precisamos que o valor de F (α, β) deve ser computacionalmente indistinguível de qualquer valor aleatório a partir do co-domínio mesmo se você souber o valor de E (α) e você sabe o valor de E (β). Agora a questão é que como instanciar esta função E e F? Pode ser o seguinte: então imagine que levemos exponenciação para a base pública g. Então você assume que g é alguma base fixa conhecida publicalmente e podemos levar a função candidata E para ser a seguinte: E (α) é definido para ser esta base g α e esta função F (α, β) pode ser definido como sendo a exponenciação disso com relação a esta base g e uma potência de exponenciação de energia é α times β. Portanto, esse é o meu candidato F (α, β). Agora é fácil perceber que se eu definir a minha função E e função F como esta. Em seguida, sou capaz de satisfazer um dos requisitos da função E e F que me interessa. A saber, se eu for dado E (α) e se eu quiser computar F (α, β) então o que eu tenho que fazer é eu ter que apenas erguer esse E (α) β que me dará o valor de F (α, β). Da mesma forma se eu possuo E (β) e eu não sei β então apenas conhecendo α e E (β) Eu posso computar F (α, β) elevando esse valor E (β) α. Então, isso satisfaz um dos principais requisitos que eu preciso da minha função E e função F, mas acontece que tirar essa exponenciação de inteiro não é suficiente para instanciar aquele abstrato Diffie – Hellman Key Exchange Protocol porque há vários outros problema de segurança com esta função E e F. O primeiro grande problema é que é função E não é uma função de sentido único e para ver isso imagine você saber a descrição da base g e você sabe o valor de E (α) ou seja, g α e seu objetivo é descobrir o α então é muito fácil computar o desconhecido α apenas pegando o logaritmo natural. E computar logaritmo natural é uma tarefa computacionalmente fácil. Por isso, a função E no primeiro lugar em si não é uma função de sentido único e isso significa que não posso alcançar essas noções de privacidade fraca e de forte privacidade. Não só a função E é uma função unidireta, o problema aqui é que eu não posso usá-lo para fins práticos. Não posso usar essa função E função F do candidato F para finalidades práticas porque aqui meu α e β podem ser quaisquer inteiros arbitrários. Considerando que se eu quiser instanciar e implementar essa função E e F, não posso trabalhar em uma função ou domínio no intervalo que consiste em números inteiros arbitrários e que poderiam ser de tamanho infinito. Antes, estaremos interessados em trabalhar em domínios que sejam finitos na natureza de modo que seja por isso que agora tentaremos procurar as funções de candidato E e F que não são apenas funções pontuais e não apenas satisfaz o requisito em funções E e F que precisamos para este abstract Diffie – Hellman Key Exchange Protocol, mas também estamos interessados que essas funções devam ser de domínio algebraico finito adequado. (Consulte O Tempo De Deslizamento: 05 :25) Para isso agora temos que relembrar a teoria de grupos que tínhamos visto quando construímos nossas informações teoríticas MACs a saber quando construímos a função universal. Então, deixe-me rapidamente passar pela definição de grupos. Portanto, um grupo que eu denote por este símbolo é um conjunto com alguma operação adequada sobre os elementos do conjunto e dizemos que conjunto (é um grupo se ele satisfaz os seguintes axiomas a saber: deve satisfazer o imóvel de encerramento que afirma que para cada um,, o elemento. A segunda propriedade é que a operação deve satisfazer a propriedade associatividade a saber para cada uma,,, () = () detém. Precisamos da existência de um elemento de identidade, a saber, deveria existir um elemento único que denote como e no conjunto tal que, tal que para cada um. Você deve ter um elemento inverso para cada elemento no conjunto a saber: para cada elemento a partir do conjunto deve existir um elemento único que eu denote por um -1 tal que um -1 = a -1 = mantém. Eu ressalto que esse elemento um -1 não significa o 1/a numérico. Trata-se apenas de uma interpretação ou apenas uma notação para o elemento inverso especial correspondente ao elemento a que eu preciso do meu conjunto. Por isso, novamente apenas para relembrar que também tínhamos visto alguns exemplos de grupos. O conjunto de números inteiros (Z, +) constitui um grupo Abeliano. O que é um grupo Abeliano? Um grupo Abeliano é um grupo especial que satisfaz todos os axiomas do grupo e em cima disso deve satisfazer a propriedade commutativa. A saber, a sua operação deve satisfazer a propriedade comutativa e é fácil perceber que o conjunto de números inteiros juntamente com esta operação + que satisfaz os axiomas do grupo. Se você pegar qualquer um 2 inteiros adicioná-los, você obter um inteiro, adição é associativo, 0 é o elemento identidade porque se você adicionar 0 em qualquer número inteiro você obtiver esse inteiro. Se você pegar qualquer número inteiro a, o inverso correspondente é – a. Considerando que verifica-se que o conjunto de números naturais não forma um grupo com relação ao + funcionamento porque não temos o aditivo inverso. Porque aditivo inverso do elemento, digamos 2 é – 2, mas -2 não pertence ao conjunto de números naturais. Da mesma forma o conjunto de números reais não zero R − {0} forma um grupo com relação à operação de multiplicação porque a multiplicação de quaisquer 2 números reais lhe dá um número real, portanto, o encerramento é satisfeito, a multiplicação é associativa, o elemento 1 é o elemento de identidade. Para cada elemento nonzero a, o inverso correspondente é o numérico 1/a porque o número real um multiplicado com 1/a inverso lhe dará o elemento identidade 1 e é por isso que o conjunto de números reais diferente de zero forma um grupo. (Consulte O Slide Time: 08:59) Agora estamos interessados em tipos especiais de grupos que chamamos de grupos cíclicos. Então, vamos ver o que é exatamente um grupo cíclico? Um grupo com relação a uma operação o é chamado de grupo cíclico de ordem q se as seguintes condições se mantiver: em primeiro lugar, (, o) deve satisfazer os axiomas do grupo a saber: encerramento, propriedade associativa, existência de identificação, existência do inverso para cada elemento de grupo. Se for um grupo Abeliano então está tudo bem, mas não precisamos que seja um grupo Abeliano. Por isso, pictorialmente imagine que temos certos elementos deste conjunto e esta operação o satisfaz a todos esses axiomas de grupo. O segundo requisito adequado aqui é que desde eu estou dizendo que o grupo é um grupo cíclico de ordem q. Por ordem q, quero dizer que há q número de elementos no meu conjunto. Então, é isso que eu quero dizer com a ordem do grupo de ser q. E por que se chama grupo cíclico? Chama-se grupo cíclico porque preciso de um elemento especial que eu chamo de um gerador que denogo por dizer g. Este g deve ser um dos elementos deste conjunto tal que todos os elementos a partir do conjunto podem ser gerados por este elemento especial g por diferentes potências. Aqui “ powers ”, vai ficar claro para você muito em breve o que exatamente eu quero dizer por poderes aqui. Basicamente, a ideia aqui é que esse elemento especial g que eu chamo como gerador ele tem a capacidade, ele tem a capacidade de gerar todos os elementos em seu conjunto. Se eu tenho pelo menos um elemento gerador tão especial que eu chamo como gerador, então o meu grupo é chamado de cíclico, mas eu não tenho nenhum elemento tão especial g então meu grupo não é chamado de grupo cíclico. Então, deixe-me explicar para você o que exatamente eu quero dizer gerando diferentes elementos por diferentes poderes do gerador de elementos. Então deixe o p ser um prime e eu defino um conjunto Zp * que consiste no elemento 1 p – 1 e agora deixe-me definir uma operação de multiplicação que é diferente da multiplicação aritmética normal então a operação que eu vou definir é ela é denotada por .p e que também é chamada de modulo de multiplicação p. A maneira como essa multiplicação vai ser realizada é a seguinte: Se eu pegar qualquer 2 elementos a, b do conjunto Zp * então multiplicação modulo p de a e b é igual a você multiplicar a e b numericamente e tirar o lembrete com relação ao modulo p. Seja qual for o lembrete que você obtiver que será um número na faixa de 0 a p-1 e é assim que definimos essa operação do modulo de multiplicação p. Agora vou afirmar um resultado que é um resultado padrão que se segue a partir da teoria do número. Não vou provar isso, mas se você está interessado na prova deste teorema então pode se referir a qualquer referência padrão a partir da teoria do número. Por isso, o teorema basicamente afirma que para cada número primo p o conjunto Zp * junto com o modulo de multiplicação da operação é um grupo ou ele constitui um grupo constituído por elementos p – 1. Isso significa que a ordem de grupo é p – 1. Então nós não vamos provar isso, mas eu vou demonstrar que realmente isso é verdade se p é o seu prime. Por isso, estou tomando p = 5 aqui e Z5 * basicamente consiste em elementos {1, 2, 3, 4}. Então o que eu fiz foi ao longo das fileiras que anotei o elemento 1, 2, 3, 4 e ao longo das colunas eu denotei os elementos 1,2, 3, 4 e isso é como uma matriz aqui. E o que eu fiz aqui é o (i, j) entrada denota os resultados de (i. j) modulo 5 aqui. Se eu considerar essa entrada, este é o resultado de (2. 2) modulo 5. Da mesma forma (4. 3) o modulo 5 vai te dar 2 e assim por diante. Assim você pode ver a partir dessa matriz que sua propriedade de encerramento está satisfeita. Você leva qualquer i e qualquer j no intervalo que pertence a Z5 * e realizar a operação (i. j) modulo 5, você vai obter o número na faixa de 1 a 4. A operação de multiplicação que aqui definimos satisfaz a propriedade associatividade que significa se eu pegar (i, j) entrada, então não importa em que ordem eu multiplique (i, j) entrada e tomemos o modulo 5, vou obter o mesmo lembrete. O elemento identidade é o elemento 1 aqui porque se você vê esta matriz aqui e se você foca na coluna abaixo de 1 aqui então sob aquela 1, 1 ponto 1 modulo 5 te dá 1, 2 ponto 1 modulo 5 dá 2, 3 ponto 1 modulo 5 dá 3 e 4 ponto 1 modulo 5 dá 4. Assim, o elemento 1 serve como elemento de identidade aqui. Agora sob cada elemento você terá o elemento inverso correspondente. Por isso, o inverso de 1 é 1 aqui porque 1 ponto 1 dá 1. O inverso de 2 é 3 porque 2 ponto 3 modulo 5 te dá o elemento identidade 1, o inverso de 3 é 2 porque 3 ponto 2 modulo 5 te dá o elemento identidade 1 e inverso de 4 é 4 porque 4 ponto 4 modulo 5 dá-lhe o elemento identidade 1. Então você tem todos os axiomas satisfeitos e agora você pode ver, você tem alguns elementos de gerador especiais presentes aqui também. Eu vou demonstrar isso também. Antes de entrar para saber se o elemento gerador aqui existe ou não, deixe-me primeiro definir o que queremos dizer com exponenciação de grupo neste conjunto Zp *. Para qualquer elemento g pertencente ao conjunto Zp *, eu defino g0 a ser 1. E eu defino g 1 para ser g porque realmente o g0 modulo p você vai obter 1 modulo p que é igual a 1 e g 1 se g é um elemento de Zp *. É claro que é menor que p e se você fizer g1 e depois pegar mod p então o efeito de mod p não surte efeito. Você vai obter g apenas. Considerando que eu defino g i para ser a operação de multiplicação do modulo p aplicado i – 1 vezes. E acontece que não importa se eu levo o lembrete no final ou se eu levo no lembrete depois de realizar cada indivíduo. p operação i – 1 vezes, os resultados serão iguais porque isso vem da propriedade associatividade do meu grupo Zp *. Então eu posso definir gi para ser o mesmo que você executa o gi numérico e então você tira um mod p final para trazer de volta o resultado na faixa 0 p – 1. Então, por causa da maneira como gi é definida para o caso eu ser 0, eu para ser 1 e eu para ser um genérico eu, posso dizer que posso definir meus gi. Eu posso usar a notação gi no conjunto Zp * para denotar o valor numérico gi modulo p so que é uma notação que eu vou usar aqui e é isso que eu quero dizer pelo poder de um elemento g no conjunto Zp * aqui. Por isso, novamente vou afirmar outro resultado bem conhecido da teoria de número que afirma que para cada número primo p, existe pelo menos a um elemento g no conjunto Zp * tal que quando você computa quando ergue g para diferentes poderes e realiza operação modulo p a saber: você faz g0 mod p, g1 mod p up to gp – 2 mod p, então você vai obter todos os elementos no conjunto Zp * em alguma ordem arbitrária. Isso significa p – 1 potências distintas deste elemento especial g vai dar a você todos os elementos em Zp * e isso significa que você tem pelo menos um gerador presente neste conjunto Zp *. É isso que eu quero dizer com a geração de todos os elementos do conjunto por diferentes poderes. Sua aqui neste exemplo particular é a Zp * e a alegação da teoria de número é que existem pelo menos um elemento nesta Zp * tal que se você levantar g para os diferentes poderes aqui e realizar a operação do grupo a saber a operação do modulo de multiplicação p você vai obter todos os elementos de Zp *. Novamente eu não estou dando uma prova disso, mas se você está interessado na prova pode ver qualquer referência padrão. Vejamos se este teorema se detém para o exemplo atual que estamos considerando aqui. Portanto, se eu pegar o elemento 2 que é um elemento de Z5 * e executar 20 modulo 5, 21 modulo 5, 22 modulo 5 e 23 modulo 5, vou obter os elementos 1, 2, 4, 3, respectivamente. Por isso, observe que não estou obtendo todos os elementos de Z5 * na ordem exata. Mas estou obtendo todos os elementos em alguma ordem arbitrária. Portanto, para a definição de grupo cíclico, a exigência é de que diferentes poderes de g devem dar a todos os elementos desse conjunto em qualquer ordem arbitrária. A ordem não importa aqui. Da mesma forma o elemento 3 também é um elemento especial aqui porque 30 modulo 5, 31 modulo 5, 32 modulo 5 e 33 modulo 5 vai dar-lhe o elemento 1,3, 4, 2 a saber, o Z5 inteiro *. Mas se eu pegar o elemento 4 e tentar levantar ou computar diferentes potências de 4, eu não sou capaz de gerar todos os elementos de Z5 *. Eu poderia gerar apenas os elementos 1 e 4. Sendo assim, desde o resultado da teoria do número que estou declarando aqui afirma que eu tenho algum elemento especial g que tem a capacidade de gerar todo o conjunto Zp *. Isso significa que o conjunto Zp * juntamente com esta operação modulo de multiplicação p é um grupo cíclico de ordem p – 1. Porque tem p – 1 elementos e realmente neste exemplo 2 é o dos geradores de Z5 *, 3 é também um dos geradores de Z5 *, mas 4 não é um gerador de Z5 *. Agora você pode estar se perguntando por que o nome cíclico aqui. A razão pela qual estou chamando de cíclica porque assim que você tiver um gerador g diga por exemplo para o grupo Zp*e então se você computar a próxima potência de g a saber g p – 1 você vai obter um dos elementos que já está lá em Zp *. Essencialmente você vai obter o elemento g0 apenas. Então novamente a prova para isso segue a partir da teoria do número, mas eu não vou provar que se você computar g p – 1 você obterá o mesmo valor que o g 0. A próxima potência de g dará a você g1 e assim por diante. Nesse sentido ele é cíclico que significa assim que você vai até o limite gp – 2, e se você for começar a tomar a próxima sequência de poderes de g você começará a receber de volta o mesmo ciclo. Você obterá os mesmos elementos de Zp * e ele vai continuar acontecendo e é por isso que o nome grupo cíclico. Por isso, grupos cíclicos, apenas para resumir os grupos cíclicos são tipos especiais de grupo que tem pelo menos um gerador. (Consulte O Tempo De Deslizamento: 20 :59) Assim, o grupo Zp * com relação à operação modulo de multiplicação p constitui o grupo cíclico multiplicativo porque lá a operação foi de multiplicação. Não foi a multiplicação natural. Não foi a multiplicação de número inteiro, mas poderia ser interpretada como uma operação multiplicativa. Acontece que também podemos definir grupos cíclicos com base na noção de operação de adição e deixar-nos fazer isso. Então, deixe o p ser um prime e eu defino um conjunto Zp para ser o conjunto de números inteiros 0 p – 1. Então a diferença entre Zp * e Zp é que é que o elemento 0 não está lá em Zp *, mas o elemento 0 agora é permitido em Zp. Agora deixe-me definir uma operação de adição neste conjunto Zp o qual chamo como complemento modulo p denotado por este símbolo + p e o modulo de adição p de algum par de números a, b do conjunto Zp não é nada além de executar o complemento numérico ou inteiro a e b e levar o modulo p. De modo que o resultante é um elemento no set 0 p – 1. Então novamente vamos dar um exemplo aqui o conjunto Z5 consiste no número inteiro {0, 1, 2, 3, 4} e o que eu fiz aqui é eu fiz a matriz que denota o resultado da execução da operação + modulo 5 em qualquer par de elementos no conjunto Z5. Novamente, há um fato bem conhecido da teoria do número que afirma que se você pegar qualquer prime p então o conjunto Zp junto com o modulo de adição de operação constitui um grupo. Mas agora a ordem do grupo é prime a saber: tem p número de elementos porque você agora está tendo o elemento 0 p – 1 enquanto que o conjunto Zp * era um grupo multiplicativo de ordem p – 1. Então agora vamos ver como podemos interpretar a exponenciação do grupo neste grupo aditivo. Por isso, definimos 0 vezes g para ser 0 e definimos uma vezes g para ser g onde g é qualquer elemento no conjunto Zp. Considerando que i vezes g é definido como o resultado dessa operação de adição modulo p sendo aplicada sobre o elemento g, i – 1 vezes. Acontece que não importa se eu levo o mod no último ou se eu levo o mod depois de cada + operação o resultado vai ser o mesmo porque isso segue da propriedade associatividade da operação + e daí eu posso dizer que eu times g é o mesmo que a multiplicação de número inteiro de i e g modulo p. Por isso, quando digo que tempos g que não significava que eu estou multiplicando eu e g, eu vezes g é a notação que eu segui por g e eu segui por g é igual a multiplicação de número inteiro de i e g modulo p. Assim, com base nessas 3 maneiras ou na forma como essa exponenciação de grupo é definida com relação a esta + operação eu posso usar a notação que eu. g é igual a multiplicação de número inteiro de i e g modulo p. E novamente há um resultado bem conhecido da teoria de número que afirma que para cada prime p existem pelo menos um elemento especial g no conjunto Zp tal que 0 vezes g, 1 vezes g up to p – 1 vezes g a saber, o p – 1 potências distintas de g vai dar de volta todos os elementos do conjunto Zp em alguma ordem arbitrária. Por isso, agora aqui a exponenciação é basicamente tratada como se você quisesse computar g x. Basicamente, g x aqui é interpretado como se você estiver realizando a operação + modulo p operação x – 1 número de vezes. Sendo assim, essa é a interpretação de poder de g quando estou considerando a operação de grupo subjacente nos conjuntos aditivos. Por isso, novamente, no contexto do Z5 o elemento 1 acaba por ser um elemento tão especial onde todas as diferentes potências de 1 vai dar de volta todos os elementos de Z5. O mesmo vale para 2 já que poderes bem diferentes de 2 vai te devolver todos os elementos de Z5. Isso significa que o conjunto Zp junto com a operação + modulo p é um grupo cíclico de ordem p. Por isso, tínhamos visto exemplos de grupos cíclicos baseados na operação de multiplicação. (Consulte O Tempo De Deslizamento: 25 :26) Então, tínhamos visto exemplos de grupo cíclico com base em operação de adição. Agora vamos definir o que queremos dizer com exponenciação de grupo em grupos cíclicos abstratos. Por isso, para explicação estou assumindo que o meu é algum grupo abstrato onde a operação subjacente é uma operação multiplicativa. Não precisa ser uma multiplicação de número inteiro, mas pode ser interpretada no sentido multiplicativo e tem uma ordem q a saber, tem q números de elementos. Uma vez que se trata de um grupo abstrato, denogo o elemento de identidade para ser e deixar g ser um elemento deste grupo. Em seguida, usamos a notação a seguir. Sendo assim, já que estamos usando notação multiplicativa aqui para aquele grupo abstrato, utilizarei a notação g0 para designar o elemento de identidade e g1 para denotar o elemento de identidade. E a notação gi para denotar o elemento que obtenho por compor ou realizar a operação do grupo no elemento g, i – 1 número de vezes. Eu ressalto que essa notação é completamente diferente da exponenciação de inteiro. Isso é apenas uma notação, gi não significa que eu estou multiplicando g, i – 1 vezes. É basicamente apenas uma notação que usei para representar que estou realizando a operação de grupo no elemento g, i – 1 número de vezes. No entanto, verifica-se que as regras da exponenciação de número inteiro ainda são aplicáveis neste grupo multiplicativo abstrato. Ou seja, se eu pegar o elemento de grupo gm que é basicamente o elemento g composto por si mesmo m – 1 números de vezes conforme a operação do grupo e eu levo o outro elemento de grupo dizer g n que é o elemento de grupo g composto por si mesmo n – 1 número de vezes. Então se eu executar a operação do grupo nesses 2 elementos então o resultado será o mesmo que o elemento g sendo composto m + n – 1 número de vezes. Da mesma forma, se eu pegar o elemento gm e executar a operação do grupo naquele elemento n – 1 número de vezes então eu obterá o mesmo resultado que obtenho realizando a operação do grupo no elemento g, m + n – 1 número de vezes e assim por diante. Além disso, se esse elemento g é um grupo cíclico então acontece que diferentes poderes de g e novamente por diferentes poderes de g eu não significam a exponenciação de inteiro. Poder por diferentes poderes de g significa a definição de exponenciação de grupo nesse sentido abstrato. Portanto, se este g for um gerador então diferentes poderes de g que vão desde o 0º poder até o q – 1. º poder vai me dar de volta todo o elemento de set em alguma ordem arbitrária. E finalmente um fato interessante que vamos encontrar mais tarde ou usar mais tarde é o seguinte: se você tem algum elemento g que é um gerador do grupo então o elemento gi é o mesmo que o elemento gi modulo q, isso significa que você pode executar mod q operação no expoente também. Por isso, para qualquer i que seja < q este fato é trivialmente verdadeiro porque gi e gi mod q são iguais se i < q. Mas o que este fato diz que se eu for maior que q, então g para o poder que maior poder i vai lhe devolver a mesma resposta que o resultado que você obterá através da elevação g para o índice i modulo q. Novamente, não estou dando a prova para isso você pode se referir a qualquer texto padrão sobre a teoria do número para prova disso. Agora essa discussão que nós temos até agora aqui é com respeito a um grupo conjuntural multiplicativo. Podemos estender a nossa definição para qualquer grupo cíclico abstrato onde a operação subjacente seja aditiva. Assim, podemos definir g aos g tempos g para ser e ou o elemento de identidade a saber, o 0º poder de g aqui é o elemento identidade e g1 no grupo cíclico aditivo será interpretado como uma vez g e definição diz que 1 vezes g vai dar-lhe o elemento g. E gi neste grupo cíclico aditivo será interpretado como i vezes g que é definido para ser a operação do grupo, ou a operação de grupo aditivo realizada no elemento g, i – 1 vezes. E acontece que as regras de exponenciação se mantêm no grupo cíclico aditivo também. Ou seja, se eu pegar o elemento m vezes g que é o mesmo que gm no grupo cíclico aditivo e outro elemento n vezes g que é o equivalente a gn no grupo cíclico aditivo. Se eu executar a operação do grupo então o resultado será o mesmo que m + n vezes o elemento g a saber o equivalente do elemento g (m + n).E o mesmo se comporta assim. Se eu pegar o elemento m tempo g e então se eu executar n vezes esse elemento, então o resultado será o mesmo que nm vezes esse elemento g e assim por diante. Além disso, se o elemento g for um gerador, então diferentes poderes de g vai me dar o conjunto inteiro em alguma ordem arbitrária e os diferentes poderes de g são escritos como 0 vezes g, 1 vezes g e q- 1 vezes g. E como foi o caso do grupo de ciclismo multiplicativo eu tenho um fato correspondente aqui também que se g é um gerador então qualquer i vezes g que é o equivalente correspondente de gi é o mesmo que eu modulo q vezes g. Isso significa se eu > q e então se você quiser computar que eu vezes g então você pode primeiro reduzir esse índice i modulo q e então elevar esse índice para o elemento g para obter a resposta resultante. (Consulte O Tempo De Deslizamento: 31:55) Então agora definimos uma noção de grupos cíclicos e agora vamos ver o que queremos dizer com discreto logaritmo nos grupos cíclicos. Então imagine que você recebe um grupo cíclico arbitrário de ordem q e sem perda de generalidade supõem que a operação do grupo subjacente é uma operação multiplicativa. Não precisa ser uma multiplicação de número inteiro, mas para propósito de notação usaremos a notação multiplicativa aqui. Já que a ordem é q isso significa que tem finito número de elementos. Assim, esta cor pontos denota o elemento variado no seu conjunto. Já que é um grupo cíclico ele tem algum gerador pelo menos um gerador que eu denote por g. Por isso, destaquei esse elemento g aqui e conforme a definição de grupo cíclico diferentes poderes desse elemento g vai dar-lhe todo o conjunto em alguma ordem arbitrária. O que isso significa é que se você pegar qualquer elemento y deste conjunto então existe algum índice exclusivo x na faixa 0 para q – 1 tal que gx teria dado o elemento y e lembre-se gx está realizando a operação do grupo no elemento g, x – 1 número de vezes. Não significa necessariamente que eu esteja multiplicando g, x número de vezes. Estou realizando a operação de grupo multiplicativo subjacente sobre o elemento g, x – 1 número de vezes. Portanto, a razão de existir um x único neste intervalo de 0 q – 1 tal que gx teria dado a você y. Vem do fato de que o elemento g é um gerador. Agora este exclusivo x na faixa 0 para q – 1 ele é chamado de logaritmo discreto de seu elemento y para a base g que denotamos por esta notação DLog yg = x. E você pode considerar esse log discreto para ser um equivalente ao log natural. No mundo de número real se você tem algum número real g para o poder te dando y então dizemos que definimos que log yg = x. O que estamos a tentar fazer aqui é que estamos a tentar dar uma definição equivalente no mundo discreto a saber, no contexto de um grupo onde temos algum número finito de elementos dizem q números de elementos e uma vez que estamos a considerar um grupo. Os elementos aqui são discretos. Entre quaisquer dois elementos de grupo não será um elemento de grupo arbitrário que vem subindo. Por isso, é por isso que este logaritmo que estamos definindo a noção de logaritmo que estamos definindo neste grupo cíclico é chamado como logaritmo discreto. Curiosamente, verifica-se que o logaritmo discreto obedece às regras do logaritmo natural i.e Dlogge = 0, Dlogghr = r (Dloggh) mod q. Por que estamos tomando modulo q é que esta é a coisa que estamos tendo o suporte que pode sair de q, que pode atravessar o intervalo de 0 para q – 1, mas conforme a definição de log discreto o índice o logaritmo discreto tem que estar na faixa 0 q – 1 e é por isso que estamos tomando modulo q aqui e da mesma forma Dloggh1 h2 = (Dloggh1 + Dloggh2) mod q. Você vai verificar esses fatos. Estes são alguns exercícios simples para você e o fato final que vamos usar no contexto de logaritmo discreto é que se você tem algum gx dado para ser y onde x não precisa estar na faixa 0 para q – 1. Então o DLogyg é o mesmo que x modulo q. Bem se o seu x que você é dado é realmente na faixa de 0 q – 1 então x módulo q é igual a x. mas o fato interessante aqui é que se você tem se lhe é dado um x que está fora do intervalo 0 a q – 1 tal que gx é dado y e se você é interessante computar o DLogyg é mesmo que executar a operação x módulo q. Novamente, este é um fato bem conhecido da teoria do número que não vou provar aqui você pode ver qualquer texto padrão para a prova deste teorema. Então isso me leva até o final desta palestra. Para resumir nesta palestra, introduzimos a noção de grupos cíclicos e vimos a definição de logaritmo discreto. Na próxima palestra veremos alguns suposições de dureza de criptografia de candidatos com base no cíclico

Notification
Você recebeu uma nova notificação
Clique aqui para visualizar todos eles