暗号理論入門 3.16〜3.18
- 作者: 林芳樹
- 出版社/メーカー: 丸善出版
- 発売日: 2012/04/20
- メディア: 単行本
- この商品を含むブログを見る
3.16 剰余環の分解
中国人の剰余定理を使うと、大きな剰余環 の代わりに、多くの小さな剰余環 で計算することができる。
を互いに素な整数とし、 であるとする。このとき、写像
は環の同型写像である。
での計算が での計算に帰着できる。
の剰余類を の剰余類の組に移し、組の各成分ごとに計算し、中国人の剰余定理で結果を の剰余類に戻す。
3.17 オイラーの 関数の決定
を互いに素な自然数とし、 とする。
このとき、 である。
が成立する。
例. が成立する。
の因数分解がわかっている場合、 は時間 で計算される。
3.18 多項式
は単位元 をもつ可換環とする。 上の一変数の多項式(polynomial)とは
と表されるもののことである。
変数 についての 上のすべての多項式の集合は で表される。
とする。このとき を多項式の次数といい、 と書く。