On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography

Basic Information

• Paper ID: 2304.02471
• Title: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• Authors: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Germany)
• Classification: math.CO (Combinatorics), math.GR (Group Theory), math.NT (Number Theory)
• Publication Date: October 9, 2025 (arXiv version)
• Paper Link: https://arxiv.org/abs/2304.02471v6

Abstract

This paper provides four combinatorial proofs of Morgado's formula for the number of regular integers modulo $n$ based on bijective principles and the inclusion-exclusion principle. The formula corresponds to sequence A055653 in OEIS, where an integer $m$ is called regular modulo $n$ if and only if the congruence equation $m^2x \equiv m \pmod{n}$ has a solution in the integer ring $\mathbb{Z}$. To emphasize the significance of this research, the authors connect this sequence and Morgado's formula to a recently proposed multi-prime multi-power generalization of the RSA cryptosystem.

Research Background and Motivation

Core Problem

This research addresses the fundamental problem of computing the number of regular integers modulo $n$ and exploring its significance in cryptographic applications.

Problem Significance

1. Theoretical Significance: The concept of regular integers was first introduced by Morgado in 1972 and represents an important combinatorial object in number theory. Its counting formula involves unit divisors and Euler's totient function, which are fundamental concepts in number theory.
2. Practical Applications: In the authors' proposed generalization of the RSA cryptosystem, regular integers constitute the message space for correct decryption, so their count directly relates to the correctness probability of the cryptographic system.

Limitations of Existing Methods

Previous proofs of Morgado's formula primarily relied on the multiplicative property of the $\varrho(n)$ function, lacking intuitive combinatorial explanations. This paper provides deeper understanding through purely combinatorial methods.

Research Motivation

The authors' research motivation stems from practical needs encountered in their multi-prime multi-power RSA generalization, requiring estimation of the correct decryption probability for arbitrary messages.

Core Contributions

1. Four Combinatorial Proofs: Based on bijective principles and the inclusion-exclusion principle, four different combinatorial proofs of Morgado's formula are provided from different perspectives.
2. Explicit Encoding Scheme: The fourth proof provides an explicit encoding of regular integers, which may be valuable for further research on sequence A055653.
3. Cryptographic Applications: Connects the theory of regular integers with RSA cryptosystem generalizations, revealing the practical significance of this number-theoretic concept.
4. Theoretical Insights: The combinatorial methods naturally lead to the multiplicative property of the $\varrho(n)$ function.

Detailed Methods

Task Definition

Input: Positive integer $n$Output: Number of regular integers modulo $n$, denoted $\varrho(n)$Constraint: Integer $m$ is regular modulo $n$ if and only if there exists $x \in \mathbb{Z}$ such that $m^2x \equiv m \pmod{n}$

Core Theoretical Foundation

Definition: An integer $m$ is called regular modulo $n$ if the congruence equation $m^2x \equiv m \pmod{n}$ has an integer solution.

Morgado's Formula (Theorem 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ where $d \parallel n$ denotes that $d$ is a unitary divisor of $n$ (i.e., $d|n$ and $\gcd(d, n/d) = 1$).

Key Property (Proposition 2): For any $n \in \mathbb{N}$ and $m \in \mathbb{Z}$, the following conditions are equivalent:

• (a) $m$ is regular modulo $n$
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

Four Proof Methods

Method 1: Equivalence Relation Proof

By defining an equivalence relation $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$ on $\mathbb{Z}^{\text{reg}}_n$, a bijection is established between equivalence classes and $\mathbb{Z}^*_{n/d}$.

Method 2: Pure Bijection Proof

Construct the mapping $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)$

The inverse mapping is: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

Method 3: Reduced Fraction Proof

Each $m \in \mathbb{Z}^{\text{reg}}_n$ is mapped to a reduced fraction $m/n$, proving that the denominators of these reduced fractions are precisely all unitary divisors of $n$.

