Calculadora de raiz quadrada modular de Tonelli-Shanks

Insira n e um primo p para encontrar a raiz quadrada modular.

Como usar

  1. Insira os valores necessários nos campos.
  2. Clique em “Calcular” para ver o resultado.
  3. Copie ou compartilhe o resultado com o botão “Compartilhar”.

Sobre esta calculadora

O algoritmo de Tonelli-Shanks encontra uma raiz quadrada modular — um valor r tal que r² ≡ n (mod p) — para um dado número n e um módulo primo ímpar p, uma das operações fundamentais da teoria computacional dos números. Antes de executar o algoritmo principal, ele verifica o critério de Euler: n é um resíduo quadrático módulo p (ou seja, existe uma raiz quadrada) exatamente quando n^((p−1)/2) ≡ 1 (mod p). Quando p ≡ 3 (mod 4), a raiz quadrada tem um atalho direto em forma fechada, mas o Tonelli-Shanks é necessário para o caso geral mais difícil em que p ≡ 1 (mod 4), usando elevações ao quadrado repetidas contra um não resíduo quadrático para extrair fatores de 2 de p−1.

Essa operação sustenta a criptografia prática — mais notavelmente a descompressão de um ponto de uma curva elíptica a partir de sua coordenada x nos formatos comprimidos de chave pública usados pelo ECDSA e pelo Bitcoin, em que a coordenada y precisa ser recuperada como raiz quadrada modular de um valor derivado da equação da curva.

Isto foi útil?

Pode escolher até 3 reações.

Comentários

  • Seja o primeiro a comentar.

Calculadoras populares

Todas as calculadoras