はじめに
Qiitaに投稿すべき内容ではないかもしれませんが、暗号を勉強していくと数学に戻っていく必要があります。
ここでは、他の投稿には詳しく書かないけど、重要な事をつらつらと書いていこうと思います。
（※：はたして、どこまで戻れば良いのか・・・）
整数(integer)
整数です、$\cdots,-2,-1,0,1,2,\cdots\ $ってやつです。
通常、整数の集合を$\mathbb{Z}$で表します。
さまざまな性質があることは既知であるとします。
（※：厳密にやるなら群とか環とかをやらないとダメっぽい・・・）
約数(divisor)
ある整数$n$を割り切れる数、除法の剰余(remainder)が$0$となる数、$a$を約数といいます。
ということは、$ n=ab $となる$b$が存在します。
素数(prime number)
約数が$1$と自身の値のみである数、$p$を素数といいます。
最大公約数(greatest common divisor)
２つ以上の整数において、そのいずれの約数にもなる整数を約数といいます。
その約数の中で最大の値を最大公約数といいます。
公約数 - Wikipedia
最大公約数 - Wikipedia
互いに素(relatively prime)
２つの整数$a,b$の最大公約数が$1$の場合、互いに素といいます。
ユークリッドの互除法(Euclidean Algorithm)
2つの自然数の最大公約数を求める方法です。
$a<b$とすると、$b=qa+r\ $と表す事が出来ます。
$d_0$を$a,r$の公約数とします。そうすると、$qa+r$も$d_0$で割り切れます。
したがって、$d_0$は、$a,b$の公約数となります。
$d_1$を$a,b$の公約数とします。そうすると、$b=qa+r\ $は$d_1$で割り切れます。
したがって、$r\ $も$d_1$で割り切れるので、$d_1$は、$a,r$の公約数となります。
$a,b$と$a,r$の公約数は同じとなります。
ということは、$a,b\ $と$a,r\ $の最大公約数も同じとなります。
２つの整数$a,b$に対する最大公約数を$\gcd(a,b)\ $とします。
アルゴリズムにする事ができます。
1.入力を$a,b(a\ge b)\ $とします。
2.$\ b=0\ $ならば、$a$が最大公約数です。
3.$a$を$b$で割った商を$q$、剰余を$r$とします。（$\ a = bq + r\ $）
入力を$b,r$として、2.から繰り返す。
go言語で実装してみます。
// greatest common divisor
func gcd(a, b *big.Int) *big.Int {
if a.Cmp(b) < 0 {
return gcd(b, a)
}
for b.Cmp(big.NewInt(0)) != 0 {
r := new(big.Int).Mod(a, b)
a = b
b = r
}
return a
}
素因数分解(prime factorization)
整数に対する素因数分解の存在性と一意性(unique factorization theorem)です。
※：証明はよくわからなかった・・・直感的には理解できたが・・・
素因数分解 - Wikipedia
算術の基本定理 - Wikipedia
最小公倍数(least common multiple)
倍数(multiple)は、整数を整数倍した数です。
公倍数(common multiple)は、2つ以上の整数に共通な倍数です。
最小公倍数(least common multiple)は、0ではない複数の整数の公倍数のうち最小の自然数です。
倍数 - Wikipedia
公倍数 - Wikipedia
最小公倍数 - Wikipedia
2つの整数$a,b$に対する最小公倍数を$\ \text{lcm}(a,b)\ $とします。
2つの整数$a,b$に対する、最大公約数と最小公倍数の関係は以下のとおりです。
\begin{align*}
\gcd(a,b) \times \text{lcm}(a,b) = ab
\end{align*}
整数$a,b$を素因数分解して、お互いに不足している素数を補うと考えると直感的に理解できると思います。
したがって、最小公倍数を求める式は以下のとおりです。
\begin{align*}
a,b & \in \mathbb{Z} \\
\text{lcm}(a,b) & = \frac{ab}{\gcd(a,b)} \\
\end{align*}
go言語で実装してみます。
// least common multiple
func lcm(a, b *big.Int) *big.Int {
return new(big.Int).Div(new(big.Int).Mul(a, b), gcd(a, b))
}
剰余(modulo)
整数を$n$(法)で割った余り(剰余：modulo)を剰余環とし、$\mathbb{Z}_n$で表します。
コンピュータ上で高速に演算する為だったり、データ容量を節約する為だったりと利点が多い為、利用されるケースが多いです。
剰余演算 - Wikipedia
剰余類環 - Wikipedia
分配則
加法と乗法には分配則が成り立ちます。
\begin{align*}
& a = q_1n + r_1 \\
& a \bmod n = r_1 \\
& b = q_2n + r_2 \\
& b \bmod n = r_2 \\
& r_1 < n , r_2 < n \\
\end{align*}\quad
加法の分配則は、以下のとおりです。
\begin{align*}
& (a+b) \bmod n = ((a \bmod n)+(b \bmod n))\bmod n \\
& r_1 + r_2 = q_3n + r_3 \\
& \text{left side :} \\
& a+b = q_1n + r_1 +q_2n + r_2 \\
& \qquad =q_1n +q_2n +q_3n + r_3 = (q_1 +q_2 +q_3)n + r_3\\
& (a+b) \bmod n = r_3 \\
& \text{right side :} \\
& (r_1 + r_2)\bmod n = (q_3n + r_3)\bmod n = r_3
\end{align*}\quad
乗法の分配則は、以下のとおりです。
\begin{align*}
& (a\times b) \bmod n = ((a \bmod n)\times (b \bmod n))\bmod n \\
& r_1 \times r_2 = q_4n + r_4 \\
& \text{left side :} \\
& a\times b = q_1q_2n^2 + (q_1r_2+q_2r_1)n + r_1r_2 \\
& \qquad = (q_1q_2n+q_1r_2+q_2r_1+q_4)n + r_4\\
& (a\times b) \bmod n = r_4 \\
& \text{right side :} \\
& (r_1 \times r_2)\bmod n = (q_4n + r_4)\bmod n = r_4
\end{align*}\quad
逆数
$-a$を$\mathbb{Z}_n$の正の整数で表す場合、以下のとおりです。
\begin{align*}
(-a \bmod n &= (-(q + 1)n + n - r) \bmod n \\
&= n - r \\
&= n - (a \bmod n) \\
\end{align*}\quad
$a^{-1}$は以下を満たす$a^{-1} \bmod n$です。
\begin{align*}
& ((a \bmod n)\times (a^{-1} \bmod n))\bmod n = 1 \\
\end{align*}\quad
$a\ $と$n$が互いに素($\gcd(a,n)=1$)の場合に逆数を持ちます。
詳しい証明は、以下のリンクを参照してください。
モジュラ逆数 - Wikipedia
フェルマーの小定理 - Wikipedia
これで、剰余(modulo)についての四則演算が可能になったと思います。
（※：除算については、気をつける必要がありますが・・・）
通常の四則演算の後で剰余(modulo)をとっても、剰余(modulo)で四則演算しても結果は変わらないという事です。
さいごに
この投稿に意味があるか不明ですが、なにかお役にたつのであれば幸いです。
内容には注意していますが、所詮プログラマーが書いているので正確な内容でない可能性があります。
正確な情報が知りたい場合は、数学者などに問い合わせた方が良いと思います。
また、間違い、ご指摘などありましたらお知らせください。