整数論テクニック集

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.1 モノイド的構造を見つけて二分累乗する (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 うまい変形で除算を回避する (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

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