YouTube

Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

Portuguese, Brazilian υπότιτλους

← Encriptação RSA - Passo 3

Πάρτε τον Κωδικό ενσωμάτωσης
8 Γλώσσες

Showing Revision 4 created 02/05/2015 by Alberto Oliveira.

  1. Há mais de 2 mil anos
    Euclides mostrou

  2. que todo número possui
    apenas uma fatoração prima,
  3. que pode ser vista como uma chave secreta.
  4. Acontece que a fatoração prima é um
    problema naturalmente complicado.
  5. Deixe-me explicar o que é fácil,
  6. e o que é difícil,
  7. introduzindo a Complexidade de Tempo.
  8. Todos nós já multiplicamos números antes
  9. e cada um tem seu modo
    para acelerar o processo.
  10. Se programarmos um computador
    para multiplicar números,
  11. ele pode fazer isso muito mais
    rápido do que um humano.
  12. Aqui está um gráfico que mostra
    o tempo necessário
  13. para um computador multiplicar
    dois números.
  14. E, claro, o tempo necessário
    para encontrar a resposta
  15. aumenta quando os números crescem.
  16. Note que o tempo de cálculo fica
    bem abaixo de 1 segundo
  17. mesmo com números
    bem grandes.
  18. Portanto, é fácil de ser feito.
  19. Agora compare isso com a fatoração prima.
  20. Se te pedem para encontrar
    a fatoração prima de 589,
  21. você notará que o problema
    parece mais difícil.
  22. Não importa a sua estratégia,
  23. você vai precisar de algumas tentativas
    para encontrar um divisor de 589.
  24. Com algum esforço, você perceberá
    que 19x31 é a fatoração prima.
  25. Se te pedissem para encontrar
    a fatoração prima de 437.231,
  26. você provavelmente desistiria
    e usaria um computador.
  27. Isso funciona bem para números pequenos,
  28. mas se usamos um computador para fatorar
    números cada vez maiores,
  29. há um efeito de fuga.
  30. O tempo necessário para realizar
    os cálculos cresce rapidamente,
  31. já que há mais passos envolvidos.
  32. À medida que os números crescem,
  33. o computador leva minutos, e então horas,
  34. e eventualmente, precisará
    de centenas ou milhares de anos
  35. para fatorar números enormes.
  36. Nós, portanto, dizemos que
    é um problema difícil,
  37. devido a essa taxa de crescimento
    do tempo necessário para resolver .
  38. Então fatoração foi o que Cock usou para
    desenvolver a solução do alçapão.
  39. Passo 1.
  40. Imagine que Alice gera um
    número primo aleatório
  41. com mais de 150 dígitos.
  42. Denote-o por P1.
  43. Então, um segundo número primo
    com quase o mesmo número de dígitos.
  44. Denote-o por P2.
  45. Ela então multiplica esses
    dois números primos
  46. para conseguir um número composto N,
  47. que possui mais de 300 dígitos.
  48. Esse passo de multiplicação
    levaria menos que 1 segundo.
  49. Nós até conseguimos fazer isso
    em um navegador de Internet.
  50. Ela então pega a fatoração de N,
    P1 vezes P2, e a esconde.
  51. Agora, se ela der N a qualquer pessoa,
  52. essa pessoa teria que ter um computador
    rodando durante anos para ter a solução.
  53. Passo 2.
  54. Cock precisa descobrir uma função que
    depende de conhecer a fatoração de N.
  55. Para isso, ele olha o trabalho de 1760
    do matemático suíço Leohnard Euler.
  56. Legendado por [Gabriel Mello Gomes]
    Revisado por [Alberto Oliveira]