Fundações de Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Lecture – 55 Número da Teoria Olá a todos. Bem-vindo a esta palestra. Basta uma rápida recapitulação, na última palestra concluímos nossa discussão sobre criptografia de chave pública. Por isso, nesta palestra o roteiro é o seguinte. (Consulte O Slide Time: 00:29) Vamos basicamente discutir alguns dos principais resultados relacionados à teoria do número que utilizamos durante nossa extensa discussão sobre criptografia de chave publicitário. Eu ressalto que não estaremos tendo uma discussão completa sobre a teoria do número porque eu pessoalmente sinto que como; em um curso sobre fundações de criptografia devemos basicamente apenas usar os fatos importantes da teoria do número. Mas pensei que provavelmente deveríamos ter uma discussão de muito alto nível sobre alguns dos resultados importantes que utilizamos extensivamente durante nossa discussão sobre criptografia de chave pública. Tão motivado por isso teremos essa discussão; hoje a palestra do ’ é baseada completamente na teoria do número foram discutirmos sobre a aritmética Modular, números Prime e suas propriedades e veremos o algoritmo GCD do Euclides Estendido ’. (Consulte O Slide Time: 01:28)Então, vamos começar com a aritmética Modular. Então imagine que você recebe 2 números ou 2 inteiros a, N pertencente ao conjunto de números inteiros Z. E aqui N é o modulus onde N > 1. Então um mod N é definido para ser o restante r, tal que o restante r está na faixa de 0 a N-1, tal que o relacionamento a = q vezes N + r se mantém para algum número inteiro q. Se for esse o caso, então dizemos que um modulo N é r. Então por exemplo, se eu quiser descobrir 5 modulo 4 então 5 modulo 4 é 1, porque se eu dividir 5/4 eu fico com o restante 1. Da mesma forma, se eu quiser descobrir -11 modulo 3 então -11 modulo 3 é 1 porque 1 está na faixa de 0 a 2 e -11 pode ser relacionado a 3 por esta relação a saber eu posso dizer que -11 é 3 vezes-4 + 1. Acontece que eu posso escrever -11 como uma combinação linear do meu modulo 3 em outra forma também, ou seja, posso dizer que – 11 = (3 vezes – 3)-2. E daí pode-se sentir que -11 modulo 3 deve ser-2 mas que não é esse caso porque assim como por nossa definição o restante r deve estar na faixa de 0 a N-1. É por isso que -11 modulo 3 é 1 e não -2. Agora temos a definição de um modulo N; portanto, se temos dois números inteiros a e b tal que tanto um como b lhe dá o mesmo restante modulo, o modulo N então dizemos que um é congruente a b e nós nós a notação que um ≡ b modulo N. Então isto significa que a e b são equivalentes no sentido em que se dá o mesmo lembrete n. Assim como por a definição de um modulo N verifica-se que, se um é congruente a b modulo N então isto é possível se e somente se a diferença de a e b é completamente divisível por N. Porque se um dá o restante r modulo N e desde um é congruente a b modulo N que significa b modulo N é também o mesmo lembrete r e se eu subtrato b de um então o restante r e r cancela fora e o que eu obtenho é que a-b é completamente um múltiplo de N e daí ele será completamente divisível por N. (Consulte o Tempo do slide: 03:58) Então temos algumas regras aritméticas conhecidas para a aritmética modular. Então por exemplo temos dois números a e b e se eu sei que um modulo N é um’ e b modulo N é b’ então posso dizer que um modulo N de + b será o mesmo valor que você obteve fazendo a operação a’ + b’ modulo N. O mesmo vale para subtração, bem como multiplicação. Então a maneira como você pode interpretar essas regras é que você pode imaginar como se você puder primeiro realizar os modulares ou você pode primeiro fazer o modulo de redução, o modulus N. E então você pode realizar a adição, subtração, operação de multiplicação em vez de adicionar ou subtrair ou multiplicar e então fazer o modulo de redução N. Para ser mais específico para a instância imagine que eu quero computar o valor deste número a saber: Quero executar o produto de 1093028 e 190301 modulo 100. Se eu quiser computar esse valor, então há duas maneiras de fazer isso. A primeira forma será que eu primeiro executo o produto aqui ou primeiro computo o produto aqui e depois faço o modulo de redução 100. Mas esta será uma operação complicada porque multiplicar esses dois grandes números será realmente desafiador. Não posso fazê-lo facilmente em um notebook. Por outro lado, a mesma operação que posso realizar através da primeira redução dos valores individuais aqui a saber, 1093028 e 190301 modulo 100. E reduzir cada um dos modulo 100 é muito simples. Porque eu só tenho que me concentrar nos dois últimos dígitos aqui que eu receito como 28 e 1 e então eu posso multiplicar 28 e 1 e depois voltar a reduzi-lo, reduzir o modulo de resposta 100. E seja lá o que for obtido pela opção 1 e qualquer que seja o resultado que obtive pela opção 2 eles serão iguais às nossas regras de regras aritméticas de aritmética modular. Portanto, este é um truque muito poderoso ou poderoso aplicável no contexto da aritmética modular onde você deve; onde; em vez de aplicar a operação e depois fazer o modulo ou redução modulo N e você pode primeiro reduzir o modulo de operandos N e, em seguida, você pode realizar a operação e se for necessário você pode executar novamente um modulo de redução N. (Consulte o Tempo de Slide: 06:13) Então, vimos a adição, subtração e multiplicação modulo N e o que sobre divisão modular. Portanto, a questão é podemos dizer o seguinte, imagine um modulo N é um’ e b modulo N é b’ então podemos dizer que um dividido por b modulo N será o mesmo que um’/b’ modulo N. Resposta é não, porque na verdade em verifica-se que a operação a dividida por b modulo N não está em tudo bem definida. Por isso, para demonstrar meu ponto imagine minha a e b são 3 e 5 e meu modulo é 4 então eu sou dado 3 modulo 4 e 5 modulo 4 é 1 e eu sei que 3 dividido por 1 modulo 4 o que me deram 3 mas se eu quiser calcular 3 dividido por 5 modulo 4 eu não tenho a resposta, pois essa operação 3 dividida por 5 modulo 4 não está nada bem definida. Isso significa na aritmética modular eu não posso dizer que, se me for dado que o produto de ac modulo N e o produto bc modulo N são iguais. Então eu não posso dizer que cancelar c de ambas as partes e não pode obter implicação que um modulo N = b modulo N, o que teria sido possível se eu tivesse realizado a mesma operação em aritmética regular e c não; e c não é 0. Isso significa na aritmética regular se eu souber que ac = bc e c não é 0 então posso dizer que se eu dividir ambos os lados por c então eu obtenho a = b. Mas a mesma coisa que não posso concluir na aritmética modular porque a divisão modular não é bem definida. (Consulte O Slide Time: 07:50) Então agora vamos discutir alguns dos algoritmos para aritmética modular. Então imagine que somos dados dois operandos a e b cada um de tamanho n-bit e o modulo N cujo tamanho também é n-bit, e algumas das operações comuns que encontramos na criptografia de chave pública são realizar a adição modular, multiplicação, subtração e a exponenciação. Por isso, lembrar a exponenciação modular é uma operação muito importante em quase todas as instanciações de criptosistem público-chave, onde encontramos exponenciação modular. Por isso, agora queremos ter algoritmos para executar essas operações aritméticas modulares, tais que os algoritmos resultantes, sua complexidade, sua complexidade de tempo deve ser alguma função polinomial no número de bits a saber n. Por isso, acontece que se eu quiser realizar adição modular, subtração e multiplicação eu posso executá-los em poly (n) número de operações de bits. Mas, que tal exponenciação modular, imagine que eu quero computar ab modular N, um algoritmo ingênuo será que eu executo a2 modulo N seja qual for o resultado eu multiplique-o novamente com um e faça um modulo N, e como que eu tenho que executar basicamente b-1 multiplicações modulares e já que cada multiplicação modular requer um número de operações de polia (n) e eu estou executando b tal ordem de b tais operações pode-se dizer que, a complexidade de tempo geral deste algoritmo de exponenciação modular ingênua será O (b * poly (n))-bit operações e, portanto, é geral polinomial. Mas isso não é correto porque o que exatamente é o valor de b aqui. Eu tenho que expressar o valor de b também como alguma função de n e verifica-se que a magnitude de b aqui é alguma função exponencial em número de bits n. Basicamente b pode ser tão grande quanto 2n. Isso significa, esse algoritmo de exponenciação modular ingênuo; sua complexidade temporal é função exponencial e o número de bits que você precisa para representar o seu a b e o módulo N e por isso é o algoritmo de tempo exponencial. Não podemos usar esse algoritmo de exponenciação ingênuo para executar; para computar ab modulo N. (Consulte o Tempo do slide: 10:16)Então agora o que nós vamos discutir é veremos um algoritmo de tempo de polia para computar exponenciações modulares. Assim, este método é chamado como o método Square e Multiply. E para demonstrar o algoritmo eu vou dar um exemplo aqui. Eu quero computar uma para a potência 53 modulo N. Lembre-se, a abordagem ingênua será multiplicar um 52 vezes e cada um; com cada multiplicação você faz uma operação de mod N. Por isso, basicamente, a abordagem ingênua exigirá que você realize 52 multiplicações modulares. Mas o que nós vamos ver aqui é que usando o método quadrado e multiplicado podemos realizar o mesmo cálculo com apenas 9 multiplicações modulares. Assim, a ideia por trás desse método quadrado e de multiplicação é a seguinte. Por isso, eu expresso meu expoente 53 neste caso em binário. E dependendo da representação de bits de 53 onde quer que eu tenha o valor de bits 1 tenho que tirar esse poder de 2. Onde quer que o pouco poder seja 0 eu tenho que excluir esse poder de 2 e daí posso dizer que 53 dependendo de sua representação binária pode ser expressa como somatória destes poderes de 2. E daí posso dizer que um para o poder 53 não passa de produto de alguns poderes seletivos de um a saber a potência 32, um para a potência 16, um para a potência 4 e um para a potência 1. Assim, a ideia por trás desse método quadrado e multiplicado como o nome sugere é que em cada iteração vamos acumulando ou computamos os sucessivos poderes de um. E isso significa, vamos começar com uma potência 1 e então iremos a um quadrado então a partir de um quadrado iremos a um para a potência 4 então de um para a potência 4 iremos a uma para a potência 8 e assim sucessigamente dependendo do bit atual na representação binária do expoente a saber 53 neste caso decidiremos se acumulamos o poder atual de um ou não, e é por isso que o nome quadrado e multiplique. De uma forma mais detalhada imagine eu escrever 53 nessa representação binária de LSB para MSB nesta forma. E como eu vou de LSB para MSB os diferentes poderes de um que eu obtenho como vou de 1 bits corrente até o próximo bit é apenas um quadrado do poder anterior, certo e é fácil perceber que o meu objetivo é computar uma para a potência 53 e uma para a potência 53 basicamente pode ser computada por apenas multiplicar alguns poderes seletivos de um a saber os poderes de um correspondente às posições de bits onde na representação binária de 53, onde eu tenho o bit 1. Por isso, com base nessa ideia o algoritmo é o seguinte. Por isso, definimos aqui um acumulador que terá a resposta final. A resposta final que eu quero computar é uma para a potência b ou uma para a potência 53 neste caso. Então inicializo meu acumulador para ser 1 e uma vez que executo as todas as iterações meu acumulador terá a resposta final. Por isso, em cada iteração o que eu vou fazer é, vou fazer uma atualização condicional, a saber, vou fazer a operação que y = y em potência atual de um dependendo se o meu bit atual no expoente b que eu estou explorando agora é 1 ou não. Então por exemplo, atualmente eu começo com o LSB de 53 ou o expoente b, agora mesmo o bit é 1 que significa que eu tenho que tomar acumular esse poder e é por isso que vou atualizar meu acumulador por existir y e o poder atual de um e então eu vou para o próximo poder de um. E eu verifico a posição de bit, bit posição é 0; bit é 0 então não preciso acumular esse poder. Aí eu vou para a próxima potência de um que será um para a potência 4 e verifico o bit atual, é um só. Isso significa que eu tenho que acumular esse poder, então é por isso que atualizarei meu acumulado multiplicando o conteúdo atual do acumulado com o poder atual de um. Então eu vou para a próxima potência de um que não preciso incluir ou acumular porque a posição de bit no expoente é 0 então eu vou para a próxima potência de um e verifico a posição de bit do expoente em sua representação binária ela é 1, então eu tenho que acumular. E daí eu atualizo meu acumulador, e então eu finalmente vou para o MSB da representação de bits do meu expoente, é 1, isso significa que eu tenho que acumular o poder atual de uma e daí essa é a minha resposta final. Por isso, não estou escrevendo o código de pseudo exato aqui. Você pode entender; espero que você seja capaz de anotar o pseudo código aqui. Mas ideia aqui é que eu precisarei realizar uma sequência de iteração, o número de iterações não é nada além do número de bits que você precisa para representar o seu expoente b. E em cada iteração temos que fazer um quadrado obrigatório para computar o próximo poder de um. E um acúmulo opcional dependendo se o bit atual na representação binária do expoente b é 0 ou 1 e verifica-se que no pior caso meu expoente b poderia ser tal que todos os bits em sua representação binária é 1, isso significa no pior caso em cada iteração esse acúmulo opcional tem que ser realizado compulsório. Mas mesmo nesse caso o número total de multiplicação modular que acabamos realizando é duas vezes n que é alguma função polinomial no número de bits que você precisa para representar o seu n, o seu modulus e seus números a e b e daí este é um algoritmo de tempo de polia e este é o algoritmo que usamos para realizar exponenciação modular em todos os nossos criptossistemas publico-chave. (Consulte O Slide Time: 15:33)Agora, vamos discutir sobre números primos. Por isso, a definição de números prios é que um número inteiro p > 1 é chamado de número primo se seus únicos fatores positivos são o número em si e 1. E um número inteiro positivo maior que 1 que não é prime é chamado como número composto. E um teorema bem conhecido da aritmética que também é frequentemente chamado como teorema fundamental da aritmética é que qualquer número n > = 1 pode sempre ser expresso como produto de diferentes poderes de prime e isto é verdadeiro para cada n > = 1. Esse é um fato bem conhecido que podemos provar usando a indução e não entrar na prova exata. E há um outro fato bem conhecido da teoria do número que diz que, há infinitamente muitos primos. Não é o caso de se ter apenas número finito de primes. E novamente este teorema nós podemos provar usando contradição ou qualquer método de prova. Por isso, há várias provas bem conhecidas para provar o fato de que há infinitamente muitos primos. Não vou entrar em detalhes da prova aqui. (Consulte O Slide Time: 16:39)Então, se você lembrar que em nosso criptossistema RSA e também no contexto do esquema de criptografia Elgamal, nós basicamente exigimos como uma parte da descrição do setup de um número primo para estar disponível para todas as partes e o número primo deve ser suficientemente grande. Por isso, a questão é saber como exatamente escolhemos os números primos. Isso significa, precisamos de um algoritmo para verificar se um número de n bit aleatoriamente escolhido é um número primo ou não. E há um algoritmo ingênuo por fazer isso. E o algoritmo ingênuo é baseado no fato de que se um número p é composto então ele tem pelo menos um dos divisores que é menor ou igual a   e a prova deste teorema é muito simples porque se você tem todos os divisores de um número de composto p maior do que  . Digamos que você tem dois tais fatores a e b e nem um e nem b é menor ou igual a e ambos a e b são os fatores de p e p é composto então verifica-se que o produto ab será maior que p o que é uma contradição. Então isso significa que se em tudo você tiver um número composto p ele é obrigado a ter pelo menos um dos fatores da faixa 1 para. E com base nessa observação podemos ter este algoritmo de Testes de Primalidade a seguir. Então imagine que você recebe um número p e quer verificar se o número p é prime ou não e dizer que o número p é um número n-bit. Assim, o algoritmo ingênuo é basicamente você verificar se eles existem algum divisor i na faixa 2 para   para o número p. Porque se realmente p teria sido composto seu obrigado a ter pelo menos um dos divisores na faixa 2 para isso significa que ele terá pelo menos um divisor i na faixa 2 e que é o que você está pesquisando neste algoritmo ingênuo. Acontece que o tempo de execução deste algoritmo é O ( ) divisões porque você está executando número de divisões neste algoritmo. E como p é n-bit número a magnitude de p é 2n então basicamente você está executando 2 para as divisões de power n / 2 neste algoritmo ingênuo. E daí este é um algoritmo de tempo exponencial que não podemos utilizar na prática para testar se um determinado número p é prime ou não, se o meu n é suficientemente grande. Por isso, foi realmente um problema muito desafiador verificar se um determinado número p é prime ou não em quantidade de tempo polinomial. Na verdade, as pessoas acreditavam que não é possível chegar com o algoritmo de tempo de polia para verificar se um determinado número p é primo ou não. Mas a história foi feita no ano 2002 onde um grupo de cientistas de computação do IIT-Kanpur a saber: Manindra Agrawal, Neeraj Kayal e Nitin Saxena. Eles vieram com um algoritmo de tempo de polia, polinomial no número de bits que você precisa representar com o seu prime p, ou número p. E surgiram que esse algoritmo de tempo de polia que informa se um determinado número p é prime ou não e esse algoritmo é agora bem conhecido como algoritmo AKS. Assim, você pode usar esse algoritmo para verificar se um determinado número p é primo ou não. Mas acontece que não utilizamos o algoritmo AKS porque apesar de ser um algoritmo de tempo de polia os polinômios subjacentes são suficientemente grandes e que nos impede de implantar este algoritmo como é na prática. Em vez disso o que fazemos na realidade para verificar se um determinado número é primo ou não é utilizamos um algoritmo que é chamado como algoritmo de teste de primalidade de Miller-Rabin. E é um algoritmo randomizado no sentido de que você não pode confiar sempre na saída deste algoritmo. No sentido de que, para 99,99% casos ele lhe dará a resposta certa enquanto que há uma pequena probabilidade de erro na saída deste algoritmo. Isso significa que mesmo que sua entrada possa não ser um número primo ele pode acabar rotulando o número como um número primo. Portanto, nesse sentido é um algoritmo de praxe de erro. E a razão pela qual useMiller-Rabin testam para verificar se um determinado número é primo ou não é que seu tempo de execução é super, super rápido comparado com o seu algoritmo AKS. Eu ressalto que o algoritmo AKS é completamente livre de erros. Você pode confiar completamente no resultado que é dado por algoritmo AKS porque ele é um algoritmo determinístico. Não há randomização envolvida como parte do algoritmo. (Consulte O Slide Time: 21:08) Agora vamos discutir sobre o Greatest Common Divisor ou GCD. Portanto, se um e b são dois inteiros não zero então o GCD de a e b é o maior número inteiro que é um fator comum tanto para um como b. E se temos 2 números ou 2 inteiros a e b cujo GCD é 1 então dizemos que os números inteiros a e b são co-prime. E se temos esses vários pares de tais números ou vários números inteiros dizem a1 a um dizemos que eles são par-wise co-prime ou relativamente prime se par-wise os GCDs são 1 para cada par de inteiro ai, aj na lista. Portanto, se quisermos sair o GCD de 2 números a e b então o algoritmo ingênuo será que eu primeiro descurei a factorização prime de um porque como per o teorema fundamental da aritmética eu posso expressar um como produto de poderes de prime. E da mesma forma eu posso expressar meu número b como um produto de poderes de prime. E aí eu posso dizer que GCD de a e b não é nada além de eu pegar os expoentes mínimos da factorização individual de um e b e organizá-los e isso vai me dar o GCD de a e b. Mas o problema com esse algoritmo é que como no primeiro lugar eu encontro a factorização prime de a e b. (Consulte O Slide Time: 22:31) Então acontece que nós podemos fazer algo muito interessante aqui. Podemos usar um algoritmo eficiente para computar o algoritmo GCD e este algoritmo é chamado como Euclides ’ s GCD algoritmo. E base para o algoritmo Euclides ’ é o seguinte fato. Portanto, se você for dado números inteiros a e b tal que a é (b vezes q) + r. E se o seu objetivo é encontrar GCD de a e b então GCD de a e b não é nada além de GCD de b e r, se a = (b vezes q) + r. Novamente não estou a dar a prova deste facto. Você tem que acreditar em mim. Mas com base nisso podemos descobrir um algoritmo para computar o GCD de a e b. E basicamente, o que fazemos neste algoritmo é definimos meu x valor para um e y valor para b e iterativamente eu acho o valor de x modulo y, eu defino minha atual y para ser o próximo x e eu levo o restante do meu atual x modulo y para ser o próximo y. E eu executo essa operação até que minha y se torne 0. Assim que o meu y se torna 0 o que acabará por acontecer, obtenho o x naquele ponto para ser o GCD de a e b. E uma correção deste algoritmo segue pelo fato de que GCD de a e b será igual a GCD de b e r e GCD de b e r será igual a GCD de r e b modulo r e assim por diante. Isso significa em cada passo que estou basicamente reduzindo o valor de tão chamado b e eventualmente ele se tornará 0.So se você está se perguntando que qual é a complexidade do tempo ou quantas divisões modulares eu estou realizando aqui; quantas operações mod eu estou realizando dentro deste algoritmo Euclides ’. Posso chegar com um limite exato usando o teorema de Lame ’ s bem conhecido que diz que se o GCD de a, b for computado usando Euclides ’ s algoritmo e ele precisa n número de divisões então o seu b deve ser pelo menos n + tinto Fibonacci números a saber b deve ser maior ou igual a f (n + 1), portanto aqui f (n + 1) denota um número de Fibonacci n + 1 Fibonacci. Se você está se perguntando o que é o número do Fibonacci, é uma sequência começando com 0 o próximo número é um só. Estes são os dois primeiros números de Fibonacci. E então se eu quiser computar o valor do número do ith Fibonacci, o número da i-ésima Fibonacci é basicamente a somatória do número anterior de Fibonacci e depois anterior ao número anterior de Fibonacci. Então essa é a minha sequência de Fibonacci aqui. Portanto, o que o teorema de Lame ’ basicamente diz é que, se o algoritmo de GCD de Euclides ’ teria realizado n número de divisões então a magnitude de b será pelo menos tão grande quanto o número de n + 1 Fibonacci. E também existem limites inferiores bem conhecidos sobre o valor do nésimo número Fibonacci. Diz, o limite inferior diz que para cada extremidade do valor do nth Fibonacci número é pelo menos α tempos n-2 em que α também é chamado de relação de ouro a saber: 1 + 5. 2 Então com base nestes dois fatos posso dizer que se o meu GCD de a, b precisar n número de divisões então é máximo o n será máximo cinco vezes 10 (b). Daí, asymptoticamente o número de divisões que precisamos executar neste algoritmo é proporcional ao número de bits que precisamos para representar o valor b e, portanto, o algoritmo geral é um algoritmo eficiente. (Consulte O Slide Time: 25:57)Acontece que podemos usar o algoritmo de GCD do Euclides ’ para fazer algo mais. Por isso, para entender que me deixe primeiro ir até aqui Bezout ’ s theorem aqui. Então o que o Teorema de Bezout ’ diz é que, você sempre pode expressar o GCD de dois números a e b como a combinação linear dos números a e b. Isso significa que você pode sempre vir para cima, você sempre pode descobrir combinador linear s e t, tal que você pode expressar as entradas a e b como uma combinação linear que lhe dará o GCD de a e b. Isso significa que o GCD de a e b pode ser sempre expresso como uma combinação linear dos insumos a e b onde os combinadores s e t sempre existe. E se você está se perguntando como exatamente você pode descobrir esses coeficientes de Bezout ’ s e t ou os combinadores s e t onde você pode fazer isso realizando alguma escrituração extra ou mantendo algumas variáveis extras no algoritmo Euclides ’ s. E este algoritmo estendido onde você executa a atividade de estante extra para descobrir os combinadores lineares s e t também é conhecido como algoritmo de Euclides Estendida ’. Por isso, não vou entrar em detalhes completos de como exatamente essa escrituração extra acontece no algoritmo do Euclides ’. Deixe-me demonstrá-lo. Então, suponhamos que você queira descobrir os coeficientes combinadores lineares ou Bezout ’ para os números a ser 252 e b a ser 198. Portanto, se você vir a forma como o algoritmo GCD irá operar, o algoritmo de GCD do Euclides ’ irá operar para a entrada a ser 252 e b a ser 198 é a seguinte. Na primeira iteração a sua a será 252, b será 198 e você obterá o valor de 252 modulo 198. Na próxima iteração o seu a se tornar 198 e seu b se tornará o atual restante 54 e assim por diante. E você faz essa operação até que seu restante se torne 0. E quando o seu restante se torna 0 você sabe que 18 é o seu GCD. Por isso, agora seu objetivo é descobrir os combinadores lineares para que você possa representar o GCD 18 como a combinação linear de 252 e 198. E para isso o que podemos fazer é voltar a rastrear aqui e podemos ver que eu posso reescrever 18 para ser; com base nessa equação, posso reescrever 18 para ser 54 vezes 1-36. E se eu voltar uma vez passo acima então eu sei que o meu 36 não passa de 198-3 vezes 54. Então, se eu voltar aqui e eu substituir o valor de 36 aqui então eu obtenho que 18 pode ser reescrito como uma combinação linear de 54 e 198, mas esse não é o meu objetivo. O que eu posso fazer é novamente eu posso voltar um passo para cima e eu posso reescrever meu 54 como uma combinação linear de 252 e 198. E se eu substituir essa combinação linear nesta última equação eu acabo conseguindo que 18 seja representada como uma combinação linear de 252 e 198, isso significa que os coeficientes do meu Bezout ’ são 4 e-5. Por isso, nesta demonstração realmente para descobrir os coeficientes do Bezout ’ fiz um rastreamento posterior mas no algoritmo de realmente Euclides ’ você precisa apenas do passe para frente, não é necessário fazer uma trilha de trás em, faça a escrituração e descubra os coeficientes do Bezout ’. (Consulte O Slide Time: 29:21)Então, como exatamente este algoritmo GCD de Euclides Estendida será útil. Assim, será útil computar o modulo inverso multiplicativo N. So recall como ocorreu; a forma como definimos a operação de modulo de multiplicativo N. Assim, um * b modulo N é definido para o lembrete de um no modulo b N e lembre-se que definimos um inteiro b para ser o inverso multiplicativo de um modulo N se o produto de um e b modulo N te der 1. E utilizamos a notação b = a-1 para denotar o inverso multiplicativo de um modulo N e o fato básico aqui é que se b é inverso multiplicativo de um modulo N então um é também o inverso multiplicativo de b modulo N e verifica-se que se de fato temos um inverso multiplicativo de um modulo N, a saber se você tem b tal que um tempo b modulo N é 1 então é b + qualquer múltiplo do modulo N. Isso significa que não importa se você adicionar múltiplos de módulo N a b ou você subtrair múltiplos de módulo N a partir de b todos eles também serão o inverso multiplicativo de um modulo N e isto é por causa do fato de que um tempos b +-k vezes N termina up fressed como a combinação linear de um e N usando os combinadores s e t. E agora se eu pegar mod N em ambos os lados dessa equação então no lado direito eu obtenho um modulo N e 1 modulo N vai me dar 1. Mas o meu lado esquerdo a saber de tempos s + N vezes t modulo N vai me dar um tempo s modulo N porque N vezes t modulo N vai me dar 0 porque é o múltiplo de N. Então o que eu obtenho tomando mod N em ambos os lados é que eu obtenho a relação que um tempos s modulo N = 1 que mostra que s é na verdade o inverso multiplicativo de um modulo N. E é assim que podemos obter o; ou você pode computar o inverso multiplicativo de um número a se for co-prime a N. Então isso me leva até o final desta palestra. Só para resumir e esta palestra acabamos de discutir sobre um altíssimo nível do básico; alguns dos fatos importantes da teoria do número que usamos extensivamente durante a nossa discussão sobre criptografia de chave publicitário. Especificamente, vimos; discutidos sobre aritmética modular. Vimos um algoritmo de tempo de polia para computar exponenciação modular que é uma operação chave que executamos em qualquer criptosistema de chave pública ou qualquer algoritmo de criptografia no criptossistema de chaves públicas. Discutimos também sobre um teste de Primalidade, propriedades de número primo. E também discutimos sobre o Extended Euclides ’ s Algoritmo para computar o GCD de dois números e para computar os coeficientes Bezout ’ s serão úteis para computar o inverso multiplicativo de números.