Method 4: Inclusion-Exclusion Principle Proof

Let $P(n)$ denote the set of prime factors of $n$. For each prime $p \in P(n)$, define: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ where $m_p$ denotes the exponent of $p$ in the prime factorization of $m$. Then apply the inclusion-exclusion principle.

Technical Innovations

1. Combinatorial Perspective: Unlike previous multiplicative-based proofs, this paper provides intuitive combinatorial explanations.
2. Bijection Construction: The second proof provides explicit encoding and decoding algorithms for regular integers.
3. Multi-Angle Analysis: Four proofs reveal the essential structure of regular integers from different perspectives.
4. Cryptographic Connection: First connects the theory of regular integers with modern cryptographic applications.

Experimental Setup

Numerical Verification

The paper verifies theoretical results through concrete examples:

Example: Case of $n = 20$

• Unitary divisors: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• Predicted value: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• Actual regular integers: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• Verification: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

Mapping Examples

The paper provides detailed correspondence relationships for the $f_{20}$ mapping, verifying the correctness of the bijection.

Experimental Results

Theoretical Verification

All four proofs successfully establish the correctness of Morgado's formula, with each method providing unique combinatorial insights.

Cryptographic Application Results

In the multi-prime multi-power RSA generalization:

• Correct decryption probability: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• Lower bound estimate: For $n = p_1^{e_1} \cdots p_r^{e_r}$ (where $p_i$ are $k$-bit primes), we have $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• Practical significance: When $k = 1024$, almost all messages can be correctly decrypted

Related Work

Historical Development

1. Morgado (1972): First defined the concept of regular integers and provided a counting formula
2. Alkam & Osba (2008): Further investigated properties of regular integers
3. Apostol & Petrescu (2013): Studied extremal properties of related functions
4. Tóth (2008): Provided asymptotic results and analysis of related functions

Contributions of This Paper

Compared to existing work, this paper provides purely combinatorial proof methods for the first time and establishes important connections with cryptography.

Conclusions and Discussion

Main Conclusions

1. Morgado's formula admits rich combinatorial interpretations, with each proof revealing different structural aspects
2. Regular integers play a key role in RSA cryptosystem generalizations
3. For practical parameter choices, the correct decryption probability approaches 1

Limitations

1. Cryptographic applications are limited to specific RSA generalizations
2. Asymptotic analysis requires further investigation
3. Computational complexity analysis is insufficient

Future Directions

1. Develop more precise probability bounds
2. Investigate asymptotic properties of sequence A055653
3. Explore other cryptographic applications

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Four combinatorial proofs are each distinctive, enriching understanding of regular integers
2. Rigorous Methodology: Proofs are rigorous with clear logic
3. Applied Value: Connection with cryptography enhances practical significance of theoretical research
4. Clear Exposition: Well-structured paper with abundant examples

Weaknesses

1. Limited Applications: Cryptographic applications are restricted to the authors' own RSA generalization
2. Computational Analysis: Lacks in-depth analysis of algorithmic complexity
3. Experimental Verification: Only small-scale numerical verification; lacks large-scale computational experiments

Impact

1. Academic Value: Provides new research perspectives for number-theoretic combinatorics
2. Practical Potential: Has potential applications in cryptography
3. Reproducibility: Complete theoretical proofs; results are easily verifiable

Applicable Scenarios

1. Theoretical research in number theory and combinatorics
2. Cryptographic scenarios involving modular arithmetic
3. Applications requiring computation of special integer set sizes

References

The paper cites 8 relevant references, covering the main development history of regular integer theory and related mathematical foundations, providing readers with complete background knowledge.

Overall Assessment: This is a high-quality mathematical paper that deepens understanding of a classical number-theoretic problem through multiple combinatorial methods and successfully establishes connections with modern cryptography. The paper's theoretical contributions are solid, its application prospects are broad, and it represents valuable work in the field of number-theoretic combinatorics.