2025-11-10T02:39:08.150295

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

Dohmen, Lange-Geisler

We present four combinatorial proofs based on the bijection principle and the inclusion-exclusion principle to Morgado's formula on the number of non-congruent regular integers modulo $n$, given by the sequence A055653 in OEIS, where an integer $m$ is regular modulo $n$ if the congruence $m^2 x \equiv m \pmod{n}$ has a solution for $x$ in $\mathbb{Z}$. To emphasize the significance of the subject, we relate this sequence and Morgado's formula to a recent multi-prime multi-power generalization of the RSA cryptosystem.

academic

$n$ を法とする正則整数の個数とその暗号学への意義について

基本情報

論文ID: 2304.02471
タイトル: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
著者: Klaus Dohmen, Mandy Lange-Geisler (ミットヴァイダ応用科学大学, ドイツ)
分類: math.CO (組合せ論), math.GR (群論), math.NT (数論)
発表日: 2025年10月9日 (arXiv版)
論文リンク: https://arxiv.org/abs/2304.02471v6

要旨

本論文は、双射原理と包除原理に基づいて、Morgadoによる $n$ を法とする正則整数の個数に関する公式に対して4つの組合せ論的証明を提供する。この公式はOEIS中の数列A055653に対応し、整数 $m$ が $n$ を法として正則であるとは、合同方程式 $m^2x \equiv m \pmod{n}$ が整数環 $\mathbb{Z}$ において解を持つことと定義される。本研究の重要性を強調するため、著者らはこの数列とMorgado公式を、最近提案されたRSA暗号系の多素数多冪次推広と関連付けている。

研究背景と動機

核心問題

本研究が解決する核心問題は、 $n$ を法とする正則整数の個数を計算し、その暗号学における応用意義を探究することである。

問題の重要性

理論的意義: 正則整数の概念はMorgadoにより1972年に初めて提案され、数論における重要な組合せ対象であり、その計数公式はユニット因子とオイラー関数などの基本的な数論概念を含む。
実践的応用: 著者らが提案するRSA暗号系の推広において、正則整数は正しく復号化可能なメッセージ空間を構成するため、その個数は暗号系の正確性確率に直接関係する。

既存方法の限界

従来のMorgado公式の証明は主に $\varrho(n)$ 関数の乗法性に依存しており、直感的な組合せ論的説明が不足していた。本論文は純粋な組合せ論的方法を通じてより深い理解を提供する。

研究動機

著者らの研究動機は、多素数多冪次RSA推広において遭遇した実践的必要性に由来し、任意のメッセージの正確な復号化確率を推定する必要があった。

核心的貢献

4つの組合せ論的証明の提供: 双射原理と包除原理に基づいて、Morgado公式に対して4つの異なる観点からの組合せ論的証明を提供
符号化スキームの確立: 第4の証明は正則整数の明示的な符号化を与え、数列A055653のさらなる研究に価値がある可能性
暗号学的応用: 正則整数理論をRSA暗号系の推広と関連付け、この数論概念の実践的意義を明らかに
理論的洞察: 組合せ論的方法を通じて $\varrho(n)$ 関数の乗法性を自然に導出

方法の詳細

タスク定義

入力: 正整数 $n$ 出力: $n$ を法とする正則整数の個数 $\varrho(n)$ 制約: 整数 $m$ が $n$ を法として正則であるとは、 $m^2x \equiv m \pmod{n}$ を満たす $x \in \mathbb{Z}$ が存在することと定義される

核心的理論基礎

定義: 整数 $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$

4つの証明方法

方法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$ は $m$ の素因数分解における $p$ の重数を表し、その後包除原理を適用する。

技術的革新点

組合せ論的視点: 従来の乗法性に基づく証明と異なり、本論文は直感的な組合せ論的説明を提供
双射の構成: 第2の証明は正則整数の明示的な符号化と復号化アルゴリズムを与える
多角的分析: 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}$ 写像のすべての対応関係を詳細に示し、双射の正確性を検証している。

実験結果

理論的検証

4つの証明すべてが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$ の場合、ほぼすべてのメッセージが正確に復号化される