Resumo (o que vem a seguir?)

RKA4JL - Parabéns! Chegamos em um ponto de ramificação em nossa lição. Algumas ideias diferentes foram introduzidas, então é importante nos orientarmos antes de avançarmos em várias direções. O que motivou essa lição? Bem, aprendemos sobre encriptação RSA. E o RSA dependia de duas coisas: a primeira é que a fatoração dos números primos é difícil. Então, se eu multiplicar dois números primos grandes, P1 e P2, e eu te der N, eu posso confiar que você levará muito tempo para encontrar esses primos, talvez mais que sua vida inteira. A segunda é que o RSA requer que aqueles primos grandes que gerei sejam fáceis, o que significa que eu poderia gerar rapidamente um número primo grande. Então, vamos retornar ao primeiro problema: a dificuldade da fatoração de primos. Bom, o que há na fatoração dos primos, ou simplesmente nos próprios números primos, que torna os problemas difíceis? Para descobrir isso nós começamos com o problema principal. Dado "x", "x" é primo ou composto? Esse é um teste de primariedade. Terminamos construindo algumas soluções para este problema, e fazendo isso percebemos que esse problema era computacionalmente caro. Ou seja, não há solução instantânea para esse problema. À medida que nosso número de entrada cresceu, a quantidade de tempo ou de passos envolvidos para um algoritmo encontrar a solução também cresceu. E o quanto ele cresceu? Nós realmente entenderemos melhor agora porque podemos predizer esse espaço de busca usando o teorema de números primos. Mas a verdadeira questão pode ser pensada como um gráfico onde, no eixo vertical, temos o número de passos que cada algoritmo precisa para ser executado. Então, você pode simplesmente entendê-lo como tempo. E no eixo "x" está o tamanho da entrada. Conforme o tamanho da entrada cresceu, também cresceu o tempo levado. O problema que tivemos é que a forma dessa curva é inaceitável porque nesse cenário, uma vez que N atinja até mesmo 20 dígitos, no pior dos casos, não podemos mais resolver o problema. E se jogássemos uma entrada de centenas de dígitos no nossa algoritmo, podemos concordar que ele não funcionaria. Então é praticamente impossível checar se um número grande como entrada é primo usando nossas estratégias atuais. Agora, vamos voltar ao primeiro ponto. De acordo com o nossa atual entendimento nesta lição, a fatoração deve ser mais difícil que um teste de primariedade, isto é, existem mais passos envolvidos em achar a fatoração prima de algum número versus apenas dizer se ele é um número primo ou não. Isso porque a fatoração requer que encontremos todos os fatores primos para alguma entrada N, enquanto o teste de primariedade apenas requer que encontremos um divisor. E um lembrete legal disso é que alguns usuários têm realmente transformado esses testes de primariedade em algoritmos de fatoração de primos simplesmente por repeti-lo após encontrar o primeiro divisor. Então, o teste de primariedade é apenas um tipo de uma sub-rotina dentro do algoritmo de fatoração principal. Então, se retornamos a este gráfico, um algoritmo de fatoração seria algo parecido com isso. Conforme a entrada cresce, nosso algoritmo de fatoração seria esta linha acima da linha do teste primariedade. E perceba que em qualquer situação nós sempre temos um limite computacional, ou seja, o número de passos primitivos que podemos calcular, que é baseado no poder computacional em qualquer situação dada e a quantidade de tempo que temos. E quando você pensar nisso como uma linha horizontal, ou um limiar nesse gráfico, qualquer coisa acima dessa linha está fora de alcance. Não é prático de resolver. E nessa lição estávamos limitados pela placa do computador do andarilho, que é bastante lenta, motivo pelo qual não podíamos executar testes de primariedade em números de até mesmo vinte dígitos. Contudo, mesmo se tivéssemos, digamos, mil computadores executando por um ano, isso simplesmente empurraria essa linha horizontal para cima, para um outro limiar. E isso nos permitiria executar testes em números maiores. Mas como se pode ver, sempre atingiríamos algum limite onde a entrada é tão grande que não podemos mais resolver os problemas. Agora, isso nos leva a vários tipos de questões interessantes. Identificarei dois, que serão os que vou explorar a seguir. Primeiro de tudo: até agora eu não tenho sido muito precisa sobre essas curvas de crescimento. Contudo, seria útil se, para qualquer algoritmo que você me desse, não importa o que ele esteja tentando resolver e não importa sequer em qual máquina ele esteja sendo executado, nós pudéssemos desenhar alguma curva de crescimento correspondente neste gráfico simplesmente olhando a descrição do algoritmo. Se nós pudéssemos fazer isso, poderíamos identificar categorias de certas formas de crescimento que nos diriam o quão difícil será resolver um problema. E dessa maneira, nós podemos julgar um logaritmo antes mesmo de o executarmos. Isso é muito importante para se pensar. E você poderia me entregar seu algoritmo escrito em um pedaço de papel e eu poderia vê-lo e dizer: "Eu sei que esse algoritmo não pode ser resolvido com o tamanho de entrada necessário". E isso nos leva a uma lição de complexidade de tempo, uma ferramenta conceitual incrivelmente importante que precisaremos. E se você já ouviu: "Isso é executado em tempo polinomial", ou "tempo exponencial", esses são termos que vieram da complexidade de tempo. Próximo. Muitos de vocês devem estar pensando: "Bom, como nós estamos gerando esses números primos aleatórios na prática?". Esse é o segundo ponto que mencionei sobre o RSA. Vamos apenas passar por isso rapidamente. Para gerar números primos grandes e aleatórios de centenas de dígitos, nós temos de seguir estas instruções: Gere um número aleatório e teste se ele é primo. Se é primo, nós terminamos. Se não, tente novamente até encontrarmos um número primo. Neste procedimento de três passos, o que é mais importante é o segundo passo. É testar se é primo. Se não pudermos fazer este passo, isso não funcionará. Então, como isso está funcionando atualmente? Bom, é baseado em uma alteração sutil da definição do nosso problema. E o mais importante: o uso da aleatoriedade. Isso nos leva a uma outra lição sobre algoritmos aleatórios. Finalmente, se houver qualquer outra pergunta importante que você tenha, por favor, poste-as abaixo e poderemos planejar lições. Por exemplo, existem algumas matemáticas mais profundas que ainda temos para explorar a fim de acelerar nosso atual teste experimental de primariedade da divisão aleatória. E o que mais você está pensando? Por favor, compartilhe abaixo.