整数論

整数論はその名の通り、整数の性質と関係についての研究で、数学が誕生した時から歴史を刻んできた由緒ある分野だ。ガウスは整数論について次のような言葉を残している。

“数学は科学の女王であり、数論は数学の女王である。”

初等整数論

初等^Elemantaryは解析的整数論、代数的整数論と対比される表現であり、そのようなツールを使用しないということであって、小学生レベルで簡単であるという意味ではない。もちろん、命題を読むこと自体は最も学識が必要ないため「とりあえず」簡単だとも言えるかもしれない。数学に興味のある才能ある子供たちは、幼い頃からこのような整数論に触れる。

倍数と約数

• 最大公約数と互いに素 $\gcd$
  • 偶数の定義
• 商と余り
  • ユークリッドの互除法
• 拡張ユークリッドの定理
• 3の倍数判定法と9の倍数判定法
• 7の倍数判定法と13の倍数判定法
• 11の倍数判定法

素数

• 素数と合成数
  • 1万番目までの素数リスト
  • 素数分解の原理
  • 算術の基本定理
  • ユークリッドの証明：素数は無限に存在する
  • オイラーの証明：素数は無限に存在する
• メルセンヌ素数
• スムース素数
• 準素数

モジュラー算術

• 整数論における合同
• 合同方程式に対する代数学の基本定理
• フェルマーの小定理
  • カーマイケル数
  • コーセット判定法
  • ミラー-ラビン素数判定法
• ウィルソンの定理
• 中国剰余定理
• 連続累乗法
• 整数論における位数
  • 原始根定理
  • $p$進数
  • 指数昇降補助定理

完全数

• オイラーのφ関数 $\phi$
  • オイラーのφ関数の乗法的性質
  • オイラーのφ関数定理
  • オイラーのφ関数和公式
• 合同方程式の累乗根
• 整数論におけるシグマ関数 $\sigma$
• ユークリッドの完全数公式
• オイラーの完全数定理

二次互反法則

• 二次剰余と非二次剰余 QR, NR
• ルジャンドル記号の乗法的性質
• オイラー判定法
• ガウスの二次互反法則
• 素数を4で割った余りが1になる必要十分条件
• 素数を3で割った余りが1になる必要十分条件

楕円曲線

• ピタゴラス数
  • ピタゴラス数の一つは必ず偶数でなければならない
  • ピタゴラス数の一つは必ず3の倍数でなければならない
  • 原始ピタゴラス数は二つの奇数で表せる
  • 原始ピタゴラス数同士は互いに素である
• ペル方程式

暗号論

初期の暗号論は整数論の代表的な応用だった。何千年も純粋数学であった整数論は、暗号に対する応用を通じて実用的な学問へと変貌を遂げ、最近では抽象代数学が応用されている。

• 暗号化と復号化

離散対数

• 離散対数
• ディフィー・ヘルマン鍵交換アルゴリズム
• エルガマル公開鍵暗号システム
• シャンクスのアルゴリズム
• ポラード-ヘルマンアルゴリズム
• 離散対数問題が容易に解ける条件

素因数分解

• 素因数分解
• RSA公開鍵暗号システム
• ゴールドワッサー-ミカリ確率鍵暗号システム
• ポラードの$p-1$素因数分解アルゴリズム
• 準素数の素因数分解問題が容易に解ける条件

代数的整数論

拡張環

• ガウス整数 $\mathbb{Z} [i]$
• ガウシアンリングのノルム
• ガウス素数定理
• アイゼンシュタイン整数 $\mathbb{Z} [\omega]$
• アイゼンシュタインリングのノルム
• アイゼンシュタイン素数定理

解析的整数論

算術関数

• 算術関数 $f$
  • メビウス関数 $\mu$
  • オイラーのφ関数 $\varphi$
  • ノルム $N$
  • 単位関数 $u$
  • マンゴルト関数 $\Lambda$
  • リウビル関数 $\lambda$
  • ディバイザ関数 $\sigma_{\alpha}$
• 算術関数の乗法的性質
• 算術関数のディリクレ積 $\ast$
  • ディリクレ積に対するアイデンティティ $I$
  • ディリクレ積に対するインバース $f^{-1}$
  • ディリクレ積と乗法的性質
  • 算術関数のアーベル群 $\left( A, \ast \right)$
  • 乗法関数のアーベル群 $\left( M, \ast \right)$
• メビウスの逆公式
• ベル級数 $f_{p}(x)$
• 算術関数の微分 $f '$
• セルバーグの恒等式
• 一般化されたディリクレ積 $\circ$
  • 算術関数の部分和に対する一般化されたディリクレ積の表現

主要参考文献

• Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition)
• Apostol. (1976). Introduction to Analytic Number Theory
• Hoffstein. (2008). An Introduction to Mathematical Cryptography