Introdução

Você já viu a lição sobre Criptografia Moderna? Pelo menos no último checkpoint essa foi a questão mais perguntada pelos usuários:

Na aula vimos como a fatoração primária desempenhou um papel fundamental na construção de of trancas matemáticas. Uma tranca matemática (or função unidirecional) requer um procedimento que é fácil de realizar e difícil de reverter.

Por exemplo, se eu pegar aleatoriamente dois números primos tais como:P1 = 709 eP2 = 733

e multiplicá-los para obter: N = P1 * P2

N = 709 * 733 = 519697     (isso é fácil de computar)

Eu acabei com duas coisas: um número grande (519697) e a fatoração para esse grande número (709 * 733)

Agora, imagine que eu esconda a fatoração primária e forneça apenas o seguinte:

519697 = ? * ?     (isso é difícil de computar)

Se eu te pedir para encontrar a fatoração primária, por onde você começaria? Não se preocupe, todos teriam dificuldades com este problema! Para encontrar a solução, é necessário fazer um monte de testes de tentativa e erro. A multiplicação é rápida (fácil) de calcular, enquanto a fatoração primária é lenta (difícil). Este simples fato forma a base do esquema de criptografia RSA.

👁️ Observe este gráfico animado para ver a diferença.

Entretanto, antes de seguir adiante, precisamos ampliar o primeiro passo e fazer uma an pergunta importante. Quando dizemos "pegar aleatoriamente dois números primos grandes", como fazemos isso rapidamente? É um problema fácil?

Se você pensar sobre isso por um tempo, uma hora você vai concordar que essa etapa requer, no mínimo, a capacidade de verificar se um número gerado aleatoriamente (como 99194853094755497) é primo ou composto . Você tem um botão na sua calculadora para dizer isto?

Eu não vejo um….Porque?

Para descobrir, 's comece com um desafio...