Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by General Number field sieve algorithm

A. Othman, Jamal

doi:10.30684/etj.30.4.5

	Impact of decreasing polynomial degree in time needed to factor a 100 digits integer by General Number field sieve algorithm
Engineering and Technology Journal
Article 1, Volume 30, Issue 4, 2012, Pages 577-590 PDF (280.27 K)
DOI: 10.30684/etj.30.4.5
Author
Jamal A. Othman
Abstract
Factoring is very important in the field of cryptography, specifically in the Rivest, Shamir, Adleman(RSA) public-key cryptosystem, one of the most prevalent methods for transmitting and receiving secret data which its security relies on the fact that factoring large composite numbers (may be 300 digits) is computationally intensive task . The General Number Field Sieve (GNFS) algorithm is the fastest known method for factoring large integers (100 digits and more), selecting a polynomial is the first and the most important step of the general number field sieve. Choosing a "good" polynomial as a first step in GNFS algorithm widely affect the time needed to factor the integer which we intend to factor .In this paper we concern about polynomial selection step in GNFS, we try to examine practically the affect of choosing two different degrees polynomial on the time needed to factor a 100 digits integer. Base – method is a reasonable first step for generating a suitable polynomial for the GNFS, in this method we first choose the degree of the polynomial ( =4 or 5 in our case) and looking for ≈ and a polynomial of degree for which ( ) = 0 ,we begin with ( ) = Σ where the are the coefficients of the base- representation, Brian Murphy in his PhD thesis considered being the first how deeply study the effect of choosing a good polynomial on the time needed to factor a number , he came out with a parameter ( ) to measure without sieving the quality of the polynomial ,many programs have been written using Murphy parameter ( ( )) and iterate on the leading coefficient of the base- polynomial till reaching the required ( ( )) value which we intend to reach, we get use from a program freely available on the net which help us to choose a good polynomial after feeding the program with the required parameter . We find a 4th degree polynomial need less time than a 5th degree polynomial to factor an integer of a 100 digits, we present the result of factoring showing the two factors and the coefficients of the two polynomials and other information related to the factoring jobs using a python script written by Brian Gladman's available for free use on the net called (factmsieve.py) in two appendices
Keywords
Public key Cryptosystem; The Integer Factorization Problem; RSA public key cryptosystem; General Number Field Sieve; Polynomial selection in GNFS

Statistics Article View: 335 PDF Download: 222