Lattice Points on the Fermat Factorization Method

Abstract

In this paper, we study algebraic properties of lattice points of the arc on the conics x2−dy2=N especially for d=1, which is the Fermat factorization equation that is the main idea of many important factorization methods like the quadratic field sieve, using arithmetical results of a particular hyperbola parametrization. As a result, we present a generalization of the forms, the cardinal, and the distribution of its lattice points over the integers. In particular, we prove that if N−6≡0 mod 4, Fermat’s method fails. Otherwise, in terms of cardinality, it has, respectively, 4, 8, 2α+1, 1−δ2pi2n+1, and 2∏i=1nαi+1 lattice pointts if N is an odd prime, N=Na×Nb with Na and Nb being odd primes, N=Naα with Na being prime, N=∏i=1npi with pi being distinct primes, and N=∏i=1nNiαi with Ni being odd primes. These results are important since they provide further arithmetical understanding and information on the integer solutions revealing factors of N. These results could be particularly investigated for the purpose of improving the underlying integer factorization methods.