Sulla Ricerca Deterministica di un Elemento di Ordine Elevato Modulo un Composito

Informazioni Fondamentali

• ID Articolo: 2506.07668
• Titolo: On Deterministically Finding an Element of High Order Modulo a Composite
• Autori: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israele)
• Classificazione: cs.DS (Strutture Dati e Algoritmi), math.NT (Teoria dei Numeri)
• Data di Sottomissione: 11 giugno 2025 (arXiv v3)
• Link Articolo: https://arxiv.org/abs/2506.07668

Riassunto

Questo articolo propone un algoritmo deterministico che, dato un numero composito $N$ e un ordine obiettivo $D \geq N^{1/6}$, viene eseguito in tempo $D^{1/2+o(1)}$ e trova un elemento $a \in \mathbb{Z}_N^*$ con ordine moltiplicativo almeno $D$, oppure trova un fattore non banale di $N$. L'algoritmo migliora quello di Hittmeir, che richiedeva l'ipotesi più forte $D \geq N^{2/5}$. Quando $N$ ha fattori di potenza $r$-esima ($r \geq 2$), l'algoritmo fornisce le stesse garanzie assumendo $D \geq N^{1/6r}$.

Contesto di Ricerca e Motivazione

Contesto del Problema

1. La sfida della fattorizzazione intera: La fattorizzazione intera è un problema centrale nella teoria computazionale dei numeri. Attualmente, i migliori algoritmi casuali (come il crivello del campo numerico) hanno complessità subexponenziale, mentre i migliori algoritmi deterministici fino a poco tempo fa erano fortemente esponenziali.
2. Importanza degli algoritmi deterministici: Sebbene teoricamente ogni algoritmo casuale possa essere simulato da un algoritmo deterministico con rallentamento polinomiale, ottenere risultati di derandomizzazione incondizionati rimane significativo nella teoria della complessità e nella progettazione di algoritmi.
3. Ruolo degli elementi di ordine elevato: Il lavoro rivoluzionario di Hittmeir e Harvey ha dimostrato che trovare deterministicamente elementi con grande ordine moltiplicativo è fondamentale per progettare algoritmi di fattorizzazione deterministica efficienti.

Motivazione della Ricerca

1. Miglioramento dell'intervallo di parametri: L'algoritmo di Hittmeir richiede $D \geq N^{2/5}$, una condizione relativamente ristretta che limita l'ambito di applicazione dell'algoritmo.
2. Potenziamento dell'algoritmo di fattorizzazione: Nell'algoritmo di fattorizzazione Harvey-Hittmeir, il passo di ricerca di elementi di ordine elevato viene eseguito in tempo $N^{1/5+o(1)}$, rappresentando uno dei colli di bottiglia dell'algoritmo.
3. Significato teorico: La derandomizzazione è un problema importante della scienza computazionale teorica, e realizzarla negli algoritmi di teoria dei numeri ha profonde implicazioni teoriche.

Contributi Principali

1. Miglioramento dei parametri: Riduzione del requisito dell'ordine obiettivo da $D \geq N^{2/5}$ a $D \geq N^{1/6}$, estendendo significativamente l'ambito di applicabilità dell'algoritmo.
2. Mantenimento del tempo di esecuzione: Mantenimento della complessità di tempo $D^{1/2+o(1)}$ mentre si allentano i requisiti dei parametri.
3. Ottimizzazione per il caso di potenze $r$-esime: Quando $N$ ha fattori di potenza $r$-esima, ulteriore riduzione del requisito a $D \geq N^{1/6r}$.
4. Miglioramento dell'algoritmo di fattorizzazione: Fornitura di nuove subroutine di fattorizzazione che migliorano i metodi di fattorizzazione con informazioni di classi residue note.
5. Strumenti teorici: Dimostrazione di limiti più stretti sul numero di elementi in interi consecutivi che soddisfano specifiche condizioni di congruenza.

Spiegazione Dettagliata del Metodo

Definizione del Compito

Input: Numero composito $N$ e ordine obiettivo $D \geq N^{1/6}$Output: Un elemento $a \in \mathbb{Z}_N^*$ con ordine moltiplicativo almeno $D$, oppure un fattore non banale di $N$Complessità temporale: $D^{1/2+o(1)}$

Architettura dell'Algoritmo

Struttura dell'Algoritmo Principale (Algorithm 4.1)

L'algoritmo adotta una strategia di ricerca iterativa, contenente principalmente i seguenti passaggi:

1. Preprocessing: Utilizzo del metodo di Strassen per controllare i fattori piccoli
2. Ricerca iterativa: Ricerca per $a = 2, 3, 4, \ldots$
3. Calcolo dell'ordine: Utilizzo del metodo Baby-step Giant-step migliorato
4. Accumulo di informazioni: Mantenimento della variabile $M$ che registra il minimo comune multiplo degli ordini degli elementi controllati
5. Fattorizzazione finale: Utilizzo del nuovo algoritmo di fattorizzazione quando $M$ è sufficientemente grande

Miglioramenti Tecnici Principali

1. Miglioramento dei Limiti delle Radici Consecutive (Claim 2.6)

Per interi grandi N, ℓ, se N ha un fattore primo p > 2ℓ,
allora in m = 10√ℓ interi consecutivi {a, a+1, ..., a+m},
esiste necessariamente un elemento b tale che b^ℓ ≢ 1 (mod N)

Questo migliora la complessità di ricerca da $O(M)$ nell'algoritmo di Hittmeir a $O(\sqrt{M})$.

2. Algoritmo di Fattorizzazione per Classe Residua (Theorem 3.2) Dato $N$ e $s \geq N^α$ ($α \leq 1/(4r)$, $\gcd(N,s) = 1$), l'algoritmo può trovare in tempo $N^{1/(4r)-α+o(1)}$ tutti i fattori di potenza $r$-esima che soddisfano $p \equiv 1 \pmod{s}$.

Punti di Innovazione Tecnica

1. Miglioramento della Costruzione Polinomiale

Sulla base dell'algoritmo Harvey-Hittmeir, il polinomio di base è stato migliorato da $f(x) = x + P$ a: $g(x) = x + s' + s'(P - \tilde{P})$ dove $s'$ è l'inverso di $s$ modulo $N$, e $\tilde{P}$ è il resto di $P$ modulo $s$.

2. Riduzione dello Spazio di Ricerca

Utilizzando l'informazione che il fattore primo $p \equiv 1 \pmod{s}$, la dimensione della ricerca delle radici viene ridotta da $H$ a circa $H/s$, riducendo così il numero di intervalli di ricerca di un fattore $s$.

3. Applicazione della Riduzione di Base del Reticolo LLL

Costruzione del sistema polinomiale: