Author
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
)
