Sur la Détermination Déterministe d'un Élément d'Ordre Élevé Modulo un Nombre Composé

Informations Fondamentales

• Identifiant de l'article: 2506.07668
• Titre: On Deterministically Finding an Element of High Order Modulo a Composite
• Auteurs: Ziv Oznovich, Ben Lee Volk (École d'Informatique Efi Arazi, Université Reichman, Israël)
• Classification: cs.DS (Structures de Données et Algorithmes), math.NT (Théorie des Nombres)
• Date de soumission: 11 juin 2025 (arXiv v3)
• Lien de l'article: https://arxiv.org/abs/2506.07668

Résumé

Cet article propose un algorithme déterministe qui, étant donné un nombre composé $N$ et un ordre cible $D \geq N^{1/6}$, s'exécute en temps $D^{1/2+o(1)}$ et trouve soit un élément $a \in \mathbb{Z}_N^*$ dont l'ordre multiplicatif est au moins $D$, soit un facteur non trivial de $N$. Cet algorithme améliore celui de Hittmeir, qui nécessitait l'hypothèse plus forte $D \geq N^{2/5}$. Lorsque $N$ possède des facteurs de puissance $r$ (avec $r \geq 2$), l'algorithme fournit les mêmes garanties sous l'hypothèse $D \geq N^{1/6r}$.

Contexte et Motivation de la Recherche

Contexte du Problème

1. Le défi de la factorisation d'entiers: La factorisation d'entiers est un problème fondamental en théorie computationnelle des nombres. Les meilleurs algorithmes aléatoires connus (comme le crible du corps de nombres) possèdent une complexité sous-exponentielle, tandis que les meilleurs algorithmes déterministes étaient jusqu'à récemment fortement exponentiels.
2. L'importance des algorithmes déterministes: Bien que théoriquement chaque algorithme aléatoire puisse être simulé de manière déterministe avec un ralentissement polynomial, l'obtention de résultats de dérandomisation inconditionnels reste d'une importance capitale en théorie de la complexité et en conception d'algorithmes.
3. Le rôle des éléments d'ordre élevé: Les travaux révolutionnaires de Hittmeir et Harvey ont montré que la détermination déterministe d'éléments possédant un ordre multiplicatif important est essentielle pour concevoir des algorithmes de factorisation déterministes efficaces.

Motivation de la Recherche

1. Amélioration de la plage de paramètres: L'algorithme de Hittmeir exige $D \geq N^{2/5}$, une condition relativement stricte qui limite la portée d'application de l'algorithme.
2. Amélioration de l'algorithme de factorisation: Dans l'algorithme de factorisation Harvey-Hittmeir, l'étape de recherche d'éléments d'ordre élevé s'exécute en temps $N^{1/5+o(1)}$, ce qui en fait l'un des goulots d'étranglement de l'algorithme.
3. Signification théorique: La dérandomisation est un problème important en informatique théorique, et sa réalisation dans les algorithmes de théorie des nombres revêt une profonde importance théorique.

Contributions Principales

1. Amélioration des paramètres: Réduction de l'exigence d'ordre cible de $D \geq N^{2/5}$ à $D \geq N^{1/6}$, élargissant considérablement la portée d'application de l'algorithme.
2. Maintien de la complexité temporelle: Tout en assouplissant les exigences de paramètres, la complexité temporelle $D^{1/2+o(1)}$ est conservée.
3. Optimisation pour les facteurs de puissance $r$: Lorsque $N$ possède des facteurs de puissance $r$, l'exigence est encore réduite à $D \geq N^{1/6r}$.
4. Amélioration de l'algorithme de factorisation: Fourniture de nouveaux sous-programmes de factorisation, améliorant les méthodes de factorisation connues avec information sur les classes de résidus.
5. Outils théoriques: Preuve de bornes plus serrées sur le nombre d'éléments dans les entiers consécutifs satisfaisant des conditions de congruence spécifiques.

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée: Un nombre composé $N$ et un ordre cible $D \geq N^{1/6}$Sortie: Soit un élément $a \in \mathbb{Z}_N^*$ dont l'ordre multiplicatif est au moins $D$, soit un facteur non trivial de $N$Complexité temporelle: $D^{1/2+o(1)}$

Architecture de l'Algorithme

Structure Principale de l'Algorithme (Algorithme 4.1)

L'algorithme adopte une stratégie de recherche itérative, comprenant principalement les étapes suivantes:

1. Prétraitement: Vérification des petits facteurs à l'aide de la méthode de Strassen
2. Recherche itérative: Recherche pour $a = 2, 3, 4, \ldots$
3. Calcul de l'ordre: Utilisation d'une méthode Baby-step Giant-step améliorée
4. Accumulation d'informations: Maintien d'une variable $M$ enregistrant le plus petit commun multiple des ordres des éléments vérifiés
5. Factorisation finale: Utilisation d'un nouvel algorithme de factorisation lorsque $M$ est suffisamment grand

Améliorations Techniques Principales

1. Amélioration de la Borne des Racines Consécutives (Claim 2.6)

Pour les grands entiers N, ℓ, si N possède un facteur premier p > 2ℓ,
alors dans m = 10√ℓ entiers consécutifs {a, a+1, ..., a+m},
il existe nécessairement un élément b tel que b^ℓ ≢ 1 (mod N)

Ceci améliore la complexité de recherche de $O(M)$ dans l'algorithme de Hittmeir à $O(\sqrt{M})$.

2. Algorithme de Factorisation par Classe de Résidus (Théorème 3.2) Étant donné $N$ et $s \geq N^α$ (avec $α \leq 1/(4r)$, $\gcd(N,s) = 1$), l'algorithme peut trouver en temps $N^{1/(4r)-α+o(1)}$ tous les facteurs de puissance $r$ satisfaisant $p \equiv 1 \pmod{s}$.

Points d'Innovation Technique

1. Amélioration de la Construction Polynomiale

Sur la base de l'algorithme Harvey-Hittmeir, le polynôme de base est amélioré de $f(x) = x + P$ à: $g(x) = x + s' + s'(P - \tilde{P})$ où $s'$ est l'inverse de $s$ modulo $N$, et $\tilde{P}$ est le reste de $P$ modulo $s$.

2. Réduction de l'Espace de Recherche

En utilisant l'information que le facteur premier $p \equiv 1 \pmod{s}$, la taille de la racine de recherche est réduite de $H$ à environ $H/s$, réduisant ainsi le nombre d'intervalles de recherche d'un facteur $s$.

3. Application de la Réduction de Base LLL

Construction du système polynomial: