暗号の数学

剰余演算

剰余演算とは

剰余類と既約剰余類
整数 n を整数 q (q ≧ 2) で割った余りからなる集合
Z_q＝｛0, 1，2, ... , q - 1｝
を剰余類 (residue class)という．
集合 Z_q の中で (a_i, q) =１を満たす元の集合
Z_q^* = {a₁, a₂, ... , a_φ(q)}
を既約剰余類という．

オイラー関数
正整数 n に対して，1 ≦ m < n で (n, m) = 1 を満たす m の総数をオイラー関数（Euler's Function)といい，φ(n) で表す．
例えば， n = 12 のとき，m = 1, 5, 7, 11 であり，φ(12) = 4 である．
- n の素因数分解を n = p₁^e₁ p₂^e₂ ・・・ p_j^e_j (1, ・・・ p_j は異なる素数)とするとき，オイラー関数φ(n) は，次式で求められる．
  φ(n) = n (1- 1/p₁) (1 - 1/p₂) ・・・ (1 - 1/p_j)
- (m, n) = 1 のとき，φ(mn) = φ(m) φ(n) となる．
- d₁, d₂, ・・・, d_r を n の約数全体とするとき，
  φ(d₁) + φ(d₂) + ・・・+ φ(d_r) = n
  が成立つ．
  (例） n = 15 　(1, 3, 5, 15)
  
  φ(1) + φ(3) + φ(5) + φ(15) = 1 + 2 + 4 + 8 = 15
剰余還元
剰余演算は，法と呼ばれる固定整数 m (> 1) に基づく演算である．基本的な演算は，法 m による還元である．すなわち，m で割った余り r を求める演算である．
この演算は，次のように書かれる．
r := a mod m.
余り r は，0 ≦ r < m を満たさなければならない．
以下に例を示す．
11 mod 8 = 3

7 mod 9 = 7

-2 mod 11 = 9

12 mod 12 = 0

合同式

合同式とその性質
整数の集合Ｚの任意の元 x, y を整数 m で割った余りが等しいとき，x および y は m を法として合同であるという.
この関係は以下のように表される．
x ≡ y 　(mod m)
x と y の合同性は次と同値である．
- x を x = y + mt (t は整数)という形に表すことができる．
- x - y を m で割り切ることができる．
合同式の性質
- a ≡ a (mod m) ・・・反射律
- a ≡ b (mod m) ⇒ b ≡ a (mod m) ・・対称律
- a ≡ b (mod m)，b ≡ c (mod m) ⇒ a ≡ c (mod m) ・・・推移律
- a ≡ b (mod m)，c ≡ d (mod m) ⇒
  a + c ≡ b + d (mod m),
  a - c ≡ b - d (mod m),
  ac ≡ bd (mod m).
  自然数 n に対し，aⁿ ≡ bⁿ (mod m)
- a + b ≡ c (mod m) ⇒ a ≡ c - b (mod m)
- 加算，乗算について交換法則および結合法則が成立つ．
  分配法則 a(b + c) ≡ ab + ac が成り立つ．
- ac ≡ bc (mod m)，c と m は互いに素 ⇒ a ≡ b (mod m)
- ac ≡ bc (mod mc)，c と m は互いに素 ⇔ a ≡ b (mod m)
法 m における整数
法 m における整数は，法 m による還元の結果であり，次の集合である．
Z_m = {0, 1, ..., m - 1}
Z_m に対する加算，減算，乗算は，対応する整数の演算であり，法 m による還元が行われる．
0 ≦ a, b < m な数に対して，
a + b mod m = a + b 　 a + b < mの場合,
　　　　　　　 = a + b - m 　上記以外.

a - b mod m = a - b　 a - b ≧ 0 の場合,
　　　　　　　 = m + a - b 　上記以外.

a・b mod m = r　 (a・b = q・m + r), 0 ≦ r < m

a^-1 mod m = a'　(a・a' = q・m + 1)

例えば， Z₇ 上では，
3 = 6 + 4

5 = 1 - 3

6 = 4 × 5.
となる．
剰余除算
法 m における h の乗法逆元は，hk ≡ 1 (mod m) なる法 mにおける整数 k である．
整数 h の乗法逆元は，h^-1 mod m と表される． h が m と互いに素ならば，h の逆元は存在する．
g と h を法 m における整数，h が m と互いに素ならば，剰余除算 g/h mod m は，
g h^-1 (mod m)
で定義される．
べき乗剰余
v を正の整数，g を法 m における整数とするとき，べき乗剰余は g^v mod m を計算する演算である (exp(g, v) mod m とも書かれる)．
オイラーの定理
フェルマー(Fermat)の小定理
p が素数で，(a, p) = 1 のとき，
a ^p-1 ≡ 1 (mod p)
が成立つ．
上式の両辺に a を掛けることにより，合同式
a ^p ≡ a (mod p)
を得る．これはすべての整数 a に対して成立つ (p の倍数である a に対しても成立つため)．

オイラー(Euler)の定理
q > 1 かつ (a, q) = 1 のとき，
a^φ(q) ≡ 1 (mod q)
が成り立つ． q が素数 p のとき，φ(p) = p - 1 でありフェルマーの小定理になる．
オイラーの定理を用いて逆元計算を行うことができる．
(a, q) = 1 のとき，
a^{φ(q)- 1} ≡ a^-1 (mod q)
により逆元が求まる．
1次合同式
1次合同式は，次の形式の合同式である．
a x ≡ b (mod m)
(a, m) = d とする．合同式 ax ≡ b (mod m) は，b が d で割り切れない場合には成立しない．d の倍数である b に対しては，この合同式は d 個の解をもつ．
( a, m) = d > 1，a = a₁d，b = b₁d，m = m₁d とするとき，
a₁ x ≡ b₁ (mod m₁)
となる．この合同式は，(a₁, m₁) = 1 より1つの解 x₁ をもつ．
すなわち，
a₁ x₀ + m₁ y₀ = 1
なる x₀, y₀ が拡張ユークリッドの互除法により求められる．両辺を b₁ 倍して，
a₁(b₁x₀) + m₁(b₁y₀) = b₁
となることから
a₁(b₁x₀) ≡ b₁ (mod m₁)
となり，x₁ = b₁ x₀ となる．このとき，法 m に対する解は，
x₁, x₁ + m₁, x₁ + 2m₁, ・・・, x₁ + (d - 1)m₁
で与えられる．

平方剰余

平方剰余と平方非剰余
a に対し，次の２次合同式
x² ≡ a (mod q)
が解を持つとき a を q を法とする平方剰余という．解を持たないとき平方非剰余という．
一般に p を法とする平方剰余は (p - 1)/2 個存在する．また， GF(p) において，ランダムに選んだ p - 1 以下の整数 x が p を法として平方剰余となる確率は 1/2 になる． (例） x² ≡ 3 (mod 11) は，x = 6 の解をもつので，3 は 11 の平方剰余である．
Legendre記号とJacobi記号
Legendre記号

(a / p) = 1 　 (a: 平方剰余),
　　　　 = -1 　 (a: 平方非剰余).
任意の奇素数 p および p と互いに素な任意の整数 a に対して，以下の関係が成立つ(Euler基準)．
(a / p) ≡ a^(p-1)/2 mod p
Legendre記号は，a ≡ b (mod p) のとき次の関係が成立つ．
- (a / p) ≡ (b / p)
- (1 / p) ≡ 1
- (a₁a₂・・・a_k / p) ≡ (a₁ / p)(a₂ / p) ・・・ (a_k / p)
- (ab² / p) ≡ (a / p)
平方剰余の相互法則
p と q が奇素数のとき次式が成立つ．
(q / p) ≡ (-1)^{(p-1)/2・(q-1)/2} (p / q)

Jacobi記号
任意の整数 a と a と互いに素な整数 q が，
q = p₁^m₁ p₂^m₂・・・ p_n^m_n
であるとき(p_i は異なる素数)，
(a / q) ≡ (a / p₁)^m₁ (a / p₂)^m₂ ・・・ (a / p_n)^m_n
をJacobi記号という．
Jacobi記号に対しても，Legendre記号と同様な関係が成立つ．任意の相異なる奇素数 p, q に対して以下の関係が成立つ．
(p / q)(q / p) ≡ (-1)^{(p-1)/2・ (q-1)/2}

(-1 / p) ≡ (-1)^(p-1)/2

(2 / p) ≡ (-1)^(p²-1)/8

Jacobi記号の計算
入力: 整数 a，奇整数 n > 1.
出力: (a / n) ∈ {1,0,-1}.
1. x ← a, y ← n, J ← 1
2. While y > 1
3. 　x ← (x mod y)
4. 　If x > y/2 then
5. 　　 x ← y - x
6. 　　If y ≡ 3 (mod 4) then J ← -J
7. 　If x = 0 then x ← 1, y ← 0, J ← 0
8. 　While 4 divides x
9. 　　x ← x/4
10. 　If 2 divides x then
11. 　　x ← x/2.
12. 　　If y ≡ ± 3 (mod 8) then J ← -J
13. 　If x ≡ 3 (mod 4) and y ≡ 3 (mod 4) then J ← -J
14. 　Switch x and y
15. Return J
n が素数 p に等しい場合，Jacobi記号は次の式で求めることができる．
(a / p) = a^{(p - 1)/2} mod p

原始根

原始根とは
- (a, m) = 1 であれば，a^r = 1 mod m となる整数 r が存在する．そのうちの最小のものを法 m に関する a の位数という．
- 法 m に関するある数の位数は φ(m) の約数である．
- 位数が φ(m) の数を，法 m の原始根と呼ぶ．
- a が原始根ならば，次のべき乗は m を法としてすべて異なる．
  a, a², a³, ・・・ , a^m-2, a^m-1 (mod m)
原始根定理
任意の素数 p は原始根をもつ．p を法とした原始根は φ(p - 1) 個存在する．
原始根と指数
- p を法とする原始根 g
  p を法として 0 でない整数すべてが g のべきで表せる．
- 指数
  g を底とした法 p に関する a (1 ≦ a ≦ p) の指数: I(a)
  g^I(a) = a mod p
- 指数法則
  I(ab) ≡ I(a) + I(b) (mod p-1)
  I(a^k) ≡ k I(a) (mod p-1)
原始根の求め方
c = φ(m) とし，q₁, q₂,・・・, q_k を数 c の互いに異なる素な約数とする．m と互いに素な数 g が法 m に関する原始根であるためには，この数 g が合同式
g^(c/q₁) ≡ 1 (mod m), g^(c/q₂) ≡ 1 (mod m),・・・, g^(c/q_k) ≡ 1 (mod m)
を一つも満足しないことが必要十分である．

(例）法 41 に関する最小の原始根を求める．
1. φ(41) = 40 = 2³・5，40/5 = 8, 40/2 = 20
2. g⁸ ≡ 1 (mod 41), g²⁰ ≡ 1 (mod 41) を一つも満足しないことを検査する．
3. 2²⁰ ≡ 1 (mod 41), 3⁸ ≡ 1 (mod 41), 4²⁰ ≡ 1 (mod 41), 5²⁰ ≡ 1 (mod 41) より，2, 3, 4, 5 は原始根ではない．
4. 6⁸ ≡ 20 (mod 41), 6²⁰≡ 40 (mod 41) より，6 は原始根である．

Page Top