Crescimento de Funções e Análise de Algoritmos

32 O Crescimento de Funções Introdução Na Seção 31 discutimos o conceito de algoritmo Introduzimos os algoritmos que resolvem várias problemáticas incluindo a busca por um elemento em uma lista e a ordenação de uma lista Na Seção 33 estudaremos o número de operações usadas por esses algoritmos Vamos estimar especialmente o número de comparações usadas por algoritmos de busca linear e binária para encontrar um elemento em uma sequência de n elementos Vamos também fazer uma estimativa do número de comparações usadas pelo bubble sort e pelo insertion sort para ordenar uma lista de n elementos O tempo necessário para resolver um problema depende não só do número de operações que ele usa mas também do hardware e do software que implementa o algoritmo Entretanto quando mudamos o hardware o software usados para implementar um algoritmo podemos nos aproximar do tempo necessário para resolver um problema de tamanho n pela multiplicação dos tempos anteriores exigidos por uma constante Por exemplo em um supercomputador podemos resolver um problema de tamanho n de milhõe de vezes mais rápido do que em um PC Entretanto este fator é um milhaio que depende de n exceto talvez em termos de ordem menor Uma das vantagens da nossa notação O grande que introduzimos nesta seção é que podemos estimar o crescimento da função sem nos preocuparmos com as constantes multiplicadoras ou termos de ordem menor Isto significa que usando a notação O grande não precisamos nos preocupar com hardware e software usadas para implementar um algoritmo Além disso nessa notação podemos assumir que as operações diferentes usadas em um algoritmo levam o mesmo tempo o que simplifica consideravelmente a análise A notação O grande é muito usada para estimar o número de operações que um algoritmo utiliza à medida que sua entrada aumenta Com a ajuda dessa notação podemos determinar se é prática usar um determinado algoritmo para resolver um problema quando o tamanho da sua entrada aumenta Além disso usando a notação O grande podemos comparar dois algoritmos para resolver um problema um usando 100n² 17n 4 operações e outro n³ operações a notação O grande pode nos ajudar a ver se o primeiro algoritmo nos atende melhor do que o n³ para n mesmo se eles usarem mais operações para valores menores de n tal como n 10 Esta seção introduz a notação O grande e as notações relacionadas Ômega grande e Theta grande Explicaremos como as estimativas O grande Ômega grande e Theta grande são construídas e estabelecidas para algumas funções importantes que são usadas na análise de algoritmos Notação O grande O crescimento de funções é geralmente descrito usandose uma notação especial A Definição 1 descreve esta notação DEFINIÇÃO 1 Sejam f e g as funções do conjunto de números inteiros ou dos números reais para o conjunto dos números reais Dizemos que fx é Ogx se houver constantes C e k tal que fx C gx sempre que x k Isto é lido como fx é Ogx Observe que na relação fx é Ogx x² pode ser trocado por qualquer função com valores maiores que 2 Por exemplo fx é Ox² fx é Ox² x 7 assim por diante É verdade também que x² é Ox² 2x 1 porque x² x² 1 sempre que x 1 Isto significa que C 1 e k 1 são parâmetros da relação em que x² é Ox² 2x 1 Note que no Exemplo 1 temos duas funções fx x² 2x 1 e gx x² tal que fx é Ogx e gx é Ofx o último fato vem da inequação x² x² 2x 1 que é garantida para todos os números reais não negativos x Dizemos que duas funções fx e gx que satisfazem as relações de O grande são de mesma ordem Retornaremos esta noção mais à frente nesta seção Lembrese O fato de dizermos que fx é Ogx é às vezes escrito como fx Θgx Entretanto o sinal de igual não representa nesta notação uma igualdade genuína Ao contrário esta notação não diz que mesmo uma inequação é sustentada pela relação entre valores das funções fx e gx nos números suficientemente grandes no domínio dessas funções Entretanto é aceitável escrever fx Ogx representando o conjunto de funções g A Função fx é Ogx O Exemplo 2 mostra que 7x² é Ox³ fx Cxr em que C a₀ a₁ aₖ sempre que x 1 Assim os parâmetros C a₀ a₁ mostram que fx é Oxr Esta inequação mostra que n é Onn tomando C 1 e k 1 como parâmetros Tomando os logarithmos dos dois lados da inequação estabelecida para n obtemos log n log m n log n Isto implica que log n não é On log n tomando novamente C 1 e k 1 como parâmetros EXEMPLO 7 Na Seção 41 mostraremos que n 2n sempre que n for um número inteiro positivo Mostre que a inequação implica que n é O2n e use a inequação para mostrar que n O2n Solução Usando a inequação n 2n rapidamente concluímos que n é O2n tomando k C 1 como parâmetros Note que como a função logarítmica é crescente tomando logarithmos de base 2 dos dois lados da inequação temos que log n n Daqui segue que log n é On Novamente aceitamos C k 1 como parâmetros FIGURA 3 Uma Demonstração do Crescimento das Funções geralmente Usadas em Estimativas O grande estimativa é usada para a soma e para o produto de duas funções suponha que f1x seja Og1x e f2x seja Og2x A partir da definição de notação O grande há constantes C1 C2 k1 e k2 tal que f1x C1g1x quando x k1 e f2x C2g2x quando x k2 Para estimar a soma de f1x e f2x note que f1 f2x f1x f2x f1x f2x usando a inequação triangular Quando x é maior que k2 temos a partir das inequações para f1x e f2x que f1x f2x C1g1x C2g2x C1g1x g2x Cg1x em que C C1 C2 e gx maxg1x g2x Aqui maxa b indica o máximo ou maior entre a e b Esta inequação mostra que f1 f2x Cgx sempre que x maxk1 k2 TEOREMA 2 Suponha que f1x seja Og1x e f2x seja Og2x Então f1 f2 é Omaxg1x g2x Geralmente temos estimativas O grande para f1 e f2 em termos da mesma função g Neste caso o Teorema 2 pode ser usado para mostrar que f1 f2 é também Og porque maxg1 g2 gx Este resultado é confirmado pelo Corolário 1 COROLÁRIO 1 Suponha que fx e fx sejam Ogx Então f1 f2x é Ogx De forma semelhante as estimativas O grande podem ser derivadas para o produto das funções f1 e f2 Quando x é maior que maxk1 k2 temos que f1f2x f1xf2x C1g1xg2x C1C2g2x Cgx em que C C1C2 A partir desta inequação temos que f1xf2x é Og1g2 pois há constantes C e k com C C1C2 e k maxk1 k2 tal que f1f2x C gx sempre que x k Este resultado é confirmado pelo Teorema 3 TEOREMA 3 Suponha que f1x seja Og1x e f2x seja Og2x Então f1xf2x é Og1g2x Geralmente quando a notação Teta grande é usada a função gx em Θgx é uma função referencial relativamente simples assim como xn cx log x e assim por diante enquanto fx pode ser relativamente complicada Mostramos no Exemplo 10 que a soma dos primeiros n números inteiros positivos é Θn2 Esta soma é de ordem n2 Solução Considere fn 1 2 n Como já sabemos que fn é On2 para mostrar que fn é de ordem n2 precisamos encontrar uma constante positiva C1 tal que f C1n2 para n números inteiros suficientemente grandes Para obter uma limitação inferior para esta soma podemos ignorar a primeira metade dos termos Somando apenas os termos maiores que n2 encontramos que Suponha que fx seja Ogx em que f são funções crescentes e ilimitadas Mostre que log fx Olog gx 1 2 cdots n n2 n2 1 cdots n Suponha que fx seja Ogx É verdade que 2 fx Ogx n2 n2 cdots n2 nn2n2 Considere fx e gx como funções do conjunto de números reais para o conjunto de números reais positivos Mostre que fx cdot gx é uma função do conjunto dos números reais positivos então fx fx in Ogx n2n2 2 n24 Assim pelo menos 2k 2 2 log n 2 comparações são necessárias para realizar uma busca binária quando a lista a ser pesquisada tiver 2k elementos Se n não for uma potência de 2 a lista original é expandida para uma lista com 2k1 termos onde k no máximo 2 log n 2 comparações Consequentemente uma busca binária restrita de no máximo Olog n comparações A partir desta análise temos que o algoritmo de busca binária é mais eficiente no pior caso que uma busca linear COMPLEXIDADE DE CASO MÉDIO Outro tipo importante de análise de complexidade além da análise do pior caso é chamada de análise do caso médio O número médio de operações usadas para resolver os problemas sobre todas as entradas de observar no presente tipo de análise A complexidade temporal de caso médio é geralmente muito mais complicadada que a análise do pior caso porque a análise do caso linear pode ser feita sem muitas dificuldades como mostra o Exemplo 4 EXEMPLO 4 Descreva a performance de caso médio do algoritmo de busca linear supondo que o elemento x está na lista Isto mostra que fn é Ωn2 Concluímos que fn é de ordem n2 ou em símbolos fn é Θn2 Solução O bubble sort descrito no Exemplo 4 da Seção 31 seleciona uma lista pela realização de uma sequência de passos ao longo da lista Durante cada passo o bubble sort compara sucessivamente os elementos adjacentes trocandoos se necessário Durante a iésima passagem o i 1 maiores elementos estão nas posições corretas Durante esta etapa n i comparações são usadas Consequentemente o número total de comparações usadas pelo bubble sort para ordenar uma lista de n elementos é n1 n2 2 1 n1n 2 usandose uma fórmula de somatório que vamos demonstrar na Seção 41 Note que o bubble sort sempre usa essas comparações porque ela continua mesmo se a lista estiver completamente ordenada em alguma etapa Consequentemente o bubble sort usa n 12n comparações assim ela tem uma complexidade de pior caso Θn² em termos de número de comparações usadas Podemos mostrar que fx é Θgx se conseguirmos encontrar números reais positivos C1 e C2 e um número real positivo k tal que A situação é muito pior para problemas que não podem ser resolvidos com um algoritmo com complexidade temporal polinomial de pior caso Tais problemas são chamados de intratáveis Geralmente nada se sabe em termos da quantidade de tempo e necessidade para resolver problemas nos piores casos até mesmo quando os valores de entrada permanecem Na prática entretanto há situações em que um algoritmo com uma certa complexidade temporal de pior caso pode ser capaz de resolver um problema mais rápido para a maioria dos casos exceção essa situação em um tempo razoável onde as soluções são relativamente pequenas A primeira determinação de um algoritmo leva para resolver problemas Muitos problemas importantes na indústria estão próximos de serem intratáveis pois podem ser parcialmente resolvidos para essencialmente todos os conjuntos de entradas que aparecem em condição Outra maneira de lidar com problemas intratáveis quando eles aparecem em aplicações práticas é em vez de procurar por soluções exatas de um problema utilizar soluções aproximadas Podese por outro lado fazer aproximações em alguns casos para muitos diferentes da solução exata C1gx fx C2gx sempre que x k Isto mostra que fx Ogx e fx Ωgx O problema de satisfatibilidade é um exemplo de um problema NPcompleto podemos verificar rapidamente que um conjunto de valoresverdade para as variáveis de uma proposição composta tornaa verdadeira mas nenhum algoritmo de tempo polinomial foi descoberto para encontrar tal conjunto de valoresverdade Por exemplo uma busca exaustiva de todos os valores verdadeiros possíveis requer Θ2n operações binárias em que n é o número de variáveis da proposição composta Além disso será um algoritmo com tempo polinomial para todos os problemas satisfatíveis por conhecido haverá algoritmos com tempo polinomial para todos os problemas conhecidos nesta classe de problemas e há muitos problemas importantes nessas classes Mesmo depois de uma busca extensiva nenhum algoritmo com tempo polinomial no pior caso foi encontrado para qualquer problema desta classe É aceitável embora não demonstrado que o problema NPcompleto pode ser resolvido em tempo polinomial Para mais informações sobre a complexidade em algoritmos consulte as referências para esta seção incluindo CoLeRis01 listada no final deste livro Além disso para mais discussões formais sobre complexidade computacional em termos de máquinas de Turing veja a Seção 125 Note que uma estimativa g grande da complexidade temporal de um algoritmo expressa como o tempo necessário para resolver o problema pode mudar com o crescimento das entradas Na prática é utilizada a notificação de entrada ou seja com a menor relação por referência que pode ser mostrada Entretanto g grande faz a estimativa da complexidade temporal não pode ser remotamente transcrita no tempo do computo para um usado Uma vez que uma estimativa g grande de fn e Θgn em que fn é a complexidade temporal de um algoritmo e gn é a função referencial significa que C1gn fn C2gn quando h k em que C1 C2 e k são constantes Então sem conhecer as constantes C1 C2 e k na referência essa estimativa não pode ser usada para determinar uma limitação superior e uma inferior em relação ao número de operações usadas no pior caso Como foi dito anteriormente o tempo necessário para uma operação depende do tipo de operação e do computador a ser usado Geralmente ver uma estimativa g grande da complexidade temporal do pior caso de um algoritmo temos apenas uma estimativa O grande Note que uma estimativa O grande da complexidade temporal de um algoritmo fornece uma limitante superior mas não uma inferior do tempo de pior caso necessário para o algoritmo como uma função de determinado tamanho No entanto para simplificar normalmente estimativas O grande ao descrever a complexidade temporal dos algoritmos a partir do entendimento de que a estimativa g grande pode fornecer mais informações Entretanto o tempo necessário para um algoritmo resolver um problema de tamanho específico pode ser determinado de todas as operações usadas perferidas as operações binárias usadas por um computador A Tabela 2 apresenta o tempo necessário para resolver problemas de vários tamanhos com um algoritmo usado no menor indicado de operações binárias Tempos com n de 100 anos são indicados como um Asperisco Na Seção 36 será discutido o número de operações binárias usadas para adicionar e multiplicar os números inteiros Na construção dessa tabela considerase que cada operação binária leva 109 segundos que é o tempo necessário para uma operação binária que utilize os computadores mais rápidos da atualidade No futuro esses tempos tendem a diminuir à medida que computadores mais rápidos forem sendo desenvolvidos EXEMPLO 12 Mostre que 3x2 8x log x é Θx2 É importante saber quanto tempo um computador precisa para resolver um problema Por exemplo se um algoritmo necessita de 10 horas pode ser melhor gastar o tempo do computador e dinheiro para resolver este problema Mas se um algoritmo necessita de 10 bilhões de anos para resolver um problema seria irracional usar recursos para implementálo Em dois fenômenos mais interessantes da tecnologia moderna é o grande aumento da velocidade e da memória dos computadores Outro fator importante que diminuiu o tempo necessário para resolver problemas é o processamento paralelo que é a técnica de realizar sequências de operações simultaneamente Algoritmos eficientes incluindo muitos algoritmos com complexidade temporal polinomial por um problema mostram melhorias significativas da tecnologia Entretanto essas melhorias tecnológicas oferecem uma pequena ajuda na superação da complexidade temporal de algoritmos exponenciais Com o crescimento da velocidade de computação o aumento da memória do computador e o uso dos algoritmos que tiram vantagem do processamento paralelo muitos problemas eram considerados impossíveis de ser solucionados cinco anos atrás são resolvidos rapidamente e certamente daqui a cinco anos esta proposição continuará sendo verdadeira Solução Começo 0 log x x2 temos que 3x2 8x log x 11x2 para x 1 Consequentemente 3x2 8x log x Θx2 e log x Θx Qual o maior valor de n para que se possa resolver um um segundo um problema que usa um algoritmo que necessita de dn operações binárias em que cada operação é realizada em 109 segundos com os seguintes valores para fn a log n b n c n² d n Quanto tempo um algoritmo leva para resolver um problema nessa sequência se ele usa 2n 2n operações binárias cada uma demorando 109 segundos com os seguintes valores para n a 10 b 20 c 50 d 100 De quanto tempo um algoritmo que usa 2n operações binárias precisa se a operação leva uns tempos abaixo a 106 segundos b 109 segundos c 1012 segundos Determine o menor número de comparações eu realmente desempenharia ao realizar uma sequência de n elementos usando o Algoritmo 1 da Seção 31 b usada para localizar um elemento de uma lista com n termos da busca binária Um algoritmo de chamado de ótimo para uma solução ou problema de uma determinada operação é não houver algoritmo para resolver este problema usando números inteiros não a Mostre que o Algoritmo 1 da Seção 31 é um algoritmo ótimo com relação ao número de comparações dos números inteiros Nota As comparações usadas para contar o argumento não está em questão aqui b O algoritmo de busca binária é ótimo com relação ao número de comparações de números inteiros não incluindo as comparações usadas para contar o argumento Descreva a complexidade temporal do pior caso medida em termos de comparações do algoritmo de busca binária descrito no Exercício 27 da Seção 31 Descreva a complexidade temporal do pior caso medida em termos de comparações do algoritmo de busca descrito no Exercício 28 da Seção 31 Analise a complexidade temporal de pior caso do algoritmo que você construiu no Exercício 29 da Seção 31 para localizar uma moeda em uma lista de números inteiros não decrescentes Analise a complexidade de tempo do algoritmo de busca em ordem de 10000000 Um fato útil é que o termo principal de um polinômio determina sua ordem Por exemplo se fx ax3 bx2 cx d então f x é de ordem x3 Isto é confirmado pelo Teorema 4 cuja demonstração foi deixada como um exercício no final deste ciclo quatro seções da teoria dos números Vamos desenvolver os conceitos básicos da teoria dos números usados na ciência da computação Nesta seção recordaremos os conceitos básicos dos números primeos e concentraremos nossas discussões sobre os máximos divisores Na Seção 35 descreveremos diversos algoritmos importantes da teoria dos números relacionando o conteúdo das seções 31 e 33 sobre algoritmos e sua complexidade com as noções introduzidas nesta seção e na Seção 35 Por exemplo introduziremos os algoritmos que permitem encontrar o máximo divisor comum de dois números inteiros positivos e realizar aritmética computacional usando expansões binárias Por fim na Seção 37 continuaremos nosso estudo sobre teoria dos números introduzindo alguns resultados importantes e suas aplicações para a aritmética computacional e a criptografia a partir das mensagens secretas Consideramos que temos a liberdade de explorar e usar o que aprendeu sobre métodos e estratégias de desenvolvimento para uma nova construção As ideias que vamos desenvolver nesta seção são baseadas na noção de divisibilidade A divisão de um número inteiro por um número inteiro positivo produz um quociente e um resto Trabalhar com esses restos conduiz à aritmética modular que é usada pela ciência da computação Será discutido a construção de números pseudoaleatórios determinação de localizações na memória para avigentar um computador e codificação e decodificação de mensagens Divisão Quando um número inteiro é dividido por um segundo número inteiro diferente de zero o quociente pode ou não ser um número inteiro Por exemplo 123 4 é um número inteiro em contra posição 114 275 não é Isto nos leva à Definição 1 SE a e b são números inteiros com a 0 dizemos que a divide b se houver um número inteiro c de modo que b ac Quando a divide b dizemos que b é um fator de a e que b é um múltiplo de a A notação a b indica que a divide b Escrevemos ab quando a não divide b Lembrese Podemos expressar a b usando quantificadores como cac b em que o universo do discurso é o conjunto dos números inteiros Na Figura 1 uma linha numérica indica quais números inteiros são divisíveis pelo número inteiro positivo d EXEMPLO 1 Determine se 3 7 e se 3 12 Solução Temos que 3 não divide 7 pois 73 não é um número inteiro Por outro lado 3 12 pois 123 4 EXEMPLO 2 Considere n e d como números inteiros positivos Quantos números inteiros positivos não excedentes a n são divisíveis por d Solução Os números inteiros positivos divisíveis por d são todos os números inteiros na forma dk em que k é um número inteiro positivo Assim o número de inteiros positivos divisíveis por d que não excedem a n é igual ao número de inteiros k com 0 k n Então há nd números inteiros positivos não excedentes a n Algumas das propriedades básicas da divisibilidade de números inteiros são dadas pelo Teorema 1 FIGURA 1 Números Inteiros Divisíveis pelo Número Inteiro Positive d TEOREMA 4 Considere fx anxn an1xn1 a1x a0 em que an 0 Então fx é de ordem xn TEOREMA 1 Sejam a b e c números inteiros Então i se a b e a c então a b c ii se a b então a bc para todo número inteiro c iii se a b e b c então a c Demonstração Daremos uma demonstração direta do i Suponha que a b e a c Então a partir da definição de divisibilidade temos que números inteiros a e t com b ac Assim b c as at as t Então a divide b c Isto estabelece o item i do teorema As demonstrações dos itens ii e iii são deixadas como exercício para o leitor O Teorema 1 tem sua consequência útil COROLÁRIO 1 Se a b e c são números inteiros tal que a b c então a mb nc sempre que m e n forem números inteiros Demonstração Daremos uma demonstração direta A partir do item ii do Teorema 1 temos que a mb e a nc sempre que m e n forem números inteiros A partir do item i do Teorema 1 temos que a mb nc O Algoritmo de Divisão Quando um número inteiro é dividido por um número inteiro positivo há um quociente e um resto como o algoritmo de divisão mostra TEOREMA 2 O ALGORITMO DE DIVISÃO Considera e como um número inteiro e d como um número inteiro positivo Então haverá números inteiros q e r únicos com 0 r d tal que a dq r Apresentamos a demonstração do algoritmo de divisão no Exemplo 5 e no Exercício 37 da Seção 42 Lembrese O Teorema 2 não é realmente um algoritmo Por que não No entanto usamos esta notação convencional tradicional DEFINIÇÃO 2 Na equação dada no algoritmo de divisão d é chamado de divisor a é chamado de dividendo q é chamado de quociente e r é chamado de resto Esta notação é usada para expressar o quociente e o resto q a div d r a mod d Os exemplos 3 e 4 ilustram o algoritmo de divisão EXEMPLO 13 Os polinômios 3x3 10x7 2212x 1444 19 18x1 x9 40001x8 100 003x são de ordem x7 x8 e x9 respectivamente EXEMPLO 3 Quais são o quociente e o resto quando 101 é dividido por 11 Solução Temos 101 11 9 2 Assim o quociente quando 101 é dividido por 11 é 9 101 div 11 e o resto é 2 101 mod 11 EXEMPLO 4 Quais são o quociente e o resto quando 11 é dividido por 3 Solução Temos 11 34 1 Assim quando 11 é dividido por 3 o quociente é 4 11 div 3 e o resto é 1 11 mod 3 Note que o resto não pode ser negativo Consequentemente o resto não é 2 mesmo se 11 33 2 porque r 2 não satisfaz 0 r 3 Note que o número inteiro a é divisível pelo número inteiro d se e somente se o resto for zero quando a é dividido por d Aritmética Modular Em algumas situações nos preocupamos apenas com o resto de um número inteiro quando ele é dividido por um determinado número inteiro positivo Por exemplo quando perguntamos que horas serão daqui a 50 horas em relógio de 24 horas nos preocupamos apenas com o resto quando 50 mais a hora atual é dividido por 24 Como estamos tratando esses restos temos uma notação especial para eles Temos uma notação para indicar que dois números inteiros têm o mesmo resto quando eles são divididos pelo número inteiro positivo m DEFINIÇÃO 3 Se a e b forem números inteiros e m for um número inteiro positivo então a é congruente a b módulo m se a b 0 Usamos a notação a b mod m para indicar que a é b módulo m Se a e b não forem congruentes módulo m escrevemos a b mod m A conexão entre as notações usadas quando trabalhamos com restos tornase clara com o Teorema 3 Infelizmente como Knuth observou a notação Θ grande é normalmente utilizada para escritores sem cuidado como se tivesse o mesmo significado da notação Teta grande Mantinha isto em mente quando você viu a notação Θ grande sendo usada A crescente tendência tem sido a relação que usar a notação Teta grande sempre que merecese uma limitação superior e uma inferior em relação ao tamanho de uma função Teorema 5 Considere m como um número inteiro positivo Seja a b mod m e c d mod m então a c b d mod m e ac bd mod m Demonstração Como a b mod m c d mod m há números inteiros s e t com b a sm e c m tm Assim b d a sm c tm ac mrs tm e Assim a c b d mod m e ac bd mod m EXERCÍCIOS Nos exercícios de 1 a 14 para estabelecer uma relação O grande encontre os parâmetros C e k tal que fx C gx sempre que x k Como 7 2 mod 5 e 11 1 mod 5 temos que a partir do Teorema 5 18 7 11 2 1 3 mod 5 e que 77 7 11 2 1 2 mod 5 Precisaremos do corolário a seguir do Teorema 5 da Seção 44 1 Determine se cada uma destas funções é O As funções de hashing podem ser facilmente avaliadas para que os arquivos possam ser encontrados rapidamente A função de hashing hk k mod m tem esta característica para encontrar hk precisamos apenas computar o resto quando k é dividido por m Além disso a função de hashing deve ser subjetiva para que os dados de localizações de memória sejam utilizadas A função hk k mod m também satisfaz esta propriedade Por exemplo quando m 111 o registro do cliente com o número de Seguro Social 064212848 é projetado para a localização na memória 14 porque h064212848 064212848 mod 111 14 a fx x Encontre contraexemplos para cada uma das proposições abaixo sobre congruências b fx 3x 7 Qual a sequência de números pseudoaleatórios gerados usando o gerador de congruência linear xn1 4xn 1 mod 7 com origem x0 2 c fx log x 12 44 19 24 14 20 8 13 19 7 4 15 0 17 10 d fx 5 log x 35 Os Números Primos e os Máximos Divisores Comuns e fx x O TEOREMA FUNDAMENTAL DA ARITMÉTICA Todo número inteiro positivo maior que 1 pode ser escrito unicamente como primo ou como o produto de dois ou mais primos em que o valor dos fatores primos são escritos em ordem não decrescente de tamanho 2 Determine se cada uma destas funções é O Encontre a fatoração em números primos de 7007 a fx 17x 11 O progresso em encontrar os primos de Mersenne tem sido constante desde que os computadores foram inventados No começo de 2006 43 primos de Mersenne conhecidos em comparação a 1990 eram apenas 12 O maior primo de Mersenne conhecido novembre 2006 é 230 402 457 1 um número com mais de milhões de dígitos que foi anunciado como número primo em dezembro de 2005 Um grande esforço foi feito pelo Great Internet Mersenne Prime Search GIMPS na pesquisa de novos primos de Mersenne inclusive com implicações práticas Um teste de controle de qualidade para supercomputadores foi fazer uma cópia do teste de LucasLehmer que estabeleceu um novo grande primo de Mersenne b fx x2 1000 Usar a tentativa de divisão como o Teorema 2 nos dá procedimentos para fatoração e testes a fim de verificar se um número é primo Entretanto esses procedimentos não são algoritmos eficientes algoritmos muito práticos e eficientes que esses foram desenhados para verificar se um número é primo e transformarse importantes nas aplicações de fatores nos ramos da criptografia Isso levou a um grande interesse em desenvolver algoritmos eficientes para os fatores Procedimentos mais inteligentes foram desenvolvidos nos últimos 30 anos para garantir que os primos grandes de forma mais eficiente Entretanto mesmo os métodos de fatoração mais podem tendo sido desenvolvidos ao mesmo tempo fatorar grandes números demanda um extraordinário No entanto o desejo de fatorar grandes números interessa a muitas pessoas Há um grande esforço na Internet para fatorar números grandes especialmente aquelas com formato especial de k em que k é um número inteiro positivo grande tais números são chamados de números de Cunningham De tempos em tempos há uma lista dos Dez mais Procurados para a fatoração de números muito grandes desse tipo c fx x x x Embora não tenha sido encontrada uma demonstração da conjectura de Goldbach muitos matemáticos acreditam que ela seja verdadeira Vários teoremas foram demonstrados usando métodos complicados de análise da teoria dos números que estão fora do alcance deste livro estabelecendo resultados mais fracos que a conjectura de Goldbach Entre esses há resultados sobre o inteiro positivo maior que 2 e a soma de no máximo estes números primos demonstrado em 1995 por O Ramare e que todo número inteiro positivo suficientemente grande é a soma de um primo e de um número que ou é primo ou é o produto de dois primos demonstrado em 1966 por R Chen Talvez a conjectura de Goldbach seja comprovada num futuro não muito distante 3 Use a definição de f é Ogx para mostrar que Qual é o mínimo divisor comum de 17 e 22 2x 9x2 7 6 log x Determine se cada um destes números inteiros é primo a 21 b 29 c 71 d 143 4 Mostre que x3 2x2x 1 é Ox2 O mínimo múltiplo comum dos números inteiros positivos a e b é o menor inteiro positivo divisível por ambos a e b O mínimo múltiplo comum de a e b é indicado por mmca b 5 Mostre o menor número ímpar r para cada uma destas funções 36 Os Números Inteiros e os Algoritmos Introdução Como foi mencionado na Seção 31 o termo algoritmo originalmente referese aos procedimentos de realização de operações aritméticas usandose a representação decimal dos números inteiros Esses algoritmos adaptados ao seu com representações binárias são a base da aritmética computacional Eles forneceram boas ilustrações do conceito de algoritmo e de sua complexidade Por essas razões eles serão discutidos nesta seção Há muitos algoritmos importantes que envolvem números inteiros além daqueles usados em aritmética incluindo o algoritmo de Euclides que é um dos mais usados e talvez o mais antigo em matemática Descreveremos também um algoritmo que permite encontrar a expansão do número b de um número inteiro positivo para qualquer base b e para a potenciação modular um algoritmo importante em criptologia Representações de Números Inteiros No cotidiano usamos a notação decimal para representar os números inteiros Por exemplo 965 é usado para indicar 9 102 6 101 5 Entretanto é conveniente usar bases diferentes de 10 Em particular os computadores geralmente usam a notação binária base 2 quando trabalham com aritmética a notação octal base 8 ou hexadecimal base 16 quando representam caracteres tais como letras ou dígitos No entanto podemos usar qualquer número inteiro positivo maior que de Por essa razão indicamos números inteiros Isto é estabelecido pelo Teorema 1 TEOREMA 1 Considere b como um número inteiro positivo maior que 1 Então se n for um número inteiro positivo pode ser expresso unicamente na forma n akbk ak1bk1 a1b a0 em que k é um inteiro não negativo a0 ak são números inteiros não negativos menores de b e ak 0 Uma demonstração desse teorema pode ser feita por meio da indução matemática um método de demonstração que será discutido na Seção 41 e que pode ser encontrado também em Ro05 A representação de n dada no Teorema 1 é chamada de expansão na base b A expansão na base b de n é indicada por ak ak1 a0b Por exemplo 24510 representa 2 102 4 101 5 165 EXPANSÕES BINÁRIAS Ao escolher 2 como base temos as expansões binárias dos números inteiros Na notação binária cada dígito é 0 ou 1 Em outras palavras em números inteiros um número inteiro n apenas pode exibir uma cadeia de bits As expansões binárias expansões que são variantes das expansões binárias são usadas por computadores para representar e executar aritmética como números inteiros EXEMPLO 1 Qual é a expansão decimal do número inteiro que tem 1 0101 111₂ como expansão binária Solução Temos 1 0101 111₂ 1 28 0 27 1 26 0 25 1 24 1 23 1 22 0 21 1 20 1 0 64 0 16 8 4 0 1 351 EXPANSÕES HEXADECIMAIS Dezesseis é outra base usada em ciência da computação A expansão na base 16 de um número inteiro é chamada de expansão hexadecimal Dezesseis dígitos diferentes são usados para representar tais expansões Geralmente os dígitos usados são 0 a fn 2n log xr 1 2 3 4 5 6 7 8 9 A B C D E e F em que as letras de A a F representam os dígitos correspondentes aos números de 10 a 15 em notação decimal EXEMPLO 2 Qual é a expansão decimal da expansão hexadecimal de 2A0EB₁₆ Solução Temos 2A0EB₁₆ 2 164 10 163 14 162 16 11 175627₁₀ Cada dígito hexadecimal pode ser representado usandose quatro bits Por exemplo vemos que 1110 0101₂ E₁₆ pois 1110₂ E₁₆ e 0101₂ 5₁₆ Bytes que são cadeias de bits de extensão oito podem ser representados por dois dígitos hexadecimais b fn 3n 17ν2 Vemos que a₁ é o segundo dígito à direita da expansão na base b de n Continuamos este procedimento dividindo sucessivamente os quocientes por b obtendo dígitos adicionais na base b como restos Este processo termina quando obtemos um quociente igual a zero EXEMPLO 3 Encontre a expansão na base 8 ou octal de 12345₁₀ Solução Primeiro divida 12345 por 8 para obter 12345 8 1543 1 Dividindo sucessivamente os quocientes por 8 temos 1 543 8 192 7 192 8 24 0 24 8 3 0 3 8 0 3 Como os restos são os dígitos da expansão na base 8 de 12345 temos que 12345₁₀ 30071₈ EXEMPLO 4 Encontre a expansão hexadecimal de 177130₁₀ Solução Primeiro divide 177130 por 16 para obter 177130 16 11070 10 Dividindo sucessivamente os quocientes por 16 temos 11070 16 691 14 691 16 43 3 43 16 2 11 2 16 0 2 Como os restos são os dígitos da expansão hexadecimal base 16 de 177130₁₀ temos que 177130₁₀ 2B3EAA₁₆ Lembrese de que os números inteiros 10 11 e 14 correspondem aos dígitos hexadecimais A B e E respectivamente EXEMPLO 5 Encontre a expansão binária de 241₁₀ Solução Primeiro divida 241 por 2 para obter 241 2 120 1 Dividindo sucessivamente os quocientes por 2 temos que 120 2 60 0 60 2 30 0 30 2 15 0 15 2 7 1 7 2 3 1 3 2 1 1 1 2 0 1 Como os restos são os dígitos da expansão binária base 2 de 241₁₀ temos que 241₁₀ 1111 0001₂ O pseudocódigo dado no Algoritmo 1 encontra a expansão na base b ak a0ₐ do número inteiro n escrito na base 10 ALGORITMO 1 Construção de Expansões na Base b procedimento expansão na base b n inteiro positivo q₀ n k 0 enquanto q₀ 0 começe aₖ q₀ mod b q₀ q₀b k k 1 fim end a expansão na base b de n é ak a₀ₐ c fn n3 5 log n4 1 TABELA 1 Representação Hexadecimal Octal e Binária dos Inteiros de 0 a 15 Decimal 0 1 2 3 4 5 6 7 8 9 A B C D E F Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F Octal 0 1 2 3 4 5 6 7 10 11 12 13 14 15 Binaría 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 No Algoritmo 1 q representa o quociente obtido pelas divisões sucessivas por b começando com q n Os dígitos das expansões na base b são os restos dessas divisões e são dados por q mod b O algoritmo termina quando um quociente q 0 é alcançado Lembrese Note que o Algoritmo 1 pode ser pensado como um algoritmo voraz A conversão entre as expansões binária e hexadecimal é extremamente fácil pois cada dígito hexadecimal corresponde a um bloco de quatro dígitos binários sendo esta correspondência mostrada na Tabela 1 sem os zeros iniciais Deixamos a demonstração deste fato para os exercícios 11 e 12 no final desta seção Esta conversão é ilustrada no Exemplo 6 Mostre que se f é g e gx for um conjunto de números reais para o conjunto de números reais então fgx se é somente se gx for Ogx EXEMPLO 6 Encontre a expansão hexadecimal de 11 1110 1100₂ e a expansão binária de ABD₁₆ Solução Para converter 11 1110 1100₂ em uma notação hexadecimal agrupamos os dígitos binários em blocos de quatro adicionando zeros iniciais no começo do bloco mais à esquerda se necessário Esses blocos são 0011 1110 1100 que correspondem aos dígitos hexadecimais 3 E C e respectivamente Consequentemente 11 1110 1100₂ 3E C₁₆ Para converter ABD₁₆ em notação binária substituímos cada dígito hexadecimal por um bloco de quatro dígitos binários Esses blocos são 1010 1011 1101 Consequentemente ABD₁₆ 1010 1011 1101₂ Mostre que 3x2 8x log x e somente se fx for Ogx EXEMPLO 7 Adição de a 1110₂ b 1011₂ Solução Seguindo o procedimento especificado no algoritmo primeiro note que a₀ b₀ 0 1 0 2 1 em que c₀ 0 e s₀ 1 Então como a₁ b₁ c₀ 1 1 0 2 0 0 temos que c₁ 1 e s₁ 0 Continuando a₂ b₂ c₁ 1 0 1 2 0 0 em que c₂ 1 e s₂ 0 Por fim a₃ b₃ c₂ 1 1 1 1 2 1 temos que c₃ 1 e s₃ 1 Isto significa que c₄ c₃ 1 Assim s a b 1 1001₂ Esta adição é mostrada na Figura 1 O algoritmo de adição pode ser descrito usandose o pseudocódigo como vemos a seguir Exprima a relação em que fx é Ogx usando um esquema 110 e ab2 22 1102 1 22 110002 Para encontrar o produto adicione 1102 00002 e 110002 Realizar essas adições usando o Algoritmo 2 incluindo os bits zeros iniciais quando necessário mostra que ab 1 11102 Esta multiplicação é ilustrada na Figura 2 Mostre os gráficos das funções fx C1gx e C2gx assim como f como não é o mesmo Para somar os números inteiros ab dej 0 a j n 1 é necessária a adição de um número inteiro com m bits um inteiro com n 1 bits e um inteiro com 2n bits Sabemos a partir do Exemplo 8 que cada uma dessas adições requer On adições de bits Consequentemente um total de On2 adições de bits são necessárias para todas as n adições Explique o que significa função ser O EXEMPLO 11 Use o Algoritmo 5 para encontrar 3644 mod 645 Solução O Algoritmo 5 inicialmente designa x 1 e potencia 3 mod 645 3 Na computação de 3644 mod 645 este algoritmo determina 31 mod 645 para i 1 9 elevando ao quadrado sucessivamente e reduzindo pelo módulo 645 Se e 1 em que a versão b não é ajésima posição na expansão binária de 644 multiplicamos o valor atual x por 31 mod 645 e reduzimos o resultado módulo 645 Aqui estão os passos percorridos Explique o que significa função ser Θ Como qualquer divisor comum de 91 e de 14 também divide 91 14 6 7 e qualquer divisor comum de 14 e de 7 divide 91 temos que mdc91 14 mdc14 7 Continuando com a divisão de 14 por 7 obtemos 14 7 2 Como 7 divide 14 temos que mdc14 7 7 Além disso como mdc287 91 mdc91 14 mdc14 7 7 o problema original foi resolvido Descobriremos agora como o algoritmo de Euclides funciona em questões mais gerais Usando restos sucessivos para reduzir o problema de encontrar o máximo divisor comum de dois números inteiros positivos nos permite encontrar números inteiros novos até um dos índices chegar a zero O algoritmo de Euclides é baseado no resultado a seguir sobre máximos divisores comuns e o algoritmo de divisão Dê uma estimativa de Θ grande para cada uma destas funções EXEMPLO 12 Encontre o máximo divisor comum de 414 e 662 usando o algoritmo de Euclides Solução Usando sucessivamente o algoritmo de divisão temos 662 414 1 248 414 248 1 166 248 166 1 82 166 82 2 2 82 2 41 Assim mdc414 662 2 pois 2 é o último resto diferente de zero O algoritmo de Euclides é expresso em pseudocódigo no Algoritmo 6 a fn n 2n2 logn2 1 7 Converta ABCDEF16 da expansão hexadecimal para a binária 8 Converta cada um destes números inteiros da notação binária para a hexadecimal a 111 0111 b 1010 1010 c 111 0111 0111 9 Converta 1000 0110 10112 da expansão binária para a hexadecimal 10 Converta 1 0000 0010 00112 da expansão binária para a hexadecimal 11 Mostre que a expansão binária de um número inteiro positivo pode ser obtida a partir de sua expansão binária a partir do agrupamento de blocos de quatro dígitos binários adicionando bits iniciais se necessário e transcrevendo cada bloco de quatro dígitos binários em um único dígito hexadecimal 20 Dê uma estimativa O grande para cada uma destas funções 37 Aplicações da Teoria dos Números Introdução A teoria dos números tem muitas aplicações especialmente na ciência computacional Na Seção 34 descreveremos muitas dessas aplicações incluindo as funções de hashing a construção de números pseudoaleatórios e os códigos de substituição Neste seguimento continuaremos com nossa introdução à teoria dos números desenvolvendo alguns resultados chave apresentando duas aplicações importantes um algoritmo para a realização da aritmética com números inteiros grandes e um tipo de sistema de criptografia criado recentemente chamado de sistema de chave pública Em tal sistema não é necessariamente manter chaves secretas codificadas porque o conhecimento de uma chave deste tipo não ajuda na decodificação das mensagens em geral Chaves de codificação privadas são usadas para decodificar mensagens Antes de desenvolver essas aplicações desenvolveremos alguns resultadoschave que têm um papel central nas teorias dos números e em suas aplicações Por exemplo mostraremos como usar um sistema de congruência linear modular de pares de primos entre si usando o Teorema Chinês do Resto e então mostramos como usar esse resultado como base para realizar cálculos da aritmética com números inteiros grandes Discutiremos o Pequeno Teorema de Fermat e o conceito de um pseudoprimo e mostraremos como usar esses conceitos para desenvolver um criptossistema de chave pública Como a função g em sua estimativa fx é Ogx use uma função simples e de menor ordem 37 Aplicações da Teoria dos Números Alguns Resultados Úteis Um resultado importante que usaremos nesta seção é que o máximo divisor comum de dois números inteiros a e b pode ser expresso na forma sa tb em que s e t são números inteiros Em outras palavras mdca b pode ser expresso como uma combinação linear com coeficientes inteiros de a e b Por exemplo mdc4 14 2 e 2 24 114 Afirmamos este fato como Teorema 1 TEOREMA 1 Se a e b são números inteiros positivos então existem inteiros s e t tal que mdca b sa tb Não faremos uma demonstração formal do Teorema 1 aqui para isto veja o Exercício 36 na Seção 42 e também Ro05 mas vamos fornecer o exemplo de um método para encontrar a combinação linear de dois números inteiros iguais ao seu máximo divisor comum Nesta seção vamos supor que podemos encontrar uma combinação linear de cofatores inteiros O método consiste em trabalhar seguindo os divisões do algoritmo de Euclides Também descrito no preâmbulo do Exercício 48 um algoritmo chamado do algoritmo de Euclides estendido pode ser usado para expressar mdca b como uma combinação linear de a e b EXEMPLO 1 Expresse o mdc252 198 18 como uma combinação linear de 252 e 198 Solução Para mostrar que mdc252 198 18 o algoritmo de Euclides usa as seguintes divisões 252 1 198 54 198 3 54 36 54 1 36 18 36 2 18 Vemos pela terceira divisão que podemos expressar mdc252 198 18 como uma combinação linear de 54 e 36 Verificamos que 18 54 1 36 A segunda divisão nos mostra que 36 198 3 54 Substituindo essa expressão por 36 na equação anterior podemos expressar 18 como uma combinação linear de 54 e 198 Temos 18 54 1198 354 54 1 198 3 54 4 54 1 198 A primeira divisão nos mostra que 54 252 1 198 Substituindo essa expressão por 54 na equação anterior podemos expressar 18 como uma combinação linear de 252 e 198 Concluímos que 18 4 252 1 198 4 252 5 198 o que completa a solução a Mostre que 3x 7 Θ3 Usaremos o Teorema 1 para produzir muitos resultados úteis Um de nossos objetivos será demonstrar parte do Teorema Fundamental da Aritmética que diz que um número inteiro positivo tem pelo menos uma fatoração em números primos Mostraremos que se um número inteiro positivo tem uma fatoração em números primos em que os primos são escritos em ordem não decrescente então esta fatoração é única Primeiro precisamos desenvolver alguns resultados sobre divisibilidade LEMA 1 Se a b e c são números inteiros positivos tal que mdca b 1 a bc então a c Demonstração Como mdca b 1 pelo Teorema 1 existem números inteiros s e t tal que sa tb 1 Multiplicando os dois lados desta equação por c obtemos sac tbc c Usando o Teorema 1 da Seção 34 podemos usar esta última equação para mostrar que a c Pelo item ii daquele teorema a bc Como a sac e a bc a partir do item i daquele mesmo teorema concluímos que a divide sac bc e assim a c Isto finaliza a demonstração Utilizaremos a seguinte generalização do Lema 1 na demonstração de unicidade da fatoração em números primos A demonstração do Lema 2 será apresentada no Exercício 60 na Seção 41 porque ela pode ser mais bem trabalhada usandose o método de indução matemática que será abordado naquela seção LEMA 2 Se p é um número primo e p a₁a₂aₖ em que cada aₖ é um número inteiro então p aₖ para algum i Mostraremos agora que a fatoração de um número inteiro em primos é única Ou seja mostraremos que todo número inteiro pode ser escrito como o produto de números primos em ordem não decrescente do máximo de uma maneira Isto é parte do Teorema Fundamental da Aritmética Demonstramos a outra parte que todo número inteiro pode ser fatorado em números primos na Seção 42 Demonstração da unicidade da fatoração em primos de um número inteiro positivo Utilizaremos uma demonstração por contradição Suponha que o número inteiro positivo n possar ser escrito como o produto de números primos de duas maneiras diferentes diagnos n p₁p₂pₖ q₁q₂qₕ sendo que cada pₖ e qₕ são números primos tal que p₁ p₂ pₖ e q₁ q₂ qₕ Quando retiramos todos os primos comuns das duas fatorações temos p₁ p₂ pₖ q₁ q₂ qᵢ em que nenhum primo aparece em nenhum dos lados desta equação ou seja todos os fatores são diferentes e p e q são números inteiros positivos Pelo Lema 1 temos que pₖ qᵢ desde qᵢ é para algum k Como nenhum primo divide outro número primo isto é impossível Consequentemente pode existir no máximo uma fatoração de n em números primos em ordem não decrescente b Mostre que 2x2 x 7 Θx2 O Lema 1 também pode ser usado para demonstrar um resultado da divisão dos dois lados de uma congruência pelo mesmo número inteiro Mostramos Teorema 5 da Seção 34 que podemos multiplicar os dois lados de uma congruência pelo mesmo número inteiro Entretanto dividir os dois lados de uma congruência por um número inteiro não produz sempre uma congruência válida como mostra o Exemplo 2 c Mostre que logx2 Θlog x A demonstração do Teorema 3 descreve um método para encontrar o inverso de a módulo m quando a e m são primos entre si encontre uma combinação linear de a e m que seja igual a 1 ela pode ser feita trabalhando de trás para frente os passos do algoritmo de Euclides o coeficiente de nesta combinação linear é um inverso de a módulo m Ilustraremos este procedimento no Exemplo 3 Mostre que log x é Θlog x Este enigma pode ser transcrito como a seguinte questão Quais são as soluções para os sistemas de congruência x 2 mod 3 x 3 mod 5 x 2 mod 7 Resolvaremos esse sistema e o enigma de SunTzu ainda nesta seção Mostre que x é Ogx onde g é a função real x O Exemplo 6 ilustra como usar a construção dada na demonstração do Teorema 4 para resolver um sistema de congruências Resolveremos o sistema dado no Exemplo 6 chegando até o enigma de SunTzu Mostre que para todos os números reais e b com a 1 e b 1 se fx Olog x então fx Θlog x Suponha que fazer aritmética com números inteiros menores que 100 em um determinado processador seja mais rápido que fazer a aritmética com números inteiros maiores Podemos restringir todas as computações a números inteiros menores que 100 se representamos os números inteiros usando restos módulo pares de primos entre si Existem maneiras mais eficientes de determinar se um número inteiro n é primo De acordo com algumas fontes os matemáticos chineses acreditavam que n era primo se somente se 2n1 1 mod n Considera e como um número inteiro positivo Se n for um número inteiro positivo composto e bn1 1 mod n então n é chamado de pseudoprimo na base b Criptografia de Chave Pública Na Seção 34 introduzimos métodos para codificar mensagens com base em congruências Quando estes métodos são usados elas são sequências de caracteres sendo transcritas em números Codificação RSA No método de codificação RSA as mensagens são transcritas em sequências de números inteiros Isto pode ser feito transcrevendo cada letra em um número inteiro como foi feito com o código de César Codificamos cada bloco usando a função C M13 mod 2537 Computações que usam multiplicações modulares mostram que 181913 mod 2537 2081 e 141513 mod 2537 2182 A mensagem codificada é 2081 2182 Decodificação RSA A mensagem de texto puro pode ser rapidamente recuperada quando a chave de decodificação d um inverso de módulo p 1q 1 é conhecida Tal que mdce p 1q 1 1 Para verificar isso note que se d e1 mod p 1q 1 há um número inteiro k tal que e d 1 kp 1q 1 Portanto Cd Med M M1 M mod n Pelo Pequeno Teorema de Fermat supondo que mdcM p mdcM q 1 que mantido com exceção de casos raros temos que Mp1 1 mod p e Mq1 1 mod q Consequentemente Cd M Meφp1 M 1 M mod q Como mdcp q 1 temos que pelo Teorema Chinês do Resto Cd M mod pq O Exemplo 12 ilustra como decodificar mensagens enviadas usando o criptossistema RSA EXEMPLO 12 Recebemos a mensagem codificada 0981 0461 Qual é a mensagem decodificada se ela tiver sido codificada usandose o código RSA do Exemplo 11 Solução A mensagem foi codificada usandose o criptossistema RSA com e 43 e ϕ exponete 13 Como mostra o Exercício 4 e 937 é um inverso de 13 módulo 246 Usamos 937 como nosso expoente de decodificação Consequentemente para decodificar um bloco C computamos P C937 mod 2537 da fatoração de n Acreditase que a fatoração seja um problema difícil oposto a encontrar os primos grandes p e q o que pode ser feito rapidamente O método de fatoração mais eficiente conhecido como de 2005 requer bilhões de anos para fatorar números inteiros com 400 dígitos Consequentemente quando p e q são números primos com 200 dígitos as mensagens codificadas usandose n pq como módulo não podem ser encontradas em um tempo razoável a menos que os números primos p e q sejam conhecidos A pesquisa ativa está a caminho de encontrar novas maneiras para tornar mais eficiente a fatoração de números inteiros Aqueles que eram considerados recentemente e muitos anos atrás muito grandes para serem fatorados em um tempo razoável agora podem ser fatorados rapidamente Números inteiros com mais de 100 dígitos assim como combinações com mais de 15 dígitos têm sido fatorados em um trabalho em equipe Quando novas técnicas e fatoração foram descobertas será necessário usar números primos maiores para assegurarg o segredo das mensagens Infelizmente as mensagens que foram consideradas seguras anteriormente podem ser salvas e decodificadas por vários destinatários quando o fator n pq tornase acessível na chave pública RSA O método RSA é agora mundialmente utilizado Entretanto os criptossistemas estão sujeitos a ser chaves privadas O uso da criptografia de chave pública o sistema RSA está crescendo Entretanto há aplicações que usam sistemas de chaves privadas Por exemplo um criptossistema de chave pública como o RSA pode ser usado para distribuir mensagens para pares de indivíduos quando eles desejam se corresponder Essas mensagens então um sistema de chave privada para codificar e decodificar mensagens 1 Expresse o máximo divisor comum de cada par de números inteiros como combinação linear destes inteiros a 10 11 b 21 44 c 34 55 d 117 413 e 123 2347 f 3454 4666 g 9999 1111 2 Expresse o máximo divisor comum de cada par de números inteiros como combinação linear destes inteiros a 9 11 b 33 44 c 51 201 d 2002 2339 e 3457 4609 f 10001 13422 3 Mostre que 937 é um inverso de 13 módulo 2436 4 Encontre um inverso de 4 módulo 9 5 Encontre um inverso de 2 módulo 17 6 Encontre um inverso de 19 módulo 141 7 Encontre um inverso de 144 módulo 233 8 Mostre que se a e m forem inteiros primos entre si então o inverso de a módulo m é único módulo m Dica Suponha que haja duas soluções e veja o que acontece modulo 2 9 Mostre que um inverso de a módulo m não existe se m não é primo 10 Resolva a congruência 4x 5 mod 17 11 Resolva a congruência 2x 7 mod 11 k é um número inteiro não negativo Dica Use o Pequeno Teorema de Fermat e o Exercício 41 Uma matriz é uma disposição retangular de números Uma matriz com m linhas e n colunas é chamada de matriz m n O plural de matriz é matrizes A soma de duas matrizes de mesmo tamanho é obtida pela adição dos elementos nas posições correspondentes As matrizes de tamanhos diferentes não podem ser somadas Quando AB são computados vemos que AB 14 4 8 9 7 13 8 2 A multiplicação de matrizes não é comutativa Ou seja se A e B são duas matrizes não é necessariamente verdade que AB sejam iguais De fato pode ser apenas um desses dois produtos seja definido Por exemplo se A é 2 x 3 e B é 3 x 4 então AB é definida e será 2 x 4 entretanto BA não é definida pois é impossível multiplicar uma matriz 3 x 4 por uma matriz 2 x 3 Em geral suponha que A seja uma matriz m x n e B seja uma matriz n x m Então AB é definida apenas quando n r e BA é definida apenas quando p m Além disso mesmo quando AB e BA forem definidas elas não terão o mesmo tamanho a não ser que m r n Assim se AB e BA são definidas e são do mesmo tamanho então A e B devem ser matrizes quadradas e de mesmo tamanho mesma ordem Além disso mesmo como A e B matrizes n x n AB e BA não são necessariamente iguais como demonstra o Exemplo 4 EXEMPLO 4 Considere A 1 2 cB 2 1 AB BA Solução Encontramos AB 3 2 e BA 4 3 Assim AB BA Algoritmos para a Multiplicação de Matrizes A definição do produto de duas matrizes nos leva um algoritmo que computa o produto de duas matrizes Suponha que C cij seja a matriz m x n que é o produto da matriz m x k A aij pela matriz k x n B bj O algoritmo baseado na definição do produto da matriz é expresso em pseudocódigo no Algoritmo 1 ALGORITMO 1 Multiplicação de Matrizes procedure multiplicacao de matriz A B matrizes for i 1 to m for j 1 to n begin cij 0 for g 1 to k cij cij aigbgj end C cij é o produto de A e B