Recherche de racines primitives modulo n

Recherche de racines primitives modulo n | Outil en ligne gratuit | Elysia Tools

Guide d'utilisation de l'outil

Découvrez quand utiliser cet outil, ce qu'il prend en charge et comment les utilisateurs l'appliquent.

Points clés

Catégorie: Math & Numbers
Types d’entrée: text, select
Type de sortie: text
Exemples associés: 4
API disponible: Oui

Aperçu

Cet outil calcule et analyse les racines primitives modulo n jusqu'à 10¹². Il vérifie si le groupe multiplicatif (ℤ/nℤ)× est cyclique, détermine la plus petite racine primitive avec son certificat arithmétique, dénombre les générateurs via l'indicatrice d'Euler φ(φ(n)), en dresse la liste jusqu'à 50 éléments ou vérifie l'ordre d'un candidat spécifique.

Quand l’utiliser

Lorsque vous devez trouver un générateur d'un groupe multiplicatif modulo n pour des applications de cryptographie ou d'algèbre modulaire.
Lorsque vous souhaitez vérifier si un entier g spécifique engendre l'ensemble du groupe (ℤ/nℤ)× en testant la condition g^(φ/q) ≢ 1 (mod n).
Lorsque vous étudiez les propriétés arithmétiques d'un module pour vérifier s'il admet des racines primitives (formes 2, 4, p^k ou 2p^k).

Fonctionnement

1L'outil analyse la décomposition en facteurs premiers du module n pour confirmer qu'il appartient aux formes cycliques admissibles {2, 4, p^k, 2p^k}.
2Il calcule l'indicatrice d'Euler φ(n) et factorise cet ordre pour identifier tous ses diviseurs premiers q.
3Pour chaque candidat g, il évalue les exponentiations modulaires g^(φ(n)/q) mod n pour s'assurer qu'aucune n'est congrue à 1.
4Selon le mode choisi, il affiche la plus petite racine avec ses étapes de certification, liste jusqu'à 50 racines primitives ou détaille les tests d'échec/succès pour un candidat donné.

Cas d’usage

Configuration de paramètres pour des protocoles cryptographiques basés sur le problème du logarithme discret (Diffie-Hellman, ElGamal).
Résolution d'exercices universitaires de théorie des nombres portant sur les générateurs de groupes cycliques et la fonction φ d'Euler.
Contrôle rapide de candidats générateurs dans le cadre d'implémentations d'algorithmes de transformée de Fourier rapide (NTT) modulo un nombre premier.

Exemples

1. Recherche et énumération des racines primitives modulo 23

Étudiant en mathématiques

Contexte

L'étudiant travaille sur les générateurs d'un corps fini premier ℤ/23ℤ.

Problème

Identifier la plus petite racine primitive et lister l'ensemble des générateurs du groupe multiplicatif de taille 22.

Utilisation

Saisir 23 dans le champ Module n et sélectionner le mode « Lister aussi les racines primitives (jusqu'à 50) ».

n = 23, mode = list

Résultat

L'outil certifie que 5 est la plus petite racine primitive et liste les 10 racines : 5, 7, 10, 11, 14, 15, 17, 19, 20, 21.

2. Vérification d'un candidat générateur modulo 41

Développeur en cryptographie

Contexte

Le développeur doit valider si g = 2 est une racine primitive modulo 41 pour un échange de clés.

Problème

Vérifier si 2 engendre l'ensemble du groupe d'ordre φ(41) = 40 ou s'il appartient à un sous-groupe strict.

Utilisation

Saisir n = 41, choisir le mode « Vérifier un candidat g » et renseigner g = 2.

FAQ

Quels modules n admettent des racines primitives ?

Seuls les entiers sous les formes n = 2, 4, p^k ou 2p^k (où p est un nombre premier impair et k ≥ 1) possèdent un groupe multiplicatif cyclique.

Combien de racines primitives modulo n existent-il ?

Si le groupe est cyclique, il existe exactement φ(φ(n)) racines primitives distinctes modulo n.

Comment le certificat de primalité de la racine est-il établi ?

Un entier g est certifié racine primitive si pgcd(g, n) = 1 et si g^(φ(n)/q) ≢ 1 (mod n) pour chaque diviseur premier q de φ(n).

Quelle est la limite maximale pour le module n ?

L'outil accepte des valeurs entières de n comprises entre 2 et 10¹².

Que se passe-t-il si un candidat testé n'est pas premier avec n ?

Si pgcd(g, n) > 1, le candidat g n'est pas inversible dans (ℤ/nℤ)× et ne peut pas être une racine primitive.

n = 41, mode = verify, g = 2

Exécuter cet outil

Exemples adaptés à cet outil

Continuer avec des outils et dossiers associés

Découvrez quand utiliser cet outil, ce qu'il prend en charge et comment les utilisateurs l'appliquent.

Points clés

Aperçu

Quand l’utiliser

Fonctionnement

Cas d’usage

Exemples

1. Recherche et énumération des racines primitives modulo 23

2. Vérification d'un candidat générateur modulo 41

FAQ

Exemples de Traitement d'Images Web Python

Exemples de Traitement d'Images Android Java

Exemples de Traitement d'Images Android Kotlin

Exemples de Traitement d'Images Web Rust

Vérificateur de résidu quadratique (symboles de Legendre/Jacobi)

Interprétation des Gaz du Sang (AG / ΔAG)

Calculateur de concentration d'ADN (absorbance A260)

Calculateur de pureté OD260/230 (contamination sels/solvants)