Über die Anzahl regulärer Ganzzahlen modulo $n$ und ihre Bedeutung für die Kryptographie

Grundlegende Informationen

• Paper-ID: 2304.02471
• Titel: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• Autoren: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Deutschland)
• Klassifizierung: math.CO (Kombinatorik), math.GR (Gruppentheorie), math.NT (Zahlentheorie)
• Veröffentlichungsdatum: 9. Oktober 2025 (arXiv-Version)
• Paper-Link: https://arxiv.org/abs/2304.02471v6

Zusammenfassung

Dieser Artikel liefert vier kombinatorische Beweise für die Formel von Morgado über die Anzahl regulärer Ganzzahlen modulo $n$ basierend auf dem Bijektionsprinzip und dem Inklusions-Exklusions-Prinzip. Die Formel entspricht der Sequenz A055653 in der OEIS, wobei eine Ganzzahl $m$ als modulo $n$ regulär bezeichnet wird, wenn und nur wenn die Kongruenzgleichung $m^2x \equiv m \pmod{n}$ in der Ganzzahlring $\mathbb{Z}$ eine Lösung hat. Um die Bedeutung dieser Forschung hervorzuheben, verbinden die Autoren diese Sequenz und die Morgado-Formel mit einer kürzlich vorgeschlagenen Verallgemeinerung des RSA-Kryptosystems mit mehreren Primzahlen und mehreren Potenzen.

Forschungshintergrund und Motivation

Kernproblem

Das Kernproblem dieser Forschung besteht darin, die Anzahl regulärer Ganzzahlen modulo $n$ zu berechnen und ihre Anwendungsbedeutung in der Kryptographie zu untersuchen.

Bedeutung des Problems

1. Theoretische Bedeutung: Das Konzept regulärer Ganzzahlen wurde 1972 von Morgado erstmals eingeführt und ist ein wichtiges kombinatorisches Objekt in der Zahlentheorie. Die Zählformel bezieht sich auf Einheitsteiler und die Eulersche Phi-Funktion sowie andere grundlegende zahlentheoretische Konzepte.
2. Praktische Anwendung: In der von den Autoren vorgeschlagenen RSA-Kryptosystem-Verallgemeinerung bilden reguläre Ganzzahlen den Nachrichtenraum für korrekte Entschlüsselung, daher hängt ihre Anzahl direkt mit der Korrektwahrscheinlichkeit des Kryptosystems zusammen.

Einschränkungen bestehender Methoden

Bisherige Beweise der Morgado-Formel stützten sich hauptsächlich auf die Multiplikativität der $\varrho(n)$-Funktion und entbehrten anschaulicher kombinatorischer Erklärungen. Dieser Artikel bietet durch rein kombinatorische Methoden ein tieferes Verständnis.

Forschungsmotivation

Die Forschungsmotivation der Autoren stammt aus praktischen Anforderungen bei ihrer Verallgemeinerung des RSA-Systems mit mehreren Primzahlen und mehreren Potenzen, wobei die Wahrscheinlichkeit der korrekten Entschlüsselung beliebiger Nachrichten geschätzt werden muss.

Kernbeiträge

1. Vier kombinatorische Beweise: Basierend auf dem Bijektionsprinzip und dem Inklusions-Exklusions-Prinzip werden vier verschiedene kombinatorische Beweise für die Morgado-Formel aus unterschiedlichen Perspektiven bereitgestellt
2. Etablierung eines Kodierungsschemas: Der vierte Beweis liefert eine explizite Kodierung regulärer Ganzzahlen, die möglicherweise für weitere Forschungen zur Sequenz A055653 wertvoll ist
3. Kryptographische Anwendung: Verbindung der Theorie regulärer Ganzzahlen mit der RSA-Kryptosystem-Verallgemeinerung, um die praktische Bedeutung dieses zahlentheoretischen Konzepts zu offenbaren
4. Theoretische Einsichten: Die kombinatorische Methode führt natürlich zur Multiplikativität der $\varrho(n)$-Funktion

Detaillierte Methodologie

Aufgabendefinition

