11章　数論的アルゴリズム

概要

UBASICでは各種に数論的関数がはじめから組み込まれている。
しかし、一般の言語の場合は自前で用意しなければならない。

ここでは、数論的関数についての具体的な計算方法、
或いは整数論の計算で使用する各種アルゴリズムについて述べる。
取り上げるものは以下のとおり。

• ユークリッドの互除法、gcd(a,b), modinv(a,b)
• べき乗、modpow
• Moebius関数（μ(n)）、Euler関数（φ(n)）
• Lucas列
• Bernoulli数、Euler数
• 円分多項式、円分数
• Wieferich 素数
• aⁿ=c mod n
• 類多項式（Hilbert, Weber）

目次

1. ユークリッドの互除法
2. べき乗
3. Moebius関数、Euler関数
4. Fibonacci数、Lucas数、Lucas列の定義
5. Lucas列の計算方法
6. Bernoulli数、Euler数

• 形式ベキ級数の係数決定
• Bernoulli数
• Euler数
• tan z のTaylor展開

7. 円分多項式、円分数

• 円分多項式
• 円分数

8. Wieferich 素数 (2009/04/01)
9. aⁿ=c mod n (2009/07/22)
10. 類多項式（Hilbert, Weber）