簡易檢索 / 詳目顯示

回結果列表
研究生： 劉建甫
Liu, Chien-Fu
論文名稱： 一個有效率的整數分解法
An Efficient Method of Factoring Integers
指導教授： 黃柏嶧
Huang, Po-Yi
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 58
中文關鍵詞： 通用型數域篩選法 、RSA 、密碼學 、分解 、代數數論 
外文關鍵詞： General Number Field Sieve, RSA, Cryptography, Factorization, Algebraic Number Theory
相關次數： 點閱：85  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 一開始我們先介紹目前最流行的非對稱加密系統 RSA 和生活上的一些應用。截 至目前為止,有很多的方法在嘗試破解這個加密系統。本文討論其中一種比較有效 率的方法叫做 General Number Field Sieve。這個方法的起源是從 Fermat 的想法來 的。因此我們會從 Fermat 的方法開始做介紹並比較它們之間的差異性。接下來介 紹 General Number Field Sieve 並逐步完成裡面細節的定理內容與證明。最後找一 個例子並用程式實際演練一次。

    At the beginning, we introduce the most popular public-key cryptosystem, called RSA, and its application in real life. With this cryptosystem, there exists much more methods to crack it. In this thesis, we discuss one of these method in the following called general number field sieve, which is also more efficient than others. Since the idea of this method is come from Fermat, we will introduce some history and compare what different between them. Finally, we introduce general number field sieve, completing its details in practice and show an example by program.

    1 Introduction 8 2 History of General Number Field Sieve 10 2.1 Fermat’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Kraitchik’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Dixon’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 General Number Field Sieve 14 3.1 Ring of Algebraic Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Producing a Difference of Square . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Tools using in GNFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Finding f(x) and U . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.2 Unique Factorization Property . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.3 Perfect Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.4 Finding in Z[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 An Example of GNFS 34 4.1 Determine Parameters and Polynomial . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Each Factor Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Smooth Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.4 Solve Dependent Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5 Some Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Application in Finite Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.7 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.8 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Bibliography 41 A Program listings 42

    [1] Briggs, Matthew E. An introduction to the general number field sieve. Diss. Virginia Polytechnic
    Institute and State University, 1998.
    [2] Carl Pomerance, A Tale of Two Sieves, Notices of the American Mathematical Society, vol.
    43, no. 12, 1473-1485, 2008.
    [3] Daniel A. Marcus, Number Fields, Springer-Verlag, New York, 1977.
    [4] David M. Bressoud, Factorization and primality testing, Undergraduate Texts in Mathematics,
    Springer-Verlag, New York, 1989.
    [5] E. Weiss, Algebraic number theory, Dover Publications, New York, 1998.
    [6] J. P. Buhler, H. W. Lenstra, JR., Carl Pomerance, Factoring Integers with the Number Field
    Sieve, Springer Berlin Heidelberg, pp. 50-94, 1993.
    [7] Jean-Marc Couveignes, Computing a square root for the number field sieve, In Lenstra and
    Lenstra, Springer Berlin Heidelberg, pp. 95-102, 1993.
    [8] Johannes A. Buchmann, Introduction to cryptography, second edition, Springer, 2004.
    [9] Joseph H. Silverman, A friendly introduction to number theory, Fourth Edition, Pearson,
    New Jersey, 2012.
    [10] Peter L. Montgomery, A Block Lanczos Algorithm for Finding Dependencies over GF(2).
    Advances in Cryptology-EUROCRYPT’95 (Berlin) (L.C. Guillou and J.J. Quisquater, eds.),
    Lecture Notes in Computer Science, vol. 921, Springer-Verlag, pp. 106-120, 1995.
    [11] RSA problem, http : //en:wikipedia:org/wiki/RSAproblem.
    [12] Rudolf Lidl, Harald Hiederreiter, Introduction to finite fields and their applications, Cambridge
    University Press, 1994.
    [13] Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence, Linear algebra, Fourth Edition,
    Pearson, New Jersey, 2002.
    [14] Thomas W. Hungerford, Algebra, Graduate texts in Mathematics, vol. 73, Springer-Verlag,
    New York, 1974.

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE