以解析組合的方法討論有限體下多項式的性質

Random Polynomials over Finite Fields via Analytic Combinatorics

江紀葳

指導教授 ： 符麥克

國立交通大學/理學院/應用數學系暨研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.01080

摘要

數學領域經常研究有限體下隨機多項式質因式的性質（如整係數質因式的性質）。而這些性質常常應用在資訊工程、密碼學、編碼理論...等方面上。

　　這篇論文有三個研究動機：第一個動機是想整理參考文獻中有關有限體下隨機多項式質因式分解的性質。第二個動機是想展現如何用解析組合來證明這些質因式分解性質的結果。第三個動機是想將質因式分解性質的結果應用在質因式分解的演算法中。這些性質大多在文獻上只有粗淺的說明，而這篇論文將提供這些性質的詳細的證明及結果。

　　而這篇論文主要的概述：第一章，我們將給個簡短的概況並整理後面即將證明的結果。第二章，我們會給解析組合中常用的定理及詳細的證明。第三章，我們會用第二章中的結果來證明有限體下隨機多項式質因式的性質。最後，第四章，我們將討論第三章結果的應用。

關鍵字

解析組合 ； 多項式 ； 有限體

並列摘要

Properties of irreducible factors of random polynomials over finite fields (similar to properties of irreducible factors of random integers) have been intensively studied in the mathematical literature. Such properties have applications in computer science, cryptography, coding theory, etc.

The purpose of this thesis is three-fold. First, we want to give a survey of results which have been obtained in the literature on properties of irreducible factors of random polynomials over finite fields. Secondly, we want to demonstrate the usefulness of analytic combinatorics to prove such results. Finally, we want to discuss some applications of these properties to polynomial factorization over finite fields. We will provide detailed proofs of all the results (some of the proofs have been only sketched in the literature).

We give a brief outline of the thesis. In Chapter 1, we will give a short outlook and summarize the results we are going to prove. In Chapter 2, we will recall some tools from analytic combinatorics with detailed proofs. In Chapter 3, we will use the results from Chapter 2 to prove our results on random polynomials. Finally, in Chapter 4, we will discuss applications of the results from Chapter 3.

並列關鍵字

Analytic Combinatorics ； Polynomial ； Finite Fields

參考文獻

[1] ABRAMOWITZ, M., STEGUN, I. (1970). Handbook of Mathematical Functions. Dover, New York.

[2] BACH E., SHOUP V. (1990). Factoring Polynomials Using Fewer Random Bits, Journal of Symbolic Computation, 9, 229–239.

[3] BERLEKAMP E. (1967). Factoring Polynomials over Finite Fields, Bell Systems Technol. J., 46 1853–1859.

[5] BOCHNER S., CHANDRASEKHARAN K. (1949). Fourier Transforms. Princeton University Press.

[7] CHOR, B., RIVEST, R. L. (1985). A Knapsack type Public Key Cryptosystem based on Arithmetic in Finite Fields, IEEE Trans. Inf. Theory, 34, 901–909.