**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**