数式処理特論B 旧：数式処理特論2

Topics in Symbolic and AlgebraicComputation B 旧：数式処理特論2

991JB08

14MAAPM513

鍋島　克輔

Katsusuke Nabeshima

2024年度前期

2024 First Semester　

火曜3限

Tuesday 3rd Period　

理学研究科　応用数学専攻

Department of Applied Mathematics, Graduate School of Science

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

計算機代数の中で重要な理論の一つが分解である。多くの数学分野で，抽象的に元や方程式系を分解したりしているが，具体的に分解するアルゴリズムは今なお多くの分野で研究されている．因数分解とは既約成分の積に書き表すことであるが、既約成分は多項式の係数に多大に影響され難しく，現実的に因数分解ができるようになったのは20世紀に入ってからである．
本講義では，有限体上の因数分解として有名なバールカンプの因数分解アルゴリズムをまずは紹介し，その後，整数係数多項式の因数分解アルゴリズムであるザッセンバウスの因数分解アルゴリズムを紹介する．

Factorization and decomposition are important subjects in several fields of mathematics, for example, prime factorizations, factorizations of polynomials, primary ideal decompositions, and decomposition of algebraic equation systems. In mathematics and computer algebra, the factorization of a polynomial involves decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm.
Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields (also known as Galois fields). It was the dominant algorithm for solving the problem until Zassenhaus's algorithm of 1981.
In this course, factorizations of polynomials are considered in the context of symbolic computation, and Berlekamp's and Zassenhaus's algorithms for computing factorizations of polynomials are presented.

因数分解の理論と計算法を理解すると共に、数式処理システムを用いることで因数分解を取り扱うことができるようになる．

The aims of this lecture are to obtain an understanding of the theory of the factorization of a polynomial and its computation, as well as the ability to factorize polynomials using computer algebra systems.

20世紀に登場したバールカンプとザッセンバウスの因数分解アルゴリズムを理解し，因数分解が計算できるようになる．

Students who take this lecture should obtain an understanding of Berlekamp's algorithm and Zassenhaus's algorithm, and become able to compute the factorization of a polynomial.

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

なし

None

反転授業　Flipped classroom

-

とくに定めない。

Not specified.

２回のレポート課題の合計.

Total score of the two reports.

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

必要に応じて随時指示する


Text will be provided as needed.

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

必要に応じて随時指示する


Text will be provided as needed.

1:ユークリッドの互除法と剰余列
2:多項式剰余列と係数膨張
3:ヘンゼルの補題
4:モジュラー法 (1)
5: モジュラー法 (2)
6: 有限体上の多項式
7: バールカンプの因数分解アルゴリズム (1)
8: バールカンプの因数分解アルゴリズム (2)
9: 因子次数分離分解
10: 同次因子分離分解
11:ヘンゼル構成　
12:ザッセンバウスの因数分解アルゴリズム (1)
13 ザッセンバウスの因数分解アルゴリズム (2)
14:因数分解の効率化
15: まとめ

1: Euclidean algorithm and polynomial remainder sequences
2: Polynomial remainder sequences and intermediate expression swell
3: Hensel’s lemma
4: Modular algorithm (1)
5: Modular algorithm (2)
6: Polynomials over a finite field
7: Berlekamp’s factorization algorithm (1)
8: Berlekamp’s factorization algorithm (2)
9: Distinct degree factorization (DDF)
10: Equal degree factorization (EDF)
11: Hensel lifting　
12: Zassenhaus’s factorization algorithm (1)
13: Zassenhaus’s factorization algorithm (2)
14: Effective techniques
15: Conclusions

-

Mathematica

Mathematica

なし

None

N

N