整数論テクニック集

http://kirika-comp.hatenablog.com/entry/2018/03/12/210446 pdf

• 1 基本: アルゴリズムについて 2
  • 1.1 アルゴリズムにおける不変量 … … … … … … … … … … … … . 2
• 2 mod p 上の計算 (モジュラー演算) 3
  • 2.1 基本: 整数の加減乗除 (Lv. 1) … … … … … … … … … … … … . 3
  • 2.2 基本: 逆元 (Lv. 1) … … … … … … … … … … … … … … . 3
  • 2.3 基本: 分数の加減乗除 (Lv. 2) … … … … … … … … … … … … . 4
• 3 二分累乗法 (Lv. 1) 5
  • 3.1 モノイド的構造を見つけて二分累乗する (Lv. 2) … … … … … … … … . . 6
  • 3.2 うまい変形で除算を回避する (Lv. 2) … … … … … … … … … … … 7
• 4 Abundance で殴る (Lv. 2) 9
  • 4.1 素数の abundance で殴る (Lv. 2) … … … … … … … … … … … . 9
• 5 mod p のアルゴリズム 9
  • 5.1 基礎知識 … … … … … … … … … … … … … … … … 9
  • 5.2 mod sqrt, Tonelli-Shanks のアルゴリズム (Lv. 3) … … … … … … … … . 10
• 6 群論 (Lv. 4) 14
  • 6.1 群 (Lv. 4) … … … … … … … … … … … … … … … . . 14
• 7 平方剰余の相互法則と 2 次体 (Lv. 4) 15
  • 7.1 ルジャンドル記号 … … … … … … … … … … … … … … . 15
  • 7.2 平方剰余の相互法則 … … … … … … … … … … … … … . . 16
  • 7.3 2 次体 … … … … … … … … … … … … … … … … . 16
  • 7.4 有限体 … … … … … … … … … … … … … … … … . 17
  • 7.5 フロベニウス写像 … … … … … … … … … … … … … … . 17
  • 7.6 応用例 … … … … … … … … … … … … … … … … . 17
• 8 mod p のアルゴリズム その 2 18
  • 8.1 mod sqrt その 2, Lehmer のアルゴリズム (Lv. 3) … … … … … … … … . 18
  • 8.2 mod sqrt その 3, Cipolla のアルゴリズム (Lv. 4) … … … … … … … … . 21
• 9 多項式を使うテク (Lv. 4) 22
  • 9.1 高速フーリエ変換 (FFT) (Lv. 3) … … … … … … … … … … … . . 22
  • 9.2 フェルマーの小定理 (Lv. 3) … … … … … … … … … … … … . 24
  • 9.3 巡回群構造を用いた特殊な畳み込み (Lv. 4) … … … … … … … … … . . 29
  • 9.4 1 の 2^k 乗根 mod p を用いた畳み込み … … … … … … … … … … . 30
• 10 ペル方程式 (Lv. 4) 31
• 11 単項イデアル整域 (Lv. 5) 33