Buscador de raízes primitivas módulo n

Buscador de raízes primitivas módulo n | Ferramenta online grátis | Elysia Tools

Guia de uso da ferramenta

Veja quando usar esta ferramenta, o que ela suporta e como os usuários a aplicam.

Fatos principais

Categoria: Math & Numbers
Tipos de entrada: text, select
Tipo de saída: text
Cobertura de exemplos: 4
API pronta: Sim

Visão geral

O Buscador de raízes primitivas módulo n calcula geradores para grupos multiplicativos até 10¹², verificando se o módulo admite raízes cíclicas nas formas 2, 4, p^k ou 2p^k. A ferramenta calcula a função totiente de Euler φ(n), a função de Carmichael λ(n), identifica a menor raiz primitiva com certificado matemático g^(φ/q) ≠ 1 para cada fator primo q de φ(n), lista até 50 geradores e valida candidatos individuais.

Quando usar

Ao projetar ou implementar protocolos criptográficos como Diffie-Hellman e ElGamal que exigem geradores em grupos multiplicativos cíclicos.
Para verificar se um número inteiro g específico é uma raiz primitiva válida módulo n por meio do teste de ordem g^(φ/q) mod n.
Em estudos e exercícios de teoria dos números para calcular φ(n), contar a quantidade total de raízes φ(φ(n)) e listar elementos geradores.

Como funciona

1Verifica se n pertence à família de módulos cíclicos {2, 4, p^k, 2p^k}, fatorando o número e calculando φ(n) e λ(n).
2Fatora φ(n) em fatores primos distintos q e testa candidatos g sequencialmente para garantir que g^(φ/q) ≢ 1 (mod n) para todo q.
3Gera a contagem total de raízes primitivas via φ(φ(n)) e lista os geradores encontrados (até o limite de 50) ou calcula a ordem exata do candidato g fornecido.

Casos de uso

Configuração de parâmetros de chave pública em algoritmos baseados em logaritmo discreto.
Resolução de problemas acadêmicos de álgebra abstrata e aritmética modular envolvendo ordens de elementos.
Auditoria e teste de geradores em implementações de software de criptografia.

Exemplos

1. Listar raízes primitivas para o primo 23

Estudante de Criptografia

Contexto

Precisa identificar geradores e conferir a estrutura do grupo multiplicativo Z_23*.

Problema

Encontrar a menor raiz primitiva e obter uma lista com todos os geradores do grupo.

Como usar

Defina o Módulo n como 23 e selecione o modo 'Listar também raízes primitivas (até 50)'.

n = 23, mode = list

Resultado

Exibe menor raiz g = 5 com certificado (5^11 ≡ 22, 5^2 ≡ 2 mod 23), total de 10 raízes (φ(22)) e lista com todas: 5, 7, 10, 11, 14, 15, 17, 19, 20, 21.

2. Verificar se 2 é raiz primitiva módulo 41

Pesquisador de Segurança

Contexto

Analisando candidatos a gerador pequeno para otimização de exponenciação modular.

Problema

Verificar se g = 2 gera todo o grupo multiplicativo módulo 41 ou se sua ordem é menor que φ(41) = 40.

Como usar

Insira 41 no Módulo n, selecione o modo 'Verificar um candidato g' e preencha g com 2.

Perguntas frequentes

Quais módulos possuem raízes primitivas?

Apenas inteiros na forma n = 2, n = 4, n = p^k ou n = 2p^k (onde p é um primo ímpar e k ≥ 1) possuem raízes primitivas e formam grupos multiplicativos cíclicos.

Como o certificado de uma raiz primitiva é validado?

Para cada divisor primo q de φ(n), calcula-se g^(φ(n)/q) mod n. O candidato g é uma raiz primitiva se, e somente se, nenhum desses resultados for congruente a 1.

Qual é o limite numérico aceito pela ferramenta?

A ferramenta aceita módulos n no intervalo entre 2 e 10¹² (1 000 000 000 000).

Quantas raízes primitivas existem para um dado n?

Se o grupo multiplicativo for cíclico, a quantidade total de raízes primitivas distintas módulo n é exatamente igual a φ(φ(n)).

O que acontece se o candidato g inserido for maior que n?

O valor de g é reduzido automaticamente módulo n antes do teste de coprimalidade e da verificação de ordem.

n = 41, mode = verify, g = 2

Executar esta ferramenta

Exemplos compatíveis com esta ferramenta

Continue com ferramentas e temas relacionados

Veja quando usar esta ferramenta, o que ela suporta e como os usuários a aplicam.

Fatos principais

Visão geral

Quando usar

Como funciona

Casos de uso

Exemplos

1. Listar raízes primitivas para o primo 23

2. Verificar se 2 é raiz primitiva módulo 41

Perguntas frequentes

Exemplos de Processamento de Imagem Web Python

Exemplos de Processamento de Imagem Android Java

Exemplos de Processamento de Imagem Android Kotlin

Exemplos de Processamento de Imagem Web Rust

Verificador de resíduo quadrático (símbolos de Legendre/Jacobi)

Interpretação de Gasometria (AG / ΔAG)

Calculadora de concentração de DNA (absorbância A260)

Calculadora de pureza OD260/230 (contaminação por sais/solventes)