僕の知ってる数論
この章で出てくる文字は、断らない限り全部整数。
合同式
$a \equiv b \ (mod \ n) \Leftrightarrow \exists k \in \mathbb Z, a-b=kn$
$a,b,c \in \mathbb Z, m \in \mathbb N$
- $a \equiv b \Rightarrow a+c \equiv b+c$
- $a \equiv b \wedge c \equiv d \Rightarrow ac \equiv bd$
- $a \equiv b \Rightarrow a^m \equiv b^m$
最大公約数
aとbの最大公約数を$\gcd(a,b)$とか単に$(a,b)$とか書く。
ユークリッドの互除法を用いると、$\gcd(a,b)$は$O(\log ab)$で求まる。
さらに、拡張されたユークリッドの互除法によって、(x,y)に対して$ax+by=\gcd(x,y)$なる(a,b)を求められる。
逆元
$(x,n)=1$のとき、$ax \equiv 1 \ (mod \ n)$なるaを容易に求められる。この$a$を、$x^{-1}$とかく。
求めるには、上の拡張されたユークリッドの互除法において、$x=x, y=n, a=a$とすればよい。
カーマイケルの定理/オイラーの定理/フェルマーの小定理
カーマイケルの定理: カーマイケル関数λに対して、
$(a,n)=1 \Rightarrow a^{\lambda (n)} \equiv 1 \ (mod \ n)$
上の定理を弱くして、次の定理が示される。
オイラーの定理: オイラーのトーシェント関数φに対して、
$(a,n)=1 \Rightarrow a^{\phi (n)} \equiv 1 \ (mod \ n)$
更に弱くして、次の定理が示される。
フェルマーの小定理: $p \in \mathbb P$に対して、
$(a,p)=1 \Rightarrow a^{p-1} \equiv 1 \ (mod \ p)$
中国剰余定理
中国剰余定理: $(m,n)=1$のとき、
$x \equiv a \ (mod \ m)$かつ$x \equiv b \ (mod \ n)$なる$x$が$mn$を法として一意的に存在する。
特に、$(m,n)=1$のとき、
$x \equiv y \ (mod \ m) \wedge x \equiv y \ (mod \ n) \Leftrightarrow x \equiv y \ (mod \ mn)$
一意的とは、そのようなxのmnを法とした剰余はすべて等しいということ。
暗号でしょっちゅうでてくる気がする定理
$k \in \mathbb N$で、$a^m \equiv 1 \ (mod\ n)$のとき、$a^{km} \equiv 1 \ (mod \ n)$
それはそう。
平方剰余
$(a,b)=1$のとき、$x^2 \equiv a \ (mod \ b)$なるxが存在するときaはbを法として平方剰余であるという。
ルジャンドル記号: aが奇素数pを法として平方剰余なとき、$\left( \frac {a} {p} \right)=1$、平方非剰余なとき$\left( \frac {a} {p} \right)=-1$とかく。
定理: $\left( \frac{ab}{p} \right) = \left( \frac {a}{p} \right) \left( \frac {b}{p} \right)$
オイラーの規準: pは奇素数。
$\left( \frac{a}{p} \right)≡a^{\frac{p−1}2} \ mod\ p$
http://mathtrain.jp/criterion
平方剰余の相互法則: p,qは奇素数。
$\left( \frac {p}{q} \right)\left( \frac {q}{p} \right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}$
拡張みたいなので、ヤコビ記号とかいうのもある。
さらに拡張で、クロネッカー記号とかいうのもある。
生成元
集合$G$に対して位数とは、$|G|$のこと。群$(G,+)$で、$g \in G$の位数とは、$g^n = 1$となる最小の自然数nのこと。
ある二項演算があってそのもとで$G = {g^n | n \in \mathbb N }$のとき、$g$を$G$の生成元といい、$G=$と書く。
$Z_p$には生成元が少なくとも1つ存在する。
Rabin
準備
- $p,q \in \mathbb P (p \neq q)$を用意
- $n=pq$を計算
- $0 \le B \lt n$を用意
後々を考えると、B=0ならp,qはどんな素数でも良いけれど、Bが0でないならp,qは奇素数でなければならなそう。
暗号化
$c=x(x+B) \ mod \ n$
復号
- $x_p = \pm \sqrt {c + \frac {B^2}{4}} - \frac {B}{2} \ mod \ p$,$x_q = \pm \sqrt {c + \frac {B^2}{4}} - \frac {B}{2} \ mod \ q$ を計算
- $x \equiv x_p \ (mod \ p) \wedge x \equiv x_q \ (mod \ q)$を中国剰余定理で計算
- 求まる４つのxのうちいずれかが解
平方根の計算には、たとえばCipolla's algorithmを使う。
p,qに4k+3型の素数を使うと、平方根の計算に公式が使えて簡単になる。
RSA
準備
- $p,q \in \mathbb P (p \neq q)$を準備
- $n=pq, \phi(n)=(p-1)(q-1)$を計算
- p,qは破棄
- $e \in \mathbb N \wedge (e, \phi(n))=1 \wedge e \lt \phi(n)$なる$e$を準備
- $\phi(n)$を法として$d=e^{-1}$を計算
暗号化
$c = p^e \ mod \ n$
復号
$p = c^d \ mod \ n$
証明
$c^d \equiv p^{ed} \equiv p^{k \phi(n)+1} = p^{k \phi(n)} p \equiv 1p \equiv p$
tools
prove it!
- ユークリッドの互除法
- フェルマーの小定理、オイラーの定理（どちらから証明しても良い）
- 平方剰余ならばルジャンドル記号が1になる
- ルジャンドル記号が1ならば平方剰余
- $Z_p$の生成元の存在
Written with StackEdit.