簡易檢索 / 詳目顯示
| 研究生： |
陳建明 Chen, Jian-ming |
|---|---|
| 論文名稱： |
質數判定法 Primality tests |
| 指導教授： |
黃柏嶧
Huang, Po-Yi |
| 學位類別： |
碩士 Master |
| 系所名稱： |
理學院 - 數學系應用數學碩博士班 Department of Mathematics |
| 論文出版年： | 2008 |
| 畢業學年度： | 96 |
| 語文別： | 英文 |
| 論文頁數： | 20 |
| 中文關鍵詞： | 演算法 、質數 、合數 、質數判定法 、合成數 、多項式時間 |
| 外文關鍵詞： | prime, polynomial-time, composite, primality test, AKS algorithm |
| 相關次數： | 點閱：76 下載：2 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
In August 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena presented a remarkable algorithm (the AKS algorithm). It is an unconditional deterministic polynomial-time primality testing algorithm that determines whether an input number is prime or composite. In this thesis, the basic idea, the algorithm, the proof of correctness and the time complexity analysis of AKS algorithm, described in detail.
M. Agrawal and S. Biswas. Primality and identity testing via Chinese remaindering. Jl. of the ACM,50:429-443. 2003.
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Ann. of Math. Volume 160, Number 2 (2004), 781-793.
R. D. Carmichael. Note on a number theory function. Bull. Amer. Math. Soc., 16:232-238, 1910.
J. V. Leeuwen, editor. Handbook of Theoretical Computer Science, Volume A. Elsevier, 1990.
H. W. Lenstra, Jr. Primality testing with cyclotomic rings. Unpublished
(http://cr.yp.to/papers.html#aks has an exposition of Lenstra’s argument), August 2002.
R.Lidl and H. Niederreiter. Introduction to finite fields and their applications. Cambridge University Press, 1986.
M.Nair. On Chebyshev-type inequalities for primes. Amer. Math. Monthly, 89:126-129, 1982.
V. Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, 4:214-220,1975.
Joachim von zur Gathen and J‥urgen Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.
校內：立即公開校外：2008-08-14公開