  |
抽象数学を用いて、宇宙人レベルで難しい暗号の問題を作成します。
有限体 F₁₀₁（素数 q = 101）上の多項式環を考えます。具体的には、R = F₁₀₁[x]/(x² + 1) とします。ここで、x² + 1 は F₁₀₁ 上で既約なので、R は 101² 個の元を持つ有限体になります。
公開された要素 a ∈ R が与えられています。
エラー項 e ∈ R は小さな係数を持つ多項式で、ここでは計算を簡単にするため e = 0 とします。
次の式が成り立ちます：
b = a · s + e mod 101
公開情報として a と b が与えられているとき、秘密の要素 s を求めなさい。
b = a · s mod 101
となります。したがって、
s = b · a⁻¹ mod 101
ステップ1: a の逆元 a⁻¹ を求める
まず、a = x + 2 の逆元 a⁻¹ を計算します。これは次の等式を満たす u ∈ R を見つけることと同じです：
a · u ≡ 1 mod x² + 1
u を一般的な形 u = u₀ + u₁x（u₀, u₁ ∈ F₁₀₁）とします。
乗算を展開します：
a · u = (x + 2)(u₀ + u₁x)
= xu₀ + x²u₁ + 2u₀ + 2u₁x
x² を置き換えます： x² ≡ -1 mod x² + 1 なので、
x²u₁ ≡ -u₁
式を整理します：
a · u ≡ xu₀ - u₁ + 2u₀ + 2u₁x mod x² + 1
≡ (2u₁x + xu₀) + (2u₀ - u₁)
≡ x(u₀ + 2u₁) + (2u₀ - u₁)
等式を設定します：
u₀ + 2u₁ ≡ 0 mod 101 （x の係数が 0 であるため）
2u₀ - u₁ ≡ 1 mod 101 （定数項が 1 であるため）
u₀ ≡ -2u₁ mod 101
2(-2u₁) - u₁ ≡ 1 mod 101
-5u₁ ≡ 1 mod 101
3. 両辺に -1 を掛けます：
5u₁ ≡ -1 mod 101
4. 5 の逆元を F₁₀₁ で求めます。つまり、5 · 81 ≡ 1 mod 101 なので、5⁻¹ ≡ 81 mod 101。
5. したがって、
u₁ ≡ -81 mod 101
u₁ ≡ 20 mod 101 （なぜなら -81 + 101 × 1 = 20）
6. u₀ を求めます：
u₀ ≡ -2u₁ mod 101
u₀ ≡ -40 mod 101
u₀ ≡ 61 mod 101 （なぜなら -40 + 101 = 61）
したがって、a⁻¹ は：
a⁻¹ = u = u₀ + u₁x = 61 + 20x
ステップ2: s = b · a⁻¹ mod 101 を計算する
b = 45 + 67x と a⁻¹ = 61 + 20x なので、
s = b · a⁻¹ = (45 + 67x)(61 + 20x) mod x² + 1, 係数は mod 101
乗算を展開します：
s = (45)(61) + (45)(20x) + (67x)(61) + (67x)(20x)
= 2745 + 900x + 4087x + 1340x²
1340x² ≡ -1340
項をまとめます：
2745 - 1340 = 1405
900x + 4087x = 4987x
1405 ÷ 101 = 13 余り 92
4987 ÷ 101 = 49 余り 38
∴ 4987 mod 101 = 38
したがって、秘密の要素 s は：
s = 92 + 38x
11