Eingabe: Positive Ganzzahl $n$Ausgabe: Anzahl regulärer Ganzzahlen modulo $n$, bezeichnet als $\varrho(n)$Einschränkung: Eine Ganzzahl $m$ ist modulo $n$ regulär, wenn und nur wenn es ein $x \in \mathbb{Z}$ gibt, sodass $m^2x \equiv m \pmod{n}$

Theoretische Grundlagen

Definition: Eine Ganzzahl $m$ wird als modulo $n$ regulär bezeichnet, wenn die Kongruenzgleichung $m^2x \equiv m \pmod{n}$ eine ganzzahlige Lösung hat.

Morgado-Formel (Satz 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ wobei $d \parallel n$ bedeutet, dass $d$ ein Einheitsteiler von $n$ ist (d.h. $d|n$ und $\gcd(d, n/d) = 1$).

Schlüsseleigenschaften (Proposition 2): Für beliebige $n \in \mathbb{N}$ und $m \in \mathbb{Z}$ sind die folgenden Bedingungen äquivalent:

• (a) $m$ ist modulo $n$ regulär
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

Vier Beweismethoden

Methode 1: Äquivalenzrelations-Beweis

Durch Definition einer Äquivalenzrelation $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$ auf $\mathbb{Z}^{\text{reg}}_n$ wird eine Bijektion zwischen Äquivalenzklassen und $\mathbb{Z}^*_{n/d}$ etabliert.

Methode 2: Reiner Bijektions-Beweis

Konstruktion der Abbildung $f_n: \mathbb{Z}^{\text{reg}}_n \to \{(d, d') | d \parallel n, d' \in \mathbb{Z}^*_d\}$: $f_n(m) := \left(\frac{n}{\gcd(m,n)}, m \bmod \frac{n}{\gcd(m,n)}\right)$

Die Umkehrabbildung ist: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

Methode 3: Beweis durch gekürzte Brüche

Jedes $m \in \mathbb{Z}^{\text{reg}}_n$ wird dem gekürzten Bruch $m/n$ zugeordnet. Es wird bewiesen, dass die Nenner dieser gekürzten Brüche genau alle Einheitsteiler von $n$ sind.

Methode 4: Inklusions-Exklusions-Beweis

Für jeden Primfaktor $p \in P(n)$ wird definiert: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ wobei $m_p$ die Vielfachheit von $p$ in der Primfaktorzerlegung von $m$ bezeichnet. Dann wird das Inklusions-Exklusions-Prinzip angewendet.

Technische Innovationspunkte

1. Kombinatorische Perspektive: Im Gegensatz zu bisherigen multiplikativen Beweisen bietet dieser Artikel anschauliche kombinatorische Erklärungen
2. Bijektive Konstruktion: Der zweite Beweis liefert explizite Kodierungs- und Dekodierungsalgorithmen für reguläre Ganzzahlen
3. Mehrperspektiven-Analyse: Vier Beweise offenbaren die wesentliche Struktur regulärer Ganzzahlen aus verschiedenen Blickwinkeln
4. Kryptographische Verbindung: Erstmalige Verbindung der Theorie regulärer Ganzzahlen mit modernen kryptographischen Anwendungen

Experimentelle Einrichtung

Numerische Verifikation

Der Artikel verifiziert die theoretischen Ergebnisse durch konkrete Beispiele:

Beispiel: Fall $n = 20$

• Einheitsteiler: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• Vorhergesagter Wert: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• Tatsächliche reguläre Ganzzahlen: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• Verifikation: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

Abbildungsbeispiele

Der Artikel zeigt detailliert alle Korrespondenzen der $f_{20}$-Abbildung und verifiziert die Korrektheit der Bijektion.

Experimentelle Ergebnisse

Theoretische Verifikation

Alle vier Beweise etablieren erfolgreich die Korrektheit der Morgado-Formel, wobei jede Methode einzigartige kombinatorische Einsichten bietet.

Kryptographische Anwendungsergebnisse

In der RSA-Verallgemeinerung mit mehreren Primzahlen und mehreren Potenzen:

• Korrekte Entschlüsselungswahrscheinlichkeit: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• Untergrenzen-Schätzung: Für $n = p_1^{e_1} \cdots p_r^{e_r}$ (wobei $p_i$ $k$-Bit-Primzahlen sind), gilt $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• Praktische Bedeutung: Wenn $k = 1024$, können fast alle Nachrichten korrekt entschlüsselt werden

Verwandte Arbeiten

Historische Entwicklung

1. Morgado (1972): Erstmalige Definition des Konzepts regulärer Ganzzahlen und Angabe der Zählformel
2. Alkam & Osba (2008): Weitere Untersuchung der Eigenschaften regulärer Ganzzahlen
3. Apostol & Petrescu (2013): Untersuchung der Extremwerte verwandter Funktionen
4. Tóth (2008): Asymptotische Ergebnisse und Analyse verwandter Funktionen

Beitrag dieses Artikels

Im Vergleich zu bestehenden Arbeiten bietet dieser Artikel erstmals rein kombinatorische Beweismethoden und etabliert wichtige Verbindungen zur Kryptographie.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Die Morgado-Formel hat reichhaltige kombinatorische Interpretationen; jeder Beweis offenbart unterschiedliche Strukturebenen
2. Reguläre Ganzzahlen spielen eine Schlüsselrolle in RSA-Kryptosystem-Verallgemeinerungen
3. Für praktische Parameterwahlen liegt die Korrektwahrscheinlichkeit der Entschlüsselung nahe bei 1

Einschränkungen

1. Kryptographische Anwendungen sind auf spezifische RSA-Verallgemeinerungen beschränkt
2. Asymptotische Analysen bedürfen weiterer Forschung
3. Analyse der Rechenkomplexität ist nicht ausreichend tiefgehend

Zukünftige Richtungen

1. Entwicklung präziserer Wahrscheinlichkeitsgrenzen
2. Untersuchung asymptotischer Eigenschaften der Sequenz A055653
3. Erkundung weiterer kryptographischer Anwendungen

Tiefgreifende Bewertung

Stärken

1. Theoretische Innovation: Die vier kombinatorischen Beweise haben jeweils ihre eigenen Merkmale und bereichern das Verständnis regulärer Ganzzahlen
2. Methodische Strenge: Der Beweisprozess ist rigoros und die Logik ist klar
3. Anwendungswert: Die Verbindung zur Kryptographie erhöht die praktische Bedeutung der theoretischen Forschung
4. Klare Darstellung: Die Papierstruktur ist angemessen und die Beispiele sind reichhaltig

Mängel

1. Anwendungsbeschränkungen: Kryptographische Anwendungen sind auf die von den Autoren selbst vorgeschlagene RSA-Verallgemeinerung beschränkt
2. Rechenanalyse: Mangelnde tiefgehende Analyse der Algorithmen-Komplexität
3. Experimentelle Verifikation: Nur kleinmaßstäbliche numerische Verifikation, fehlende großmaßstäbliche Rechenexperimente

Einflussreichtum

1. Akademischer Wert: Bietet neue Forschungsansätze für zahlentheoretische Kombinatorik
2. Praktisches Potenzial: Potenzielle Anwendungswerte in der Kryptographie
3. Reproduzierbarkeit: Theoretische Beweise sind vollständig und Ergebnisse sind leicht zu verifizieren

Anwendungsszenarien

1. Theoretische Forschung in Zahlentheorie und Kombinatorik
2. Kryptographische Szenarien mit modularen Operationen
3. Anwendungen, die die Berechnung der Größe spezieller Ganzzahlmengen erfordern

Literaturverzeichnis

Der Artikel zitiert 8 relevante Arbeiten, die die Hauptentwicklung der Theorie regulärer Ganzzahlen und verwandte mathematische Grundlagen abdecken und den Lesern vollständiges Hintergrundwissen bieten.

Gesamtbewertung: Dies ist ein hochqualitatives mathematisches Papier, das durch mehrere kombinatorische Methoden das Verständnis klassischer zahlentheoretischer Probleme vertieft und erfolgreich Verbindungen zur modernen Kryptographie etabliert. Die theoretischen Beiträge des Papiers sind solide und die Anwendungsaussichten sind breit gefächert – es handelt sich um wertvolle Arbeiten im Bereich der zahlentheoretischen Kombinatorik.