Title page for ETD etd-32298-93111


Type of Document Master's Thesis
Author Briggs, Matthew Edward
Author's Email Address mbriggs@vt.edu
URN etd-32298-93111
Title An Introduction to the General Number Field Sieve
Degree Master of Science
Department Mathematics
Advisory Committee
Advisor Name Title
Brown, Ezra A. Committee Chair
Day, Martin V. Committee Member
Parry, Charles J. Committee Member
Keywords
  • Number Field Sieve
  • Factoring
  • Cryptography
  • Algebraic Number Theory
Date of Defense 1998-04-17
Availability unrestricted
Abstract
With the proliferation of computers into homes and businesses and the

explosive growth rate of the Internet, the ability to conduct secure

electronic communications and transactions has become an issue of

vital concern. One of the most prominent systems for securing

electronic information, known as RSA, relies upon the fact that it is

computationally difficult to factor a ``large'' integer into its

component prime integers. If an efficient algorithm is developed that

can factor any arbitrarily large integer in a ``reasonable'' amount of

time, the security value of the RSA system would be nullified.

The General Number Field Sieve algorithm is the fastest known method

for factoring large integers. Research and development of this

algorithm within the past five years has facilitated factorizations of

integers that were once speculated to require thousands of years of

supercomputer time to accomplish. While this method has many

unexplored features that merit further research, the complexity of the

algorithm prevents almost anyone but an expert from investigating its

behavior. We address this concern by first pulling together much of the

background information necessary to understand the concepts that are

central in the General Number Field Sieve. These concepts are woven

together into a cohesive presentation that details each theory while

clearly describing how a particular theory fits into the algorithm.

Formal proofs from existing literature are recast and illuminated to

clarify their inner-workings and the role they play in the whole

process. We also present a complete, detailed example of a

factorization achieved with the General Number Field Sieve in order to

concretize the concepts that are outlined.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  etd.pdf 870.01 Kb 00:04:01 00:02:04 00:01:48 00:00:54 00:00:04

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.