Factoring Cryptosystem Moduli when the Co-Factors Difference is Bounded
Omar Akchiche, Omar Khadir · International Journal of Information Technology Modeling and Computing · 2013
Factoring large integers is a central issue in cryptography.No efficient deterministic algorithm is known.Widely used cryptographic protocols like RSA [1], Rabin [2] system or Saryazdi [3] digital signature rely on this fact.In many cryptosystems, each user must randomly choose two large prime numbers and to produce his own keys.These integers have to be sufficiently large to ensure that it is not computationally possible for anyone to factor the modulus = .Generally, the running time for generating primes takes the most important part in the total running time.Menezes and all.[4, p. 133] give several algorithms for prime number generation and primality testing.Also, in [5], the authors made experimental tests and concluded by suggesting some rapid procedures.In literature, there exist various integer factorization methods, but they are not efficient.The oldest and simplest one is the trial divisions.Fermat [6, p. 143] proposed a technique for factoring integers that are product of two primes which are close to one another.The continued fraction algorithm [7] was developed in 1931.Some decades later, John Pollard conceived his -1 and methods [8,9] respectively in 1974 and 1975.At the end of 1970s, with the advent of the public key cryptography [10,1,2], integer factorization problem becomes of crucial importance.Numerous papers, proposing ingenious and sophisticated methods, were published.Pomerance [11] discovered the quadratic sieve algorithm in 1984.Less than two years later, Lenstra [12] suggested to factor large numbers by means of finite elliptic curves.Today, the fastest known algorithm is the General Number Field Sieve (GNFS) [13, p. 103].It was invented by Pollard in 1988 and allows to factor natural integers with more than 110 digits.Stinson [14, p. 232] has