On the number field sieve: polynomial selection and smooth elements in number fields

Coxon, Nicholas Vincent (2012). On the number field sieve: polynomial selection and smooth elements in number fields PhD Thesis, School of Mathematics and Physics, The University of Queensland. doi:10.14264/uql.2014.506

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s40540940_phd_correctedthesis.pdf Thesis (open access) application/pdf 1.00MB 128

Author Coxon, Nicholas Vincent
Thesis Title On the number field sieve: polynomial selection and smooth elements in number fields
School, Centre or Institute School of Mathematics and Physics
Institution The University of Queensland
DOI 10.14264/uql.2014.506
Publication date 2012-06
Thesis type PhD Thesis
Open Access Status Other
Supervisor Victor Scharaschkin
Total pages 172
Language eng
Subjects 080201 Analysis of Algorithms and Complexity
010101 Algebra and Number Theory
Formatted abstract
The number field sieve is the asymptotically fastest known algorithm for factoring large integers that are free of small prime factors. Two aspects of the algorithm are considered in this thesis: polynomial selection and smooth elements in number fields. The contributions to polynomial selection are twofold. First, existing methods of polynomial generation, namely those based on Montgomery's method, are extended and tools developed to aid in their analysis. Second, a new approach to polynomial generation is developed and realised. The development of the approach is driven by results obtained on the divisibility properties of univariate resultants.

Examples from the literature point toward the utility of applying decoding algorithms for algebraic error-correcting codes to problems of finding elements in a ring with a smooth representation. In this thesis, the problem of finding algebraic integers in a number field with smooth norm is reformulated as a decoding problem for a family of error-correcting codes called NF-codes. An algorithm for solving the weighted list decoding problem for NF-codes is provided. The algorithm is then used to find algebraic integers with norm containing a large smooth factor. Bounds on the existence of such numbers are derived using algorithmic and combinatorial methods.
Keyword Integer factorisation
Number field sieve
Polynomial selection
Smooth numbers
List decoding
Number field codes
Geometry of numbers

Document type: Thesis
Collections: UQ Theses (RHD) - Official
UQ Theses (RHD) - Open Access
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Thu, 14 Feb 2013, 10:50:37 EST by Nicholas Coxon on behalf of Scholarly Communication and Digitisation Service