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

基本信息

• 论文ID: 2304.02471
• 标题: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• 作者: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Germany)
• 分类: math.CO (组合数学), math.GR (群论), math.NT (数论)
• 发表时间: 2025年10月9日 (arXiv版本)
• 论文链接: https://arxiv.org/abs/2304.02471v6

摘要

本文基于双射原理和容斥原理，为Morgado关于模$n$正则整数个数的公式提供了四种组合证明。该公式对应OEIS中的序列A055653，其中整数$m$称为模$n$正则的，当且仅当同余方程$m^2x \equiv m \pmod{n}$在整数环$\mathbb{Z}$中有解。为强调该研究的重要性，作者将此序列和Morgado公式与最近提出的RSA密码系统的多素数多幂次推广联系起来。

研究背景与动机

核心问题

本研究解决的核心问题是计算模$n$正则整数的个数，并探索其在密码学中的应用意义。

问题重要性

1. 理论意义: 正则整数的概念由Morgado在1972年首次提出，是数论中一个重要的组合对象，其计数公式涉及单位因子和欧拉函数等基本数论概念。
2. 实际应用: 在作者提出的RSA密码系统推广中，正则整数构成了可正确解密的消息空间，因此其个数直接关系到密码系统的正确性概率。

现有方法局限性

以往对Morgado公式的证明主要依赖于$\varrho(n)$函数的乘性性质，缺乏直观的组合解释。本文通过纯组合方法提供了更深入的理解。

研究动机

作者的研究动机源于他们在多素数多幂次RSA推广中遇到的实际需求，需要估计任意消息的正确解密概率。

核心贡献

1. 提供四种组合证明: 基于双射原理和容斥原理，为Morgado公式给出了四种不同角度的组合证明
2. 建立编码方案: 第四个证明给出了正则整数的显式编码，可能对序列A055653的进一步研究有价值
3. 密码学应用: 将正则整数理论与RSA密码系统推广联系，揭示了该数论概念的实际意义
4. 理论洞察: 通过组合方法自然导出$\varrho(n)$函数的乘性性质

方法详解

任务定义

输入: 正整数$n$输出: 模$n$正则整数的个数$\varrho(n)$约束: 整数$m$是模$n$正则的当且仅当存在$x \in \mathbb{Z}$使得$m^2x \equiv m \pmod{n}$

核心理论基础

定义: 整数$m$称为模$n$正则的，如果同余方程$m^2x \equiv m \pmod{n}$有整数解。

Morgado公式 (定理1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ 其中$d \parallel n$表示$d$是$n$的单位因子（即$d|n$且$\gcd(d, n/d) = 1$）。

关键性质 (命题2): 对于任意$n \in \mathbb{N}$和$m \in \mathbb{Z}$，以下条件等价：

• (a) $m$是模$n$正则的
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

四种证明方法

方法1: 等价关系证明

通过在$\mathbb{Z}^{\text{reg}}_n$上定义等价关系$m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$，建立等价类与$\mathbb{Z}^*_{n/d}$之间的双射。

方法2: 纯双射证明

构造映射$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)$

该映射的逆映射为： $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

方法3: 既约分数证明

将每个$m \in \mathbb{Z}^{\text{reg}}_n$对应到既约分数$m/n$，证明这些既约分数的分母恰好是$n$的所有单位因子。

方法4: 容斥原理证明

设$P(n)$为$n$的素因子集合，对每个素数$p \in P(n)$定义： $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ 其中$m_p$表示$p$在$m$的素因数分解中的重数，然后应用容斥原理。

技术创新点

1. 组合视角: 不同于以往基于乘性的证明，本文提供了直观的组合解释
2. 双射构造: 第二个证明给出了正则整数的显式编码和解码算法
3. 多角度分析: 四种证明从不同角度揭示了正则整数的本质结构
4. 密码学联系: 首次将正则整数理论与现代密码学应用联系起来

实验设置

数值验证

论文通过具体例子验证了理论结果：

例子: $n = 20$的情况

• 单位因子: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• 预测值: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• 实际正则整数: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• 验证: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

映射示例

论文详细展示了$f_{20}$映射的所有对应关系，验证了双射的正确性。

实验结果

理论验证

所有四种证明都成功建立了Morgado公式的正确性，每种方法都提供了独特的组合洞察。

密码学应用结果

在多素数多幂次RSA推广中：

• 正确解密概率: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• 下界估计: 对于$n = p_1^{e_1} \cdots p_r^{e_r}$（其中$p_i$为$k$位素数），有$\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• 实际意义: 当$k = 1024$时，几乎所有消息都能正确解密

相关工作

历史发展

1. Morgado (1972): 首次定义正则整数概念并给出计数公式
2. Alkam & Osba (2008): 进一步研究正则整数的性质
3. Apostol & Petrescu (2013): 研究相关函数的极值性质
4. Tóth (2008): 给出渐近结果和相关函数分析

本文贡献

相比现有工作，本文首次提供了纯组合的证明方法，并建立了与密码学的重要联系。

结论与讨论

主要结论

1. Morgado公式有丰富的组合解释，每种证明揭示了不同层面的结构
2. 正则整数在RSA密码系统推广中起关键作用
3. 对于实际参数选择，正确解密概率接近1

局限性

1. 密码学应用仅限于特定的RSA推广
2. 渐近分析有待进一步研究
3. 计算复杂度分析不够深入

未来方向

1. 开发更精确的概率界限
2. 研究序列A055653的渐近性质
3. 探索其他密码学应用

深度评价

优点

1. 理论创新: 四种组合证明各具特色，丰富了对正则整数的理解
2. 方法严谨: 证明过程严格，逻辑清晰
3. 应用价值: 与密码学的联系增强了理论研究的实际意义
4. 表述清晰: 论文结构合理，例子丰富

不足

1. 应用局限: 密码学应用仅限于作者自己提出的RSA推广
2. 计算分析: 缺乏算法复杂度的深入分析
3. 实验验证: 仅有小规模数值验证，缺乏大规模计算实验

影响力

1. 学术价值: 为数论组合学提供了新的研究思路
2. 实用潜力: 在密码学中有潜在应用价值
3. 可复现性: 理论证明完整，结果易于验证

适用场景

1. 数论和组合数学的理论研究
2. 密码学中涉及模运算的场景
3. 需要计算特殊整数集合大小的应用

参考文献

论文引用了8篇相关文献，涵盖了正则整数理论的主要发展历程和相关的数学基础，为读者提供了完整的背景知识。

总体评价: 这是一篇高质量的数学论文，通过多种组合方法深化了对经典数论问题的理解，并成功建立了与现代密码学的联系。论文的理论贡献扎实，应用前景广阔，是数论组合学领域的有价值工作。