Solucionador de logaritmo discreto

O problema do logaritmo discreto pede um inteiro x tal que uma dada base g elevada a x seja congruente a um alvo h módulo um primo p. Ele sustenta a troca de chaves Diffie–Hellman, a cifra ElGamal e muitos exercícios de livro-texto em criptografia algébrica. Esta capacidade implementa o algoritmo clássico passo de bebê e passo de gigante: uma busca determinística de tempo raiz quadrada que recupera o menor expoente não negativo ou prova que h não é uma potência de g no grupo multiplicativo módulo p.

O que o logaritmo discreto pede

Dados inteiros g, h e um primo p, o logaritmo discreto de h na base g módulo p é qualquer inteiro x que satisfaça g elevado a x congruente a h módulo p. Quando existe solução, o menor representante não negativo na faixa de zero a p menos dois é único uma vez que você fixe essa faixa, e é o valor que esta ferramenta retorna.

Diferente dos logaritmos reais comuns, não há fórmula elementar em forma fechada que funcione para primos arbitrários; a dificuldade de recuperar x para primos grandes cuidadosamente escolhidos é exatamente por que a criptografia de log discreto é útil. No ensino e em experimentos de parâmetros pequenos, porém, você ainda precisa de um solucionador correto e inspecionável: um que valide a hipótese de primalidade, reduza as entradas ao sistema canônico de resíduos, busque sistematicamente e imprima um expoente verificável ou afirme claramente que não existe solução.

Como o passo de bebê e passo de gigante encontra x

O passo de bebê e passo de gigante reescreve o expoente desconhecido como x igual a i vezes m mais j, onde m é aproximadamente a raiz quadrada da ordem do grupo p menos um, e tanto i quanto j vão de zero até m. O algoritmo primeiro armazena cada valor de bebê g elevado a j módulo p num mapa de hash indexado pelo resíduo, depois caminha em passos de gigante multiplicando repetidamente o alvo pelo inverso modular de g elevado a m, procurando cada resíduo intermediário no mapa.

Um acerto fornece tanto i quanto j e, portanto, x. Bases e alvos fora de zero a p menos um são reduzidos módulo p, e a resposta ecoa g, h e p reduzidos para que os chamadores auditem a instância exata resolvida.

Entradas, limites, preço e quando não há solução

Os campos obrigatórios são g (base), h (resíduo alvo) e p (módulo primo). Strings de dígitos são aceitas para inteiros grandes dentro do limite do módulo. Se h não está no subgrupo cíclico gerado por g módulo p — por exemplo, quando g gera apenas um subgrupo próprio e h está fora dele — o solucionador retorna solved false com um expoente nulo e uma mensagem explicativa, em vez de fabricar um x errado.

Esse desfecho é uma computação bem-sucedida, não um erro de cliente, porque a entrada estava bem formada e a resposta matemática é que nenhum logaritmo existe. Erros de cliente cobrem campos ausentes, não inteiros, módulos fora da faixa permitida e p composto. A ferramenta no navegador roda a biblioteca idêntica de graça, sem conta.

Use o resultado para conferir exercícios, gerar testes de resposta conhecida para bibliotecas de criptografia, ou explorar a pertinência a subgrupos antes de escalar parâmetros num projeto de protocolo real.