合同と剰余環

使用した参考書

暗号理論入門 原書第3版

剰余類(residue class)

{b : b ≡ a mod m } = a + mZ
を a のmod m での剰余類という。
※暗号理論で用いる際 a , b ∊ Z と解釈して問題ないです。

既約剰余類(primitive residue class)

gcd(a,m) = 1
である剰余類
a + mZ
を mod m の既約剰余類という。
つまり、ある剰余類においてa,mが互いに素である時、既約剰余類となります。
※gcd(greatest common divisor)は最大公約数の意で、()内の2数の最大公約数を示します。右辺が1の時、a,mは互いに素です。

既約剰余群(primitive residue class group)

mod m の既約剰余類による群を既約剰余群といい、
(Z/mZ)*　
※「*」の部分は実際はアスタリスク
で表し、その位数を
φ(m)で表す。
※
N→N, n →φ(m)
オイラーのφ(ファイ)関数(Euler φ-function)という。
φ(m)は{1,2,3, … ,m}の中でgcd(a,m) = 1 となる a の個数である。
つまり1~mまでで互いに素である a の個数を返す関数である。