論文「群のバリアントに関連するオイラー関数」の技術的概要

著者: James Renshaw (サザンプトン大学)
日付: 2026 年 3 月
分野: 数論、群論、暗号理論

1. 研究の背景と問題提起

本論文は、群（Group）の「バリアント（variants）」という概念を離散対数問題（Discrete Log Problem, DLP）の暗号応用、特にセキュリティ強化に応用する動機から始まっています。

従来の離散対数問題に基づく暗号方式では、平文 $g$ と鍵 $e$ を用いて暗号文 $g^e$ を生成します。攻撃者が $g$ と $g^e$ から $e$ を特定する「総当たり攻撃」を行う場合、探索空間のサイズは $\phi(n)$（$n$ は群の位数）に依存します。

著者は、群のバリアントを用いた新しい暗号方式を提案し、そのセキュリティ分析において新しい種類のオイラー関数 $T(n)$ の評価が重要であると指摘しています。この関数は、鍵のペア $(x, e)$ に対する「偽陽性（false positives）」、すなわち正しい鍵とは異なるが暗号文と一致する $(y, f)$ の数を決定づけるため、その値を評価することがセキュリティの鍵となります。

2. 定義された関数 $T(n)$

論文の核心は、以下の条件を満たす整数 $m$ の個数として定義される関数 $T(n)$ です。

$$T(n) = |\{1 \le m \le n \mid \gcd(m, n) = 1 \text{ かつ } \gcd((m-1)/2, n) = 1\}|$$

ここで、$m$ は $n$ と互いに素（単位元）であり、かつ $(m-1)/2$ も $n$ と互いに素である必要があります。

• 性質: $T(n)$ は乗法的（multiplicative）ではありません。
• 関連関数:
  • オイラー関数 $\phi(n)$: $n$ 以下の $n$ と互いに素な整数の個数。
  • シェメル関数 $S_r(n)$: $n$ と互いに素な $r$ 個の連続整数の組の個数。特に $S(n) = S_2(n)$ は、$n$ と互いに素な連続する 2 整数 $(m, m+1)$ の組の個数です。

3. 手法と主要な結果（数論的解析）

著者は、$n$ の素因数分解に基づき、$T(n)$ の値を正確に計算するか、あるいは $S(n)$ を用いた精密な上下界を導出する定理を証明しました。

3.1 奇数 $n$ の場合

• 素数冪 $p^e$ に対して:
  $$T(p^e) = \frac{p^e - 2p^{e-1} - 1}{2} = \frac{S(p^e) - 1}{2}$$
• 一般の奇数 $n$（$\omega$ 個の異なる素因数を持つ）に対して:
  $T(n)$ は $S(n)$ に非常に近い値をとります。具体的には以下の不等式が成立します。
  $$\left| T(n) - \frac{S(n) - 1}{2} \right| \le \frac{3^\omega - 2^{\omega+1} + 1}{2}$$
  この結果から、$n \equiv 1 \pmod 4$ のとき $T(n)$ は奇数、$n \equiv 3 \pmod 4$ のとき $T(n)$ は偶数となることが示されています。

3.2 偶数 $n$ の場合

$n$ が偶数の場合、その構造（$2^e$ と奇数 $m$ の積）に応じて以下のようになります。

• $n = 2^e$ ($e \ge 2$): $T(2^e) = 2^{e-2}$
• $n = 2^e m$ ($m$ は奇数、$e \ge 2$): $T(n) = 2^{e-2} S(m)$
• $n = 2m$ ($m$ は奇数): $T(2m)$ は $S(m)$ の半分付近にあり、誤差項は $\omega$（$m$ の異なる素因数の数）に依存します。
  $$\left| T(2m) - \frac{S(m) - 1}{2} \right| \le \frac{3^\omega - 2^\omega + 1}{2}$$

これらの定理は、包除原理（Inclusion-Exclusion Principle）とディオファントス方程式の解の個数を数える技術を用いて証明されています。

4. 暗号への応用とセキュリティ分析

4.1 提案された暗号方式

平文 $g \in G$（$G$ は位数 $n$ の有限群）を、鍵 $(x, e)$（$x \in G, e \in \mathbb{Z}_n^*$）を用いて以下のように暗号化します。
$$c = (gx)^{e-1}g$$
ここで、$(gx)^{e-1}g$ は群 $G$ のバリアント $G_x$ における $g$ の $e$ 乗を表します。

4.2 安全性の理論的保証

攻撃者が総当たり攻撃を行う際、$(x, e)$ の組み合わせをすべて試す必要があります。しかし、定理 14 により、正しい鍵 $(x, e)$ だけでなく、以下の条件を満たす異なるペア $(y, f)$ も暗号文 $c$ を生成する「偽陽性」として現れることが示されました。

• $n$ が奇数の場合：少なくとも $S(n)$ 個の解が存在。
• $n$ が偶数の場合：少なくとも $T(n)$ 個の解が存在。

安全性への影響:

• 探索空間は $n \phi(n) \sim O(n^2)$ となり、従来の $O(n)$ に比べてセキュリティが向上します。
• しかし、$T(n)$（または $S(n)$）が小さすぎると、正しい鍵を特定する際に多くの「ノイズ（偽陽性）」が発生し、攻撃が容易になる可能性があります。
• 結論: 高いセキュリティを維持するためには、$n$ を大きくするだけでなく、$T(n)$ が $n$ に対して十分に大きくなるような $n$（例えば、$S(n)$ が大きい数）を選択する必要があります。

4.3 具体的な例（安全素数）

$p = 2q + 1$（$q$ も素数）である安全素数 $p$ を用いた場合、方程式の解の数は $p-5$ 個（$2(q-2)$ 個）となることが示されました。これは、$T(p)$ の値が $p$ に比例して大きくなることを意味し、攻撃者が正しい鍵を特定する難易度を高めます。

5. 論文の意義と貢献

1. 新しい数論関数の導入: オイラー関数やシェメル関数を拡張し、群のバリアントの構造に特化した新しい関数 $T(n)$ を定義しました。
2. 精密な評価式の導出: $T(n)$ の閉じた式（素数冪の場合）および一般の $n$ に対する厳密な上下界を導出しました。これは、乗法的ではない関数の解析において重要な成果です。
3. 暗号理論への応用: 群のバリアントを用いた DLP 暗号方式において、セキュリティパラメータとして $T(n)$ が決定的な役割を果たすことを明らかにしました。
4. 将来の課題: 離散対数問題のバリアント版における「偽陽性」の数を最小化するか、あるいは特定の $n$ において $T(n)$ を最大化する数論的な構造の探求、およびより一般的な $T_r(n)$（$(m-1)/r$ が単位元となる $m$ の個数）の研究への道筋を示唆しています。

総じて、本論文は純粋数学（数論・群論）と応用数学（暗号理論）を架橋し、新しい関数の定義とその評価が具体的なセキュリティ問題の解決にどう寄与するかを示した重要な研究です。