Über die deterministische Findung eines Elements hoher Ordnung modulo einer zusammengesetzten Zahl

Grundlegende Informationen

• Paper-ID: 2506.07668
• Titel: On Deterministically Finding an Element of High Order Modulo a Composite
• Autoren: Ziv Oznovich, Ben Lee Volk (Efi Arazi School of Computer Science, Reichman University, Israel)
• Klassifizierung: cs.DS (Datenstrukturen und Algorithmen), math.NT (Zahlentheorie)
• Einreichungszeit: 11. Juni 2025 (arXiv v3)
• Paper-Link: https://arxiv.org/abs/2506.07668

Zusammenfassung

In diesem Artikel wird ein deterministischer Algorithmus vorgestellt, der für eine zusammengesetzte Zahl $N$ und eine Zielordnung $D \geq N^{1/6}$ in der Zeit $D^{1/2+o(1)}$ läuft und entweder ein Element $a \in \mathbb{Z}_N^*$ mit multiplikativer Ordnung mindestens $D$ findet oder einen nichttrivialen Teiler von $N$ entdeckt. Der Algorithmus verbessert den Algorithmus von Hittmeir, der die stärkere Annahme $D \geq N^{2/5}$ erfordert. Wenn $N$ einen $r$-ten Potenzteiler ($r \geq 2$) besitzt, bietet der Algorithmus unter der Annahme $D \geq N^{1/6r}$ die gleichen Garantien.

Forschungshintergrund und Motivation

Problemhintergrund

1. Die Herausforderung der Ganzzahlfaktorisierung: Die Ganzzahlfaktorisierung ist ein Kernproblem der rechnergestützten Zahlentheorie. Die besten bekannten randomisierten Algorithmen (wie das Zahlenkörpersieb) haben subexponentielle Komplexität, während die besten deterministischen Algorithmen bis vor kurzem stark exponentiell waren.
2. Bedeutung deterministischer Algorithmen: Obwohl theoretisch jeder randomisierte Algorithmus durch einen deterministischen Algorithmus mit polynomialer Verlangsamung simuliert werden kann, bleibt die Erreichung bedingungsloser Derandomisierungsergebnisse in der Komplexitätstheorie und im Algorithmendesign von großer Bedeutung.
3. Rolle von Elementen hoher Ordnung: Die bahnbrechende Arbeit von Hittmeir und Harvey zeigt, dass die deterministische Findung von Elementen mit großer multiplikativer Ordnung der Schlüssel zum Entwurf effizienter deterministischer Faktorisierungsalgorithmen ist.

Forschungsmotivation

1. Verbesserung des Parameterbereichs: Der Algorithmus von Hittmeir erfordert $D \geq N^{2/5}$, eine relativ strenge Bedingung, die den Anwendungsbereich des Algorithmus einschränkt.
2. Verbesserung des Faktorisierungsalgorithmus: Im Harvey-Hittmeir-Faktorisierungsalgorithmus ist der Schritt zur Findung von Elementen hoher Ordnung mit einer Laufzeit von $N^{1/5+o(1)}$ ein Engpass.
3. Theoretische Bedeutung: Derandomisierung ist ein wichtiges Problem der theoretischen Informatik, und die Realisierung von Derandomisierung in zahlentheoretischen Algorithmen hat tiefgreifende theoretische Bedeutung.

Kernbeiträge

1. Parameterverbesserung: Reduzierung der Anforderung an die Zielordnung von $D \geq N^{2/5}$ auf $D \geq N^{1/6}$, was den Anwendungsbereich des Algorithmus erheblich erweitert.
2. Beibehaltung der Laufzeit: Bei Lockerung der Parameteranforderungen wird die Laufzeitkomplexität von $D^{1/2+o(1)}$ beibehalten.
3. Optimierung für $r$-te Potenzfälle: Wenn $N$ einen $r$-ten Potenzteiler besitzt, wird die Anforderung weiter auf $D \geq N^{1/6r}$ reduziert.
4. Verbesserung des Faktorisierungsalgorithmus: Bereitstellung neuer Faktorisierungsunterprogramme, die die Faktorisierungsmethoden bei bekannten Restklasseninformationen verbessern.
5. Theoretische Werkzeuge: Beweis von engeren Grenzen für die Anzahl der Elemente in aufeinanderfolgenden Ganzzahlen, die spezifische Kongruenzbedingungen erfüllen.

Methodische Details

Aufgabendefinition

Eingabe: Zusammengesetzte Zahl $N$ und Zielordnung $D \geq N^{1/6}$Ausgabe: Entweder ein Element $a \in \mathbb{Z}_N^*$ mit multiplikativer Ordnung mindestens $D$ oder ein nichttrivialer Teiler von $N$Zeitkomplexität: $D^{1/2+o(1)}$

Algorithmusarchitektur

Hauptalgorithmusstruktur (Algorithm 4.1)

Der Algorithmus verwendet eine iterative Suchstrategie mit den folgenden Hauptschritten:

1. Vorverarbeitung: Überprüfung kleiner Teiler mit der Strassen-Methode
2. Iterative Suche: Suche über $a = 2, 3, 4, \ldots$
3. Ordnungsberechnung: Verwendung der verbesserten Baby-step Giant-step-Methode
4. Informationsakkumulation: Verwaltung der Variablen $M$ zur Verfolgung des kleinsten gemeinsamen Vielfachen der überprüften Ordnungen
5. Endgültige Faktorisierung: Verwendung eines neuen Faktorisierungsalgorithmus, wenn $M$ ausreichend groß ist

Kernverbesserungen der Technik

1. Verbesserte Grenzen für aufeinanderfolgende Wurzeln (Claim 2.6)

Für große Ganzzahlen N, ℓ, wenn N einen Primfaktor p > 2ℓ hat,
dann existiert in m = 10√ℓ aufeinanderfolgenden Ganzzahlen {a, a+1, ..., a+m}
ein Element b, so dass b^ℓ ≢ 1 (mod N)

Dies verbessert die Suchkomplexität von $O(M)$ im Hittmeir-Algorithmus auf $O(\sqrt{M})$.

2. Faktorisierungsalgorithmus für Restklassen (Theorem 3.2) Gegeben $N$ und $s \geq N^α$ ($α \leq 1/(4r)$, $\gcd(N,s) = 1$), kann der Algorithmus in der Zeit $N^{1/(4r)-α+o(1)}$ alle $r$-ten Potenzteiler finden, die $p \equiv 1 \pmod{s}$ erfüllen.

Technische Innovationen

1. Verbesserung der Polynomkonstruktion

Basierend auf dem Harvey-Hittmeir-Algorithmus wird das Basispolynom von $f(x) = x + P$ verbessert zu: $g(x) = x + s' + s'(P - \tilde{P})$ wobei $s'$ das Inverse von $s$ modulo $N$ ist und $\tilde{P}$ der Rest von $P$ modulo $s$ ist.

2. Reduktion des Suchraums

Durch Nutzung der Information, dass der Primfaktor $p \equiv 1 \pmod{s}$ erfüllt, wird die Größe der gesuchten Wurzeln von $H$ auf etwa $H/s$ reduziert, wodurch die Anzahl der Suchintervalle um den Faktor $s$ verringert wird.

3. Anwendung der LLL-Gitterbasisreduktion

Konstruktion des Polynomialsystems